アルゴリズム忘備録

競技プログラミングとかデータ分析とか

M-SOLUTIONS プロコンオープン C - Best-of-(2n-1)

atcoder.jp

 

なんとかこういう問題の本質がわかった気がする。

 

まず状態遷移を考えると、今までにAがi回勝って、Bがj回勝った、という状態をS(i, j) とおく。これに引き分けがk回あった、という状態を考えてしまうと引き分けは永遠に続くことがあるので、状態の数が無限個になってしまい考えにくい。そのためAとBの勝数だけで状態を作る。

 

すると、 S(i,j) へ遷移する可能性があるのは、S(i-1, j) (Aが勝った), S(i, j-1) (Bが勝った), S(i, j) (引き分け) となる。これが難しいところは同じ状態に戻ってくる遷移がある、つまり状態遷移がDAGではないためDP等ができないところにある。そのため、普通に計算すると無限級数の計算が必要になる。

 

そこで、この状態遷移を期待値E[i, j] の遷移と捉え、E[i - 1, j] または E[i, j - 1] からの遷移のみで記述できないか、という考察をする(これが最も重要)。これが達成できると期待値の遷移がDAGとなり、少なくともDPで計算できる。

 

これは、E[i, j] から引き分けが続き 次のステートへ進む回数の期待値を計算すればよい。これは引き分けの確率をcとする時、(1/1-c) となる。漸化式を用いて証明もできるが(次のステートに進む回数の期待値をeとおくと、 e = (e-(1-c)(1-e) + (1-c) より) 要は大体1/(1-c) 回投げると1回勝ちか負けかにはなる、という感じである。

 

というわけで状態遷移のコストを1/(1-c)倍したDAGができたのでこれをDPとして解けばよい。今回はdpにすらする必要はなく、AまたはBがn-1回勝って、他方がn-1回以下勝って、次のAまたはBが勝ち、n回勝利確定、という期待値を計算し、全体を1/(1-c)倍すればよい。計算量はこの他方の勝数のループのところでO(N)。

 

ちなみに具体的に無限級数の式を書き下すと、この程度ならWolfram Alphaで計算できるらしい。OEISとともに覚えておきたい。