今回は ABCDEF の 6 完(71:37)。 確率の問題をしっかり解けたのは大きかったが、全体的に思考があやふやになってて E までに時間を掛けすぎた気がする。
横着しようとして、stringのコンストラクタを使おうと思ったが、なぜか答えがでなかった。
環状にしたときの距離が等しければいいのでなんかうまく実装する。
具体的な解法が全然浮かばなかったので、出力例から察して 3 重ループを回して sort, unique をした。
頂点 $1$ の子の部分木において、ある子以外の部分木を取り除く必要があるので、 部分木のサイズが一番大きい子を残しておけば良い。 変に曲解して時間を使った。
ポーションはできるだけ後ろで拾いたいのでクエリを後ろから見て、どのポーションを使えばいいかを 考える。そうすればでてくるのであとはシミュレーションする。
まず先頭の確率のみを考える。この時逆に列から抜けるときの確率を考える。
$P(1, n)$ ... 現在 $n$ 人いるとき、人 $1$ が列から抜けられる確率というものを考える。
この時、このような式になる。
$$P(1, n) = \frac{1}{2} + \frac{1}{2^n} \sum_{i=0}^{n-2} \binom{n-1}{i} P(1, n-i)$$
これは遷移時に $1$ 周回ってきて何人になったかといったような式になっている。
例によって重複部分を取り除くと、
$$P(1, n) = \frac{1}{2^n} P(1, n) + \frac{1}{2} + \frac{1}{2^n} \sum_{i=1}^{n-2} \binom{n-1}{i} P(1, n-i)$$
$$\frac{2^n - 1}{2^n} P(1, n) = \frac{1}{2} + \frac{1}{2^n} \sum_{i=1}^{n-2} \binom{n-1}{i} P(1, n-i)$$
$$P(1, n) = \frac{2^{n-1} + \frac{1}{2^n} \sum_{i=1}^{n-2} \binom{n-1}{i} P(1, n-i)}{2^n-1}$$
となり、求められる式となる。これを求めるには $O(N^2)$ である。
では他の $P(i, n)$ についてはどうやって求めればいいかと言うと、実は $P(1, n)$ の答えが再利用できる。 どうするかと言うと、$i$ に先頭が回ってくるときのことを考えるのである。すると 人 $1$ のときの答えと同じになるので 答えが再利用できるというわけだ。 そしてこれは、 $$P(i, n) = \frac{1}{2^{i-1}} \sum_{j=0}^{n-2} \binom{i-1}{j} P(1, n-j)$$ によって出てくる。つまり先頭に回ってくる前に何人に減っているかということである。
このように $i (\geq 2)$ についての答えもそれぞれ $O(N)$ で求まることから全体で $O(N^2)$ で求めることができる。
うーん、 $O(N)$ 解を定数倍を早くすれば通るかなと思ったが、そもそも誤差の問題とかがありそうでヤバそう。 多分分数の大小関係を利用して解くのだと思うが、調べたところファレイ数列とかが関係ありそうな気がする。 ファレイ数列の $F_n$ を覗いてうまく二分探索できないかなー。
F みたいな問題は昔はおそらく通せなかっただろうから、通せるようになって嬉しい。 ただ、なんか今日はテンパっていたのでもうちょっと早く通せたかなと思った。 今日で黄色になるぞーって変にテンパったのかもしれない。。。 明日は AGC・・・
(2023/12/16 23:07)