キーエンス プログラミング コンテスト 2020

　時間ギリギリでEを通して五完。橙パフォは出なかったものの、自分としては上出来でした。

コンテストへのリンク

A - Painting

 一回で、H, Wのうち大きい方だけ増やせる。

B - Robot Arms

・とりあえずソート

　して考えたいけど、普通に左端でソートしても上手くいかないので、右端でソートしたら上手くいった。

　「区間スケジューリング問題」そのものだということは、コンテスト中には気付いてませんでした……。

C - Subarray Sum

　Sそのものを置けば区間が一つ作れる。残りはできるだけ大きい数字を置けば邪魔しない。

　こういうギャグっぽい問題がAtCoderで出ることは少ないので面食らった。

D - Swap and Flip

・あるカードの位置を決めたら、その偶奇を見ればAかBかが分かる

　ということに気付くのが重要。

　あとは、各iについて、A, Bのどちらを使うかで全探索した。そうすると、「奇数番目で使うか偶数番目で使うか」も分かる。奇数番目で使いたいもの、偶数番目で使いたいものそれぞれをソートしたものをS0, S1とすると、

$S0[0]\leqq S1[0] \leqq S0[1] \leqq S1[1] \leqq \dots $

　となっていれば良い。そのときの必要Swap回数は転倒数。

　公式解説放送では（bitDPによる解説の後に）この方法についても触れていて、同じ数字があったときの処理を気にしていた。
　でも、同じ数字があったときは、元の順番が小さいものが最終的な順番としても小さい箇所にあった方が良いので、普通に実装すれば気にせずに済むと思う。

E - Bichromization

　結構焦っていたので、嘘解法かも、と心配していたけどどうやら嘘じゃなかった。

・移動コストが最小の点を考える

　のが重要。最小全域木のクラスカル法のイメージだと思う。

　そもそも、同じ色同士の点をつないでもコストの増加にしか繋がらない。白い頂点同士が重みwで繋がっているとき、それらの点のコストの最小値の候補は「もう片方の点のコスト+w」となるので。

　だから、頂点の配色や辺の重みを決めていく際に、今まで使っていない二点でコスト最小（で一致する）の二点があれば、その二点を白と黒で繋がないとダメ。

　あとは、残っている頂点の中で最小のものを探して、それが、既に使われた頂点と隣接していれば、その頂点と同じ色で塗って、重みは差分にする……というようにした（この辺もクラスカルっぽく考えていた）。

　が、解説を見ると差分を取る必要はなかったようで。

　別な色に塗って、重みはDをそのまま使えば良かったらしい。そりゃあそうですね。

　木が作れたら、残りの辺の重みは$10^9$にすればOKです。

F - Monochromization

　公式解説放送を見た後、ARMERIAさんの解説記事、けんちょんさんの解説記事、kmjpさんの解説記事を交互に読みながらなんとか解説AC。

　前半の判定問題のパートは、解説放送を聞けば理解できたけど、その後が……。

　解説を読んでも、サンプル2のような元の盤面に黒マスが一つもない場合すらよく分からなかったので、絵を描いてみた。この場合の最短経路Combi(6,3)=20通りを絵に描いて、それぞれの下の部分が黒くなったものの行・列の入れ替えでできる盤面を調べた。計算してみたら確かに230個になった。それを見ながら解説を読むとDPの方針が分かってきた。

　これがDPでできるというイメージがなければ、前半のような判定ができたとしてもあまり意味がないと切り捨ててしまいそう。類題経験がないと厳しい気がするけどなぁ……。

　個人的には、「最初の盤面に黒マスが一個もない場合」を部分点で出しても良かった気がする。これだけでも十分難しい（600点以上はある）と思うけど、部分点で出すなら400～500点？　誘導にもなるし、良いと思うんだけど。

　ただ、黒マスが一個もないと、H, Wの入力二つから答えを求めることになるので、予測等で解かれかねないんですかね？

　なお、計算量が$O(2^{H+W}*H*W)$で、$10^8$オーダーとかになるので、PyPyだと厳しいかと思ったのですが、特に変な高速化をせずとも自然に書けばACできました。（自然に書けなかったので、何度かTLEの提出をしてしまいましたが）