Fまで六完。
コンテスト後のツイート
E 二次元DPをimosで高速化
— titia (@titia_til) April 23, 2022
F クエリを後ろから見て、heapqで足すもの高々K個を管理
G - Xor Cards
解説AC。非常に苦労した。
基底の個数が高々60個になるというのは気付かなくてはいけないが、その後の部分問題も難しい。自力が問われる。
Nが60のとき（つまり、三乗でも良いというとき）どう解けば良いかは、桁を意識して考えれば良い。（桁DPではないけれど、桁DPするような気持ちで）
60個の基底を表の数が大きい順に並べた後、「その基底を使ったとき（つまり裏の数のxorがかかる）どうなるか？」「使わなかったときどうなるか？」を場合分けして考える。
ただ、「ある基底を使ったときどうなるか？」を考えている中でも上の二つの場合分けをするのだが、そのときは挙動が違うに注意。
今まで使ったもの達の表の数のxorがKを超えているかどうかで場合分けをしなくてはいけない。
また、表の数に0が含まれている場合がコーナーになっている。これにも注意しなくてはいけない。
解法に至るまでも難しいが、コーナーに気を付けて実装しなくてはいけないのも厳しい。ACに至るまではかなり大変だと感じた。
0 件のコメント:
コメントを投稿