M-SOLUTIONS プロコンオープン2021(AtCoder Beginner Contest 232)

　Fまで六完。

コンテストへのリンク

コンテスト後のツイート

M-SOLUTIONS プロコンオープン2021(AtCoder Beginner Contest 232) Fまで。
C permutations全探索
D Cより大分簡単では？
E DP。行/列の一致不一致の四つを見る。H!=Wもサンプルに入れて欲しい（2ペナ）
F bit DPだと気付くまで時間かかった。
H 実装がんばればいけると思ったけど、WAのまま終了。

— titia (@titia_til) December 19, 2021

G - Modulo Shortest Path

　解説放送を見てAC。

　snukeさんも解説中に言っていたけど、私がコンテスト中に考えたのもフローだった。「フローが上手くいかない」と気付かないと厳しい。、そう気付けるようになるためには、もっとフローの練習を積まないといけないか。

　上手くグラフを作ればダイクストラでいけそう、と気付くためには、制約に注目するのが重要。「$A_i, B_i < M$」の制約の意味（和が2*Mを超えない！）に気付けば思いついてもおかしくないかな、と思う。

　

H - King's Tour

　一応自力AC。

　コンテスト中に考えたことは、

・(a, b)を通らないように周囲を一列、もしくは一行ずつ埋めていく。

・(a, b)からマンハッタン距離が遠いところを優先して通るように埋めていく。

　の二つ。

　一番目、二番目の片方ずつだと半分程度WAになったが、二つを組み合わせた（一個目で作った答えの途中から二番目を使う）らWAが二個まで減った。

　さらに、二番目で使っていた評価値「マンハッタン距離」を、max$($abs$(a-x),  $abs$(b-y))^2+$マンハッタン距離にしてみたらAC。

　Hackケースがあるかもしれないけど、それほど良い方法もない問題らしいので、まあ。