Typical DP Contest：C - トーナメント

問題

https://atcoder.jp/contests/tdpc/tasks/tdpc_tournament

考え方

i が優勝するときは K 連勝する必要がある。以下のようにDPを定義する。

dp[i][j] := i が j 連勝するときの確率

i がj 連勝するときは、i が j-1 連勝する確率に、対戦相手 k が j-1 連勝して、 i が k に勝つ場合であるから以下のようなDP遷移を考えることができる。

\displaystyle dp[i][j]=dp[i][j-1] \cdot \sum_{k\in S}dp[k][j-1]\cdot \Pr{(i, k)}
\Pr(i,\ k) は i が k に勝つ確率

DP初期値としては、0 連勝は常に可能と考えて以下のようになる。

dp[i][0] = 1.0

各 i について、j 連勝するときに戦う候補となる相手 k\in S について考える。例として以下のような K=4 のトーナメントを考えよう。相手のみを考察するのでレートは省略する。

今 i=13,\ K=3 の場合に戦う相手の候補は以下となる。これは i=13(1101) の k=3(0-indexed) ビット目以降が同じ数のうち、k=2 ビット目が異なる数である。

f:id:d_tutuz:20190103120545p:plain

i=13,\ K=4 の場合も同様である。

f:id:d_tutuz:20190103120921p:plain

Submission #3919742 - Typical DP Contest

どこに着目して考察するべきだったか

i が j 連勝するときの確率と捉えるとDPが見えてくるかもしれない。また戦う相手の候補は「bitで考えて上位bitが同じ数のうち、j-1 ビット目が異なる数」と考えるのは少しテクニックが必要な気がする。bitの性質を捉えて同じbitが同じグループに属する数はなにか？と考えると良いかもしれない。

何がバグっていたか

得た知見

  • 確率DPの定義方法(一例)
  • ビットで候補を計算する考え方と実装方法。>>と<<を組み合わせる

類題