AtCoder Beginner Contest 164 感想
https://atcoder.jp/contests/abc164/tasks
15位。
D問題
前から見ても後ろから見ても解けることは知ってて、考察の難しさも変わらない。前からやると逆元が必要で、後ろからやると逆元が要らないので後ろからやる。
E問題
頂点と銀貨枚数の組を状態としてダイクストラ法。銀貨を2500枚より多く持っていても得しないので2500枚より多い値を2500枚と同一視すればいい。状態数が50×2500程度、遷移が100×2500程度なのでこれで解けた。構造化束縛を使わなかったのが後悔。
F問題
ビットごと独立は典型。結局01の問題。最初に思いつくのは以下のこと。
- 論理総積が1の行は、すべての要素が1になっている。
- 論理総和が0の行は、すべての要素が0になっている。
行を入れ替えるとか、列を入れ替えるとかしても考察上影響がないので、下図のように制約が固まっている例で考察を進める。
さっきの考察によってピンク色の部分は確定している。可能盤面でうまく動くプログラムを作れば良くて、不可能盤面で変な動きになるのは無視できる。プログラムの最後に解の検証をすればいい。不可能判定に頭を使わない。
緑の部分も確定できる。
残った部分をどうするか。３行２列と２行３列は対称的なので、３行２列だけに着目する。ここで場合分けが入る。
２行２列、４行２列のいずれかの領域が存在する場合、３行２列はすべて０埋めするのが最適。存在しない場合、斜めに１を配置。可能盤面なら構成できる。しかし市松の方が多分書きやすい。
