ABC298E "Unfair Sugoroku"をRubyで解く
Unratedにならなけりゃ入水出来てたんだよなぁ(憤怒)
今回の問題はこちらです。
アドホック部
「勝つ」を計算可能なものに言い換える。
求めるのは「高橋くんが勝つ」確率です。これは「青木くんが地点Nに着いたターンまでに、高橋くんがゴール済みの確率」と言い換えられます。
(逆に高橋くんがゴールした時点でまだ青木くんが未ゴールの確率とする方が自然かもしれませんが、本番中に思いつきませんでした。)
つまり「青木くんが1ターン目にゴールする確率」×「高橋くんが1ターンでゴールする確率」
+「青木くんが2ターン目にゴールする確率」× 「高橋くんが2ターン以内にゴールする確率」
+「青木くんが3ターン目にゴールする確率」× 「高橋くんが3ターン以内にゴールする確率」
...
+「青木くんが1の目を出しまくって(Q - B)ターンかかった最遅パターンを引く確率」× 「高橋くんが(Q - B)ターン以内にゴールする確率」
の合計が答えです。
では何ターン目にゴールする確率はそれぞれいくらか?
これは蛙飛び系の確率DPです。
「現在iターン目です。jマス目にいる確率がズラッと配列に入っています。じゃあi+1ターン目にそれぞれのマスにいる確率を計算してズラッと配列に入れてね」というアレです。
類題はこちら
最終的にN以上のマスに飛んでしまうパターンがある場合、それらの確率を合計して「turn_i目にゴールした確率」として配列に入れ、最終的にまとめて返します。
青木くんの方はこの配列を直接使ってOKなのですが、高橋くんは「iターン目にゴールした確率」ではなく「iターン目までにゴールした確率」が欲しいので累積和を取ります。
あとは「青木くんが1ターン目にゴールする確率」×「高橋くんが1ターンでゴールする確率」
+「青木くんが2ターン目にゴールする確率」× 「高橋くんが2ターン以内にゴールする確率」
...
+「青木くんが1の目を出しまくって(Q - B)ターンかかった最遅パターンを引く確率」× 「高橋くんが(Q - B)ターン以内にゴールする確率」
を合計するだけです。
擬似コード
- 関数で高橋くんのスタート位置とダイスの面数を引数で受け取ります。ゴール位置は定数で読めるので引数で受ける必要はありません。
- ダイス面数の逆元を算出します。
- 蛙飛びDPを始めます。(N-1)マス目以前に存在する確率がなくなった場合はつまり100%ゴールしているという事なので終了します。
- 旧DPを全部見て、マスに確率が入っている場合は旧確率×ダイス面数逆元で新確率を出します。旧マス+1マス目から旧マス+ダイス面数まで全部に新確率を足します。
- 新DP配列がNより長くなった場合、つまりN以降に到達してゴールした場合は確率を合計して配列に代入します。この配列はindexがターン数,値がゴール確率です。
- 新DP配列のうちN-1以下の部分を切り出し、3に戻ります。
- 高橋君が何ターン目にゴールする確率がいくらかの配列が得られるので、累積和を取ります。indexが何ターン目までか、値がゴールする確率を配列が出ます。
- 1~6と同じことを青木君のスタート位置、青木君のダイス面数で行います。青木君が何ターン目にゴールする確率がいくらかの配列が得られます。
- 「高橋君がiターン目以前にゴールする確率」×「青木君がiターン目ちょうどにゴールする確率」を全てのiについてループで合計します。
提出コード
提出コードのProbArray関数が擬似コードの1~6の部分です。
9行目でダイス面数の逆元を出しています。筆者は全ての理解を諦めてOpenSSLライブラリに甘えていますが、良い子のみんなはきちんとフェルマーの最終定理……じゃなくてフェルマーの小定理を勉強してね！
14行目からDPループです。any?は全ての値がfalsyならfalse,値が一個でもtrulyならtrueを返します。
22行目で初期値0を代入し、23行目で新確率を足しています。これ毎回掛け算せずに小ループの外でキャッシュすればもうちょっと早かったやろ？
26行目でゴール確率を算出し、戻り値の配列に書き込んでいます。
28行目でdp配列の未ゴール部分を切り出してループします。
これで得られた配列を35~37行目で累積和にしています。
39行目で青木君に対しても同じ事をやります。
40行目以降で最終的に確率を掛けて合計します。青木君の方の配列でループしているので高橋君の配列が足りなくなる(ゴール済み)ことがあり、その場合は高橋君の配列の最後を見ます。1に決まってるんだからいちいち配列末尾見なくても1でええやんけ。
おまけ
せやな……
Discussion