AtCoder Regular Contest 185

　AB二完。

コンテストへのリンク

コンテスト後のツイート

B A[i]が今までのMINより小さいなら、A[i]をMINまで増やし、そこでとっておく値（POと呼ぶ）は後で使い切りたい。A[i]がMINより大きいときは、まず使っていないPOを使い（その次にPO2を使い）、足りなければMINを上昇させて対応。そこで余った値（PO2）は適宜使う。最終的にPO=0にときYes

— titia (@titia_til) October 13, 2024

C - Sum of Three Integers

　解説放送を見てAC。

　FFTは全く考えなかったが、登場回数の配列同士を畳み込めば、二つの配列の和の要素の登場回数になる……というのは初見ではなかったかもしれない（よく覚えていないが）。これは身に着けておきたい。

　ただ、解法が分かった後もACに非常に苦労した。ランダムケースで実行しても何で落ちているのかが分からず、かなりたくさん提出デバッグをしてしまった。

・PythonでFFTを使うなら、配列をnumpy.arrayで書き、np.fft.rfft(A,k)やnp.fft.irfft(f)を使うと速い。

・畳み込み後の要素の値が大きくなることがあるため、np.fft.rfft(A,k)のkの値をギリギリに取るのではダメ。最大値をきちんと見積もる。

　このあたりが問題だった。気を付けないと。

D - Random Walk on Tree

　解説放送を見てAC。

　解説放送で一番難しいといっていたパートは、ChatGPTに「ランダムウォークで、スタート地点からn歩の点にはじめて到達する歩数の期待値を教えて下さい。」と聞いたら、「スタート地点 0 から n に初めて到達するまでの期待値は、1次元ランダムウォークでは次のように表せます:

・En=n^2　つまり、最初に n に到達するための期待歩数は n^2  です。」と正しい返事がきた。

　また、コンプガチャについてはけんちょんさんの記事など詳しいものがある。

　どちらも、自力で導出できると良いけど、覚えておいても良いくらいの内容な気がする。

　なので、対称性に関する考察さえきちんと行ってどんな問題に帰着できるか分かれば、あとは知識（もしくは調べて）で解けたんですね。

E - Adjacent GCD

　解説放送を見てAC。

　約数包除を行うとき、各素数についての他次元平面と考えると分かりやすい、というのは知っていた（が、コンテスト中は出てこなかった）。

　

　で、約数包除のとき、あるxについて、その約数に関する値の総和を取るとxになるような値があると良い。そういうのがあれば、毎回包除をして約数の個数^2の計算時間をかけず、約数の箇所にある値の和を取る/値を書き込むさえすれば、毎回約数の個数回の計算時間で済む。

　それを実現するのが、オイラーのトーシェント関数だった！

　オイラーのトーシェント関数の定義を考えれば簡単に分かることなのだが、はじめて知りました。

　約数包除に関して理解できた気がするので、もう忘れないといいな……。

　なお、今回の問題は、100000までのトーシェント関数の値と約数のリストを予め列挙してACしました。

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