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というのは、典型の一つなのかもしれない。頭に入れておきたい。