先日開催された、AtCoder Beginner Contest 333の勉強メモです。
問題への言及がありますので、今後解く予定の方はご注意ください。
使用言語はPython・提出はPyPy3です。

公式解説

A～B

愚直にやります。Bは各頂点に0～4を割り振ると楽です。
提出例: ABC333A, ABC333B

C Repunit Trio

問題文はこちら

解法
f(x): 1がx個連続した整数(レピュニット) と定義します。

入力例3を見ると N = 333 のRepunit Trioは1122_2222_2233です。
なので高々12桁のレピュニットを全探索すればよいです。
計算量は$O(k^3)$(k: 探索する桁数 = 12)です。
3つのレピュニットを降順に並べたものを$f(x),f(y),f(z)$($x \geq y \geq z$)とします。
するとx,y,zの組を辞書順昇順に列挙すればよく、これはforループで可能です。計算量は$O(N)$です。
$f(y)$を固定したとき、$y \geq z ( \geq 1)$を満たすzはy個あります。
従って$f(x)$を固定すると、$x \geq y \geq z$を満たすy,zの組数は
$\sum_{y=1}^x y = \frac{x(x+1)}{2}$個あります。
これから、$x \geq t$を満たす(x,y,z)の組数は
$\sum_{x=1}^t \frac{x(x+1)}{2} = \frac{t(t+1)(2t+1)}{12} + \frac{t(t+1)}{4}$
個となります。これらを用い、x,y,zの順に二分探索で値を決めます。
計算量は$O((logN)^3)$です。

提出例: forループ, 二分探索3回

D Erase Leaves

問題文はこちら

解法
頂点1の部分木を、どれか1つを残して削除すれば頂点1が葉になり削除できます。
残すべき部分木は最もサイズが大きい部分木なので、結局「頂点1とつながる頂点のうち、最も部分木が大きいものはどれか？」という問題に帰着できました。
これはDFSやBFSで解けます。
DP[i]: 頂点1を親としたときの、頂点iの部分木の大きさ
として、帰りがけ順に処理を行えばよいです。計算量は$O(N)$です。
なおPyPy3だと再帰が遅いので、再帰用の「おまじない」が必要です。詳細は提出例をご確認ください。

ところで頂点1につながる辺を削除すると、UnionFindで部分木のサイズが取得できるようになるので簡潔な実装になります。
計算量は$O(Nα(N))$です。($α(N)$は逆アッカーマン関数: ほぼ定数)
提出例: BFS・DFS, UnionFind

E Takahashi Quest

問題文はこちら

解法
ポーションの所持数での二分探索を行いたくなりますが、最大値の決め打ちの判定がうまくできません。
ここはポーションを必要になるギリギリで拾うことにしましょう。正当性は、ざっくりと「必要になるポーションをあらかじめ拾っても、所持数上限を圧迫するだけなので不利」で説明ができます。
後は必要になるギリギリのポーションが高速に判定できればよいです。
クエリを前から見る場合、直近で見つけたポーションをスタックに入れておけば判定が可能です。

最後に$K_{min}$ですが、拾うポーションが決まれば愚直に実験しても$O(N)$で求まります。
おしゃれに答えるならimos法を使ってもよいでしょう。
提出例(stack・imos法)

F Bomb Game 2

問題文はこちら

解法
DPを行います。
DP[i][j]: 残りi人で、先頭からj番目のときの勝率
と定義します。初期化はDP[1][1] = 1、最後の1人は必勝です。
また、計算するのに都合がよいので、DP[x][0] = 0 としておきます。

iの昇順にDPを埋めます。
まずDP[i][1] (先頭の場合)を考えます。
最初の操作で、$\frac{1}{2}$の確率で爆発して敗北し、そうでなければ最後尾に移動します。
そうでない場合、さらに$\frac{1}{2}$の確率で次の人が爆発し、DP[i-1][i-1]に遷移します。
そうでない場合、さらに$\frac{1}{2}$の確率でその次が爆発し、DP[i-1][i-2]に遷移します。
これを繰り返すと、$\frac{1}{2^i}$の確率でまた先頭に戻ってきます。

今の確率を方程式に落とすと、このようになります。
暫定的に爆発して敗退する場合をDP[i-1][0] = 0 とみなします。

$DP[i][1] = \frac{1}{2} DP[i-1][0] + \frac{1}{4} DP[i-1][i-1] + ･･･ + \frac{1}{2^{i-1}} DP[i-1][2] + \frac{1}{2^i} DP[i][1]$
DP[i][1]を左辺に移すと
$\frac{1-2^i}{2^i} DP[i][1] = \frac{1}{2} DP[i-1][0] + \frac{1}{4} DP[i-1][i-1] + ･･･ + \frac{1}{2^{i}} DP[i-1][2]$
$=\sum_{x=1}^i \frac{1}{2^x} DP[i-1][(1-x)\%i] $
となります($\%$は余りを表します)。
右辺のDP[i-1]はすべて求まっているので、これでDP[i][1]が求まります。
ここまでの計算量は$O(N)$です。

その後の方針は2通りあります。

$O(N)$の高速化
たとえばDP[i][2]に対して上記の$O(N)$の式を立式すると
$\frac{1-2^i}{2^i} DP[i][2] = \frac{1}{2} DP[i-1][1] + \frac{1}{4} DP[i-1][0] + ･･･ + \frac{1}{2^{i}} DP[i-1][3]$
となります。
この計算には毎回$O(N)$かかるのですが、よく見るとDP[i][1]の式と非常によく似ていることに気づきます。
具体的には、DP[i][2]はDP[i][1]を$\frac{1}{2}$倍してから、DP[i-1][2]の項の係数が$\frac{1}{2}$になるように修正しただけです。
この差分更新ならば$O(1)$で行えます。DP[i][3], DP[i][4], ･･･も同様に処理すればよいです。
先頭の人の処理を見る
たとえばDP[i][2]の遷移を考えます。
先頭の人の処理を考えると、$\frac{1}{2}$の確率で爆発してDP[i-1][1]に遷移します。
爆発しなかった場合、一歩前に進むのでDP[i][1]に遷移します。
なので$DP[i][2] = \frac{1}{2} DP[i-1][1] + \frac{1}{2} DP[i][1]$と表せます。
これはどちらも求まっているので、結局$O(1)$で遷移計算が可能です。

どちらも合計の計算量は$O(N^2)$になります。
提出例: O(N)を高速化, 先頭を見る

G Nearest Fraction

問題文はこちら

解法
wikipediaを見ると、ファレイ数列という分数列がヒットします。

これを読むと、分数の中間数を取ることで既約分数が得られることが分かります。
つまり$\frac{A}{B} < \frac{A+C}{B+D} < \frac{B}{D}$で得た中間数、$\frac{A+C}{B+D} $は既約分数です。
この性質を使うと、中間数を挿入し続けるだけで小数の近似ができそうです。

TLE解法
まず、Rは分数に変換しましょう。
以降、$R = \frac{R_T}{R_B}$とします(Top, BottomのT,Bです)。

明らかに、$R_B \leq N$ならばこれが答えです。
以降はそうでない場合、すなわちRの近似を探す場合を考えます。

現在のRの近似を$L,U = \frac{L_T}{L_B}, \frac{U_T}{U_B}$とします。
ただし、$L<R<U$です(Lower, UpperのL,Rです)。初期値は$L,U = \frac{0}{1}, \frac{1}{1}$です。
中間数midは$\frac{L_T + U_T}{L_B + U_B}$で得られるので、これで下界か上界を更新します。
$L<mid<R$なら$L ← mid = \frac{L_T + U_T}{L_B + U_B}$で
$R<mid<U$なら$U ← mid = \frac{L_T + U_T}{L_B + U_B}$で、それぞれ更新します。
分母がNを超えたら近似を打ち切り、答えを出力すればよいです。

AC解法
上記の方法は大抵のケースでACできますが、コーナーケースが存在します。

sample input (sample output: 1 10_000_000_000)

0.00000000006
10000000000

このケースでは、計算量が$O(N)$となってしまいTLEします。
実際の処理を見てみましょう。

$L,U = \frac{0}{1}, \frac{1}{1}, mid = \frac{1}{2}$となる。$R<mid<U$なので$U ← mid$
$L,U = \frac{0}{1}, \frac{1}{2}, mid = \frac{1}{3}$となる。$R<mid<U$なので$U ← mid$
$L,U = \frac{0}{1}, \frac{1}{3}, mid = \frac{1}{4}$となる。$R<mid<U$なので$U ← mid$
$L,U = \frac{0}{1}, \frac{1}{4}, mid = \frac{1}{5}$となる。$R<mid<U$なので$U ← mid$

･･･

N-1. $L,U = \frac{0}{1}, \frac{1}{N-1}, mid = \frac{1}{N}$となる。$R<mid<U$なので$U ← mid$
N. $L,U = \frac{0}{1}, \frac{1}{N}, mid = \frac{1}{N+1}$となる。分母がNを超えたので終了。

以上の処理を見ると、近似の下界か上界が変わらない場合に似たような計算が連続し、重くなっていることが分かります。
ここを高速化しましょう。

中間数とRの大小関係が変わらない(下界か上界が変わらない)場合、中間数の更新をまとめて行えます。
1ステップ目の下界と上界を$L,U = \frac{L_T}{L_B}, \frac{U_T}{U_B}$とすると、$x$ステップ目は

mid = \left\{
\begin{array}{ll}
\frac{L_T + x U_T}{L_B + x U_B} & (L < mid < R) \\
\frac{x L_T + U_T}{x L_B + U_B} & (R < mid < U)
\end{array}
\right.

となります。この$x$は二分探索を行えば$O(logN)$で求めることができます。

二分探索の回数を評価します。
二分探索は中間数の下界と上界が変わるたびに行われ、初回更新を除くと分母の値が小さい方が更新されます。
つまり、$min(L_B, U_B) ← L_B + U_B + α$ です。
$L_B$と$U_B$の値は交互に更新されることを考えると、n回目の更新ではフィボナッチ数の第n項以上の値を取ることになります。
フィボナッチ数は約50項目に$max(N) = 10^{10}$を迎えるため、二分探索は高々50回程度しか行われないとわかります。
本問の制約下で、この計算量は十分高速です。
提出例

おわりに

おわりです。
このかいであおいろになれて、とてもうれしかったです。

ABC333 勉強メモ

公式解説

A～B

C Repunit Trio

D Erase Leaves

E Takahashi Quest

F Bomb Game 2

G Nearest Fraction

おわりに