はじめに
「WA_TLE's Bless」writerのKowerKointです。
ゲーム形式にすることで少しひねった期待値DPの行列累乗問題でしたが、正しく行列を構築できたでしょうか。
解法
DPを定義する
状態が順に遷移して、状態に紐付けられたスコアを求める問題なので、動的計画法を考えるのが自然です。
$i$回サイコロが振られたあと、次にサイコロを振るプレイヤーをA、そうでない方をBとしたとき、BがAの$j$マス($0\leq j<N$)マス先にいるとし、AにWA_TLEが宿っているとき$k=1$、ついていないとき$k=0$とすると、状態は$(i,j,k)$の組で表されます。
BのAに対する相対的な位置さえわかれば円の中にどこにいるかは区別しなくても問題ありません。
このような状態にある確率をp[i][j][k]、その時の「Aのレーティング - Bのレーティング」の期待値をe[i][j][k]としておきます。
状態$(i,j,k)$から、Aが出したサイコロの目を$x$であるときの次の状態を$(i+1,j',k')$とすると、
j'=\{N-(j+k)\}\bmod N \\
k'=(\lfloor\dfrac{j+k}{2}\rfloor+1)\bmod 2
というようになります。
このとき、
p[i+1][j'][k']+=p[i][j][k]*(1/M)
e[i+1][j'][k']+=-(e[i][j][k]+j'*p[i][j][k])*(1/M)
というようにDPが遷移します(上記は疑似コードです)。
$O(NMK)$のDPが構築されました。
行列累乗に落とす
上で示したDPは、回数$i$によらない遷移であることから行列累乗を行うことができます。
$i$回の遷移で$(j,k)$状態から$(j',k')$に遷移する確率を$P_i[j][k][j'][k']$として
を$i$回の遷移での「次にサイコロを振るプレイヤーのレーティング - そうでないプレイヤーのレーティング」の増加量の期待値のうち、$(j,k)$状態から$(j',k')$に遷移する場合の占める部分を$E_i[j][k][j'][k']$として$2N\times2N$行列$P_i$、$E_i$を定義します。
$P_i$は線形性を持っていて、
P_{i_1+i_2}[j][k][j''][k'']=\sum_{(j',k')}P_{ i_1}[j][k][j'][k']\cdot P_{i_2}[j'][k'][j''][k'']
が成り立ちます。
これを行列積とみなしてダブリングによる高速計算を行うのが通常の行列累乗のセオリーでした。
実は、無理に行列積の形に落とせなくても似たようなダブリングは可能なことがあります。
$E_i$については
E_{i_1+i_2}[j][k][j''][k'']=\sum_{(j',k')}\{(-1)^{i_1}P_{i_1}[j][k][j'][k']E_{i_2}[j'][k'][j][k]+(-1)^{i_2}E_{i_1}[j][k][j'][k']P_{i_2}[j'][k'][j''][k'']\}
と書けます。
以上でダブリングを行えば、行列累乗と本質的に変わらないアルゴリズムが実践でき、計算量は行列の作成に$O(N^2+NM)$時間、行列累乗の実践に$O(N^3\log{K})$時間の合わせて$O(NM+N^3\log{K})$時間となります。
なお、確率と期待値を両方とも行列の成分に持った$4N\times 4N$の行列を用意して通常の行列累乗で計算することもできます(実はwriter解はこっち)。