Educational Codeforces Round 81 (Rated for Div. 2)

　Dまでの四完。
　それほど失敗した気はしなかったのに、順位はイマイチでした。

コンテストへのリンク

A. Display The Number

　各数字を点灯させるのに何本の電灯が必要かを考えると、1の二本と7の三本が少ない電灯で済むことが分かる。

　基本的には1を使い、最後に1余るようなら、一番上の桁を7にする。

B. Infinite Prefixes

　s一回書き終ると、（1の個数）-（0の個数）が何個変化するかを計算。

　また、その間に、0を基準として、（1の個数）-（0の個数）がどのように変化するかを計算。

　たとえば、s="1101"なら一回ごとに（1の個数）-（0の個数）は+2し、

　0→+1→+2→+1→+2

　のように変化するので、

0: 一回

+1: 二回

+2: 一回

　の値を取る。……というようなことを利用して計算した。

　xの値になりうるのは何回繰り返したときかを計算し、そのそれぞれの回で、何回ずつxを取るかを探索して和を取った。

　ただ、ながたかなさんのブログのように、sの文字のindexに着目する方が賢かったようです。変化が±0のとき以外は、各indexのときにxになることは一回しかありえない。

　なるほど確かにそうですね。

C. Obtain The String

　けんちょんさんの、「部分文字列を走査する DP」の記事のDPを使って解く問題。特に、

・next[i][c]:= S の i 文字目以降で最初に文字 c が登場する index

　を求めておくのが本質だと思います。

　なお、AtCoder Beginner Contest 138　E - Strings of Impurityとほぼ同じ問題でした。コンテスト中は全く思い出せなかった……。

D. Same GCDs

　a以上a+m-1以下のxで、gcd(x, m)=gcd(a, m)となるようなxの個数を求めれば良いので、gcd(a,m)を素因数分解し、約数包除を用いて計算した。

　ただ、ユークリッドの互除法を考えれば、gcd(m+i, m)=gcd(i, m)なのだから、0～m-1の範囲で数えればOKだったようです。

　さらに、mをGCD(a, m)で割れば、x=m/GCD(a, m)としたとき、xと互いに素なx以下の自然数の個数ということになり、これはオイラーのφ関数として知られているものなようです。

E. Permutation Separation

　ARMERIAさんのブログの記事やけんちょんさんのブログの記事を見て通した。コンテスト直後のTwitterで、「そんなに難しくない」という意見も見たけど、個人的には難問だと思っています。

　まず、

・最初にどう分けるか

・最終状態がどうなってるか

　を考えるのは自然。

　ただ、さらに、コストの計算もするとなると、O($n^3$)かかってしまいそう。

　三乗オーダーだと、高速化したとしてもACできる計算量にはなりそうもない……コンテスト中はそう考えて、何か天才的な方法があるんじゃないか……と迷走してしまった。が、実際は上記の方法を高速化すればO(nlogn)まで落ちる。

　その高速化も簡単ではない。私は上記の解説ブログを読んでもなかなか理解できず、初期状態と最終状態を変化させた場合のコストを表にしてみてようやく理解することができた。

　まあ、「高速化できるはず」という気持ちになれば、差分を取ってみるのは自然だし、思いつけない内容ではないと思うけれど……。

　無理そうに見えても、

・高速化できないか試す

　ことが大事か。

　なお、PyPyで通すには制限時間も結構厳しく、手持ちの遅延Segment treeでは通らなかったため、Starry Sky tree（？）を使って通しました。

　なお、ながたかなさんのブログ記事によると、そういったデータ構造を使わずとも通せるようですが……私は理解できていません。

F. Good Contest

　ARMERIAさんのブログの記事やけんちょんさんのブログの記事を参考に解説ACした。

　Eより解法は思いつきやすいと思う。

　DPしよう、という方針が見えれば座標圧縮は自然。

　ただ、DPの遷移は難しい。

　同じ区間を使い続ける場合の処理を一度に行う……という方法に気付けなければいけない。ただ、このDPは、キーエンス プログラミング コンテスト 2020　F - Monochromizationとかなり似ています。（この問題の応用がMonochromizationと思って良さそう）

　逆に言えば、こういう、順次更新していくだけではなく、（部分的に）一度に遷移させるDPというのは、典型の一つなのかもしれない。頭に入れておきたい。

キーエンス プログラミング コンテスト 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の提出をしてしまいましたが）