問題
$N$ 本目の傘を購入して、最後の移動を行った時点でゲーム終了とします。
制約
・確率 $0 < p < 1$，小数．
・$0 < N < 10^5$，整数．
ツイートでは $p$ パーセント（$p$ は整数）としていましたが、解説で無駄な $\frac{1}{100}$ 倍が入るだけなので小数とします。ただし，$p$ が極端に $0$ や $1$ に近いと答が巨大になりすぎるため、$0.01 \leqq p \leqq 0.99$ くらいの制約にしておいた方が適切な出題かと思います。
出力
移動回数の期待値を小数で出力せよ．
なお、$p$ が有理数であれば解も有理数で，適当な$\pmod{p}$で求めることもできます。
入力例・出力例
【入力例】$N = 1$, $p = 0.5$
【出力例】2.0
$N = 1$ のときは最初に雨と出くわすまでの回数の期待値で、$1/p$ が答となります。
【入力例】$N = 10$, $p = 0.3$
【出力例】247.61904761904762
解答
データの持ち方・乱数シミュレーション
2地点間の往復ですが，これら2地点は区別の必要がありません。
・現在地に置かれている傘の数
・反対側に置かれている傘の数
がわかれば、その後の状態をシミュレーションすることができます。
以下では、状態 $(a,b)$ といえば、現在地に傘が $a$ 本あり、反対側に傘が $b$ 本ある状態を示すこととします。例えば $N = 10$ として、乱数シミュレーションしてみましょう。
確率・期待値の計算をする場合、それほど精度を求めていないのであれば、シミュレーションによる計算は非常に手軽です。実装も手軽で計算ミスもしづらいですね。競技プログラミングの文脈以外で確率や期待値を扱う場合は、これで済む場合も多いと思います。また、厳密値を計算しなければいけない場合でも、シミュレーションが手短に出来る場合は一度実装しておくと、検算に利用することができます。
問題の分割
傘を購入した直後の状態は必ず等しいです。
したがって、計算すべき期待値は、次のように分割できます。
・$a = n$, $b = 0$ の状態から始めるとする。$(a,b) = (n+1,0)$ になるまでの回数の期待値を$E_n$ と表すこととする。
・答は、$\sum_{k=0}^{N-1}E_k$ と表すことができる。
したがって以下では主として、$n$ 本の傘を持っているときに、$n+1$ 本目の傘を購入するまでに何回かかるのかを考えていきます。
マルコフ過程・連立方程式を作る
仮に、現在傘を $3$ 本目まで購入しているとしましょう。このとき、 $(a,b)$ としては$(0,3)$, $(1,2)$, $(2,0)$, $(3,0)$ の4通りの状態があります。また、ある状態からの遷移はその状態に至るまでの過程とは全く独立です。このような確率過程は マルコフ過程 と呼ばれ、
・（終了状態が存在しない場合）十分なターン数経過後の確率分布
・（終了状態が存在する場合）終了までの時間の期待値
などは、典型的な問題です。本問題も、完全にこの形に当てはまります。専門用語が登場しましたが、専門的で難解な公式が必要というよりは、ごく自然な考え方で解くことができます。
状態が$(0,3)$, $(1,2)$, $(2,1)$, $(3,0)$ とありますが、簡単のため
・$a_0$：状態 $(0,3)$ からスタートしたとき，$4$ 本目の傘を購入するまでの移動回数の期待値。
・$a_1$：状態 $(1,2)$ からスタートしたとき，（以下同様）
・$a_2$：状態 $(2,1)$ からスタートしたとき，（以下同様）
・$a_3$：状態 $(3,0)$ からスタートしたとき，（以下同様）
と表すこととします。（なお、$4$ 本目を購入したときの移動も回数に含めておきます）
例えば、$a_0$ は次のように場合分けして計算することができます。
・初手に雨が降っていた場合：確率は $p$ である。1回で傘が増える。
・初手に雨が降っていない場合：確率は $q = 1-p$ である。1回移動した後、状態 $(3,0)$ に遷移する。したがって、期待値 $1 + a_3$ の回数で傘が増える。
※ 以下、$q = 1-p$ と書きます。
ここから、次のような式を作ることができます：
\[a_0 = p\cdot 1 + q \cdot \bigl(1 + a_3\bigr) = qa_3 + 1.\] 同様の考察を$a_1$, $a_2$, $a_3$ に対して行うと，次の形になります：
\[\begin{align*}
a_0 &= && && && qa_3+ && 1,\\
a_1 &= && &&qa_2+ &&pa_3+ && 1,\\
a_2 &= && qa_1+ &&pa_2+ && && 1,\\
a_3 &= qa_0+&&pa_1+ && && && 1.
\end{align*}\]移行すれば，
\[
\begin{pmatrix}
1 & 0 & 0 & -q\\
0 & 1 & -q & -p\\
0 & -q & 1-p & 0\\
-q & -p & 0 & 1
\end{pmatrix}
\begin{pmatrix}
a_0 \\ a_1 \\ a_2 \\ a_3
\end{pmatrix} =
\begin{pmatrix}
1 \\ 1 \\ 1 \\ 1
\end{pmatrix}\] という形になって、連立方程式を解くことで $a_0$, $a_1$, $a_2$, $a_3$ を計算することができます。特に $a_3$ の値が、$3$ 本目の傘から $4$ 本目の傘までの回数の期待値です。
このコードで、小さな $N$ については十分高い精度で答を出すことができます。ただ，この実装だと巨大な $N$ については計算時間，の以前にメモリが足りません。$N\times N$ 行列は，定義しただけでも $N^2$ 個の値を格納するので。この問題は行列を疎行列にすることで対処できます。
母関数の利用
傘が $n$ 本の状態を考え、同様に $a_0,\ldots,a_n$ を定めます。連立方程式の解を厳密に決定しましょう。元の問題のままでは $a_k$ が $a_{n-k}$ や $a_{n-k+1}$ を用いて表されるという，少しややこしい規則です。（このまま解く方法もあるかもしれませんが）
1回の移動ではなく，2回の移動を考えることで，連立方程式を作ります。例えば，状態 $(1,2)$ からの遷移を考えます。
・雨、雨となる：確率は $p^2$。2回の移動の後に状態 $(1,2)$ に戻る。
・晴、晴となる：確率は $q^2$。2回の移動の後に状態 $(1,2)$ に戻る。
・雨、晴となる：確率は $pq$。2回の移動の後に状態 $(2,1)$ に遷移する。
・晴、雨となる：確率は $pq$。2回の移動の後に状態 $(0,3)$ に遷移する。
したがって上述の記号で
\[ a_1 = 2 + (p^2 + q^2) a_1 + pq a_2 + pqa_0\] という式を作ることができます。また状態 $(0,3)$ からスタートすると、確率 $p$ で1回の移動で終了です。この辺も考慮して次のような方程式が得られます。
\[\begin{align*}
a_0 &= q^2a_0+&&pqa_1+ && && && (1+q),\\
a_1 &= pqa_0+&&(p^2+q^2)a_1+&&pqa_2+ &&&& 2,\\
a_2 &= && pqa_1+ &&(p^2+q^2)a_2+ &&pqa_3+ && 2,\\
a_3 &= &&&&pqa_2+&& (p^2+q^2)a_3+&& 2.
\end{align*}\] この例では $n = 3$ としていますが、$n$ がとても大きいときを考えると、式の大半が
\[ a_k = pqa_{k-1} + (p^2+q^2)a_k + pqa_{k+1} + 2\] と書けていることが分かります。便宜上 $a_{n+1} = 0$ とおけば，この式が$1\leqq k\leqq n$ で成り立ちます。このような式の集まりは，数列の母関数を考えると簡潔に表すことができます。
$f(x) = a_0 + a_1x + a_2 x^2 + \cdots + a_nx^n$ とおき、このように数列の値を係数に並べた多項式を母関数と呼びます（無限数列ならば、多項式を無限に続けた形式的べき級数になります。）
$1 – p^2 – q^2 = 2pq$ なので上の式は $a_{k-1} – 2a_k + a_{k-1} = \frac{-2}{pq}$ と表すことが出来ます。そこで、$g(x) = (x^2 – 2x + 1)f(x)$ を考えましょう。$g(x)$ における $x^{k+1}$ の係数は $a_{k-1} – 2a_k + a_{k+1} = \frac{-2}{pq}$ になります。 したがって、$g(x)$ はほとんどの係数が $\frac{-2}{pq}$ です。このことから、$g(x)$ と $\frac{-2}{pq}\cdot\frac{1-x^{n+2}}{1-x}$ がほとんど常に同じ係数を持つことを示しています。
「ほとんど常に」の部分をきちんとやってあげる ($1\leqq k\leqq n$に対して$x^{k+1}$ の係数が一致するのでした）と、
\[ g(x) = \frac{-2}{pq}\cdot \frac{1-x^{n+2}}{1-x} + \text{（1次式）}\] という形で表すことができると分かります。$n+2$ 次以上の項をまとめて$O(x^{n+2})$と表します。形式的冪級数になりますが、
\[ (1-x)^2f(x) = \frac{-2}{pq}\cdot \frac{1}{1-x} + \text{（1次式）} + O(x^{n+2})\] より
\[\begin{align*} f(x) &= \frac{-2}{pq}\cdot \frac{1}{(1-x)^3} + \frac{\text{（1次式）}}{(1-x)^2} + O(x^{n+2})\\
&= \frac{-2}{pq}\cdot \frac{1}{(1-x)^3} + \frac{\text{（定数）}}{(1-x)^2} + \frac{\text{（定数）}}{1-x} + O(x^{n+2})\end{align*}\] と書けます。
\[\begin{align*}
\frac{1}{1-x} &= 1 + x + x^2 + x^3 + x^4 + x^5 + \cdots &&= \sum_{k=0}^{\infty}x^k,\\
\frac{1}{(1-x)^2} &= 1 + 2x + 3x^2 + 4x^3 + 5x^4 + 6x^5 + \cdots &&= \sum_{k=0}^{\infty}(k+1)x^k,\\
\frac{1}{(1-x)^3} &= 1 + 3x + 6x^2 + 10x^3 + 15x^4 + 21x^5 + \cdots &&= \sum_{k=0}^{\infty}\frac{(k+2)(k+1)}{2}x^k\end{align*}
\] となることから，ある定数 $c_1, c_0$ が存在して $f(x)$の$x^k$の係数（$k\leqq n+1$）は
\[a_k = -\frac{1}{pq}k^2 + c_1k + c_0\] と書けることが分かります。
この時点で、連立方程式の規則的な部分は達せられるので、境界の規則に外れた部分から$c_1$, $c_0$ を決定します。$a_0 = q^2a_0 + pqa_1 + (1+q)$, $a_{n+1} = 0$ から $c_1$, $c_0$ を計算すると，最終的に
\[ a_k = \frac{1}{pq}\bigl((n+1)-k\bigr)(k+q)\] が成り立つことが分かります。特に $a_n = \frac{n+q}{pq}$ となります。この値が $E_n$ です。
最終版
あはは…もはや競技「プログラミング」でやる必要なし。これで $O(N)$ ですが、これはただの等差数列の和ですので、もちろん $O(1)$ になります。傘が $N$ 本になるまでの回数の期待値は $\frac{N(N+2q-1)}{2pq}$ ということになりますね。
類題など
最後の母関数を使った解析はともかくとして、マルコフ過程の期待値を連立方程式から調べる手法は競技プログラミングでもたまにある問題かと思われます。
有名題
最も簡単なのは次のようなタイプです：
（問）サイコロを何回も投げる。はじめて「6」の目が出るまでに投げる回数の期待値を求めよ．
（解答）期待値を $x$ とする。1回投げると、$5/6$ の確率で初期状態に遷移、$1/6$ の確率で終了するので、$x = 1 + \frac{5}{6} x$ が成り立つ。よって $x = 6$である。
なお、期待値の定義にしたがって $\sum_{k=0}^{\infty} kp_k$ を計算する方法もありますが、上の解答よりは複雑になります。
Atcoder
・ARC 016-C ソーシャルゲーム
遷移状態の表現の実装が少しややこしいですが、原理的には上のサイコロ問題と同様です。遷移に非自明なループがないならば、連立方程式を解く必要はないです。
Project Euler
・[084] Monopoly Odds
・[227] The Chase
・[280] Ant and seeds
・[481] Chef Showdown
・[497] Drunken Tower of Hanoi
いかにもマルコフ過程に関する問題になっているものを適当にリストアップ。
遷移が分かりやすい（いかにも状態が整数1つで書ける）のは 227, 497 あたり。ただし 497 は数が超巨大なので何らかの明示公式を求めないと厳しい。他のやつは、状態の記述がやや手間です。
モノポリー（084）は、リアルにあるゲームが題材。回数期待値ではなく定常分布の計算ですが、同様に連立方程式を作ることを考えてみてください。いかにも実装がしんどそうですが、いざ書くとそうでもないです。
