公式

C - Final Exam 解説 by E869120 印刷ページ


ステップ 1

まず、本問題は、下図のようなグリッドで \(0\) 段目から \(n\) 段目に移動するとき、\((n, 正の値)\) にたどり着く確率を求める問題と等価です。たとえば \(n=4\) の場合、\(0\) 段目から \(4\) 段目に移動する際、最終的に \((4, 2)\) または \((4, 4)\) にたどり着く確率を求める問題と等価です。

そのため、本問題は単純な動的計画法によって計算量 \(O(N^2)\) で解くことができます。しかし、本問題の制約は \(N \leq 10\,000\,000\) と非常に大きいため、残念ながら TLE となってしまいます。

そこで小さい \(n\) で実験をして、以下のような考察を得ます。(対称性を使うと証明できます)

  • \(n\) が奇数のとき: \((n, 正の値)\) に移動する確率は \(1/3\)
  • \(n\) が偶数のとき: \((n, 正の値)\) に移動する確率は \((n, 負の値)\) に移動する確率の \(1/2\) 倍

この考察を使うと、\(n\) が奇数の場合に \(f(n)\) の値を計算することができ、また \(n\) が偶数の場合も、\((n, 0)\) に移動する確率さえ求まれば \(f(n)\) の値を計算することができます。問題は、\((n, 0)\) に移動する確率をどう求めるかです。



ステップ 2

(以下、\(n\) が偶数であることを仮定します)

そこで、下図において青で示したような、\((2k, 0)\) から \((2k+1, -1)\) へ移動する辺に着目します。

このとき、\((0, 0)\) から \((n, 0)\) へ移動する経路のうち、青の辺を \(t\) 本通るものは、必ず確率 \(2/3\) の辺を \(n/2+t\) 本、確率 \(1/3\) の辺を \(n/2-t\) 本通ります。たとえば \(n=6\) のとき、以下が成り立ちます。

  • 青の辺を \(0\) 本通る経路では、確率 \(2/3\) の辺を \(3\) 本、確率 \(1/3\) の辺を \(3\) 本通る
  • 青の辺を \(1\) 本通る経路では、確率 \(2/3\) の辺を \(4\) 本、確率 \(1/3\) の辺を \(2\) 本通る
  • 青の辺を \(2\) 本通る経路では、確率 \(2/3\) の辺を \(5\) 本、確率 \(1/3\) の辺を \(1\) 本通る
  • 青の辺を \(3\) 本通る経路では、確率 \(2/3\) の辺を \(6\) 本、確率 \(1/3\) の辺を \(0\) 本通る

したがって、\((0, 0)\) から \((n, 0)\) へ青の辺を \(t\) 回通って移動する経路の数を \(p_t\) とするとき、求める「\((n, 0)\) に移動する確率」は以下の式で表されます。

\[ \sum_{0 \leq i \leq n/2} \left( p_i \times \left( \frac{2}{3} \right)^{n/2+i} \times \left( \frac{1}{3} \right)^{n/2-i} \right) \]

さらに、\(p_0, p_1, p_2, \cdots, p_{n/2}\) は単純な二項係数の引き算で表され、具体的には \(p_t = {}_{n}\mathrm{C}_{n/2+t} - {}_{n}\mathrm{C}_{n/2+t+1}\) となります。したがって、「\((n, 0)\) に移動する確率」は

\[ \sum_{0 \leq i \leq n/2} \left( \left({}_{n}\mathrm{C}_{n/2+i} - {}_{n}\mathrm{C}_{n/2+i+1} \right) \times \left( \frac{2}{3} \right)^{n/2+i} \times \left( \frac{1}{3} \right)^{n/2-i} \right) \]

となり、各 \(n\) につき \(O(n)\) で答えが分かります。しかしながら、本問題では \(n=1, 2, \dots, N\) すべてについて答えを求める必要があるため、まだ TLE となってしまいます。



ステップ 3

ステップ 2 の最後の式をさらに分かりやすくしてみましょう。以下のようになります。

\[ \left( \frac{1}{3} \right)^n \times \sum_{0 \leq i \leq n/2} \left({}_{n}\mathrm{C}_{n/2+i} \times 2^i\right) - \left({}_{n}\mathrm{C}_{n/2+i+1} \times 2^i\right) \]

シグマの外側の項を除くと、本質的には以下の \(2\) つの関数に対し、\(g(n) - h(n)\) を計算すればよいことが分かります。

  • \(g(n) = \sum_{0 \leq i \leq n/2} \left( {}_{n}\mathrm{C}_{n/2+i} \times 2^{n/2+i} \right)\)
  • \(h(n) = \sum_{0 \leq i \leq n/2} \left( {}_{n}\mathrm{C}_{n/2+i+1} \times 2^{n/2+i} \right)\)

を計算すればよいことが分かります。そこで \(g(n)\) の値を使うと、\(g(n+2)\) の値は以下の漸化式により計算することができます。

\[ g(n+2) = 9g(n) - 2^{n/2}{}_{n}\mathrm{C}_{n/2} + 2^{n/2+1}{}_{n}\mathrm{C}_{n/2-1} \]

同様に、\(h(n)\) の値を使うと、\(h(n+2)\) の値は以下の漸化式により計算することができます。

\[ h(n+2) = 9h(n) - 2^{n/2}{}_{n}\mathrm{C}_{n/2+1} + 2^{n/2+1}{}_{n}\mathrm{C}_{n/2} \]

そこで漸化式を使って \(g(n), h(n)\) を計算すると、\(k!\) や \(1/k!\) などの値の適切な前計算により、計算量 \(O(N)\) で \(n = 2, 4, 6, \dots, N\) すべてに対して「\((n, 0)\) へ移動する確率」を求めることができます。これでようやく、本問題が解けました。



実装例 (C++)

投稿日時:
最終更新: