う〜ん・・・う〜ん・・・
栄子、さっきから何を唸っているでゲソ？
ああ、イカ娘。さっきからこの問題に挑戦しているんだが全く分からなくてな・・・
え〜と、なになに・・・
なーんだ、典型的なDP(動的計画法)じゃなイカ！しかも、割と簡単な部類に入ると思うでゲソよ？
DPってことは割と直感で分かったんだが、どういう風に更新式を立てればいいのか分からないんだよ・・・
i個目の道で踏んでいる泥の数の期待値を出せばいいんじゃないかとか、色々考えたんだけど・・・
う〜ん、難しく考えすぎじゃなイカ？
ひとつヒントをあげるでゲソ。この問題の目的は期待値を求めることでゲソ。栄子、そもそも期待値とはなんだったでゲソ？
期待値ってそりゃあ、確率変数とそれが起こる確率を掛けあわせて足したものだけど・・・
なんだ、分かってるじゃなイカ！それじゃ、この問題は期待値の求め方からこのように分解できるでゲソ。これはごく自然なアプローチじゃなイカ。
(求める値) = 0 × (泥を0個踏む確率) + 1 × (泥を1個踏む確率) + ... + n × (泥をn個踏む確率)
つまり、最後まで到達したとき、泥を1〜n個踏んでいる確率がそれぞれ求まればいいのでゲソ。
なるほど・・・
考え方は分かったんだが、泥をx個踏んでる確率ってどうやって求めるんだ？
ここでDPを使うでゲソ。(i番目の道で泥をx個踏んでいる確率) = dp[i][x] と置けば、更新式が見えてこなイカ？
・・・ああ、分かったぞ！現在地から、次の二つの泥の状態について考えればいいんだ！
図で説明するとこうだ。
これは2マス進んだほうがいい。1マス進んだ場合、i+3番目も泥だった場合は泥を2回踏むはめになっちまうからな。
この考え方は基本的に有効で、選択肢が同じならなるべく2マス進んだほうがいいはずだ。なぜなら、後に来る泥の遭遇確率を減らせるからな。
これは1マス進んで泥を回避した方がいい。i+3が空だった場合は泥を回避できる。
これは2マス。わざわざ1マス進んで泥を踏むことはないだろう。
これはどっちでもいい気がするが2マス進んでおけばいいだろう。
場合分けは以上。終端に注意してコードに落としこむとこうなるな。
double[][] dp = new double[52][52];
dp[0][0] = 1.0;
for (int i = 0 ; i < len ; i++) {
for (int l = 0 ; l <= 50 ; l++) {
if (i >= len-2) {
// 最後から2番目の場合は、そのまま1マス進む
dp[i+1][l] += dp[i][l];
} else if (dp[i][l] > 0) {
// 次のマスが泥、その次のマスも泥の場合
double p1 = (road[i+1] * road[i+2]) / 10000.0d;
dp[i+2][l+1] += dp[i][l] * p1;
// 次のマスが空、その次のマスは泥の場合
double p2 = (double)((100 - road[i+1]) * (road[i+2])) / 10000.0d;
dp[i+1][l] += dp[i][l] * p2;
// 次のマスが泥、その次のマスは空の場合
double p3 = (double)((road[i+1]) * (100 - road[i+2])) / 10000.0d;
dp[i+2][l] += dp[i][l] * p3;
// 次のマスが空、その次のマスも空の場合
double p4 = (double)((100 - road[i+1]) * (100 - road[i+2])) / 10000.0d;
dp[i+2][l] += dp[i][l] * p4;
}
}
}
// 終点で足しあわせて期待値を求める
double answer = 0.0;
for (int i = 1 ; i < len ; i++) {
answer += dp[len-1][i] * i;
}
return answer;
これでどうだ！
残念でゲソね栄子。惜しいけど違うでゲソ。
にゃぁ！？
一体どこが違うんだ・・・？戦略は間違ってないはずなのに！
確かに、各パターンにおける個々の戦略は間違ってないでゲソ・・・
でも、値の更新の仕方に問題があるのでゲソ。
(2)次のマスが空、その次のマスは泥の場合についてもう一度考えてほしいのでゲソ。
i番目において、この図の青の矢印で確率を更新しているでゲソ。
ここで、(2)のパターンの確率において、「i+2番目が泥である」という情報がi+1番目での確率に含まれてしまっているのでゲソ。
だから、i+1番目において、i番目から伝わった確率については、「i+2番目は泥である」と仮定して計算しなければならないのでゲソ。
なんて面倒な・・・
じゃあ、こういう場合はどうすればいいんだ？
栄子の考え方をそのまま使うとすると、「i+2番目が泥である」という情報を使ったかどうか、という状態を新たにもたせる必要があるでゲソ。
だけど、ここは戦略を少し変えるだけで解決できるでゲソ。
そもそも、何故おかしいことになったかといえば、「i+1番目のマスの確率を更新するのにi+2番目の道路の情報を使ってしまった」ことじゃなイカ。
だから、1マス進む場合は次のマスだけ見ればいいのでゲソ。
そうか！つまり、
ってすればいいのか？
その通りでゲソ。栄子のコードを修正すると次のようになるでゲソ。
double[][] dp = new double[52][52];
dp[0][0] = 1.0;
for (int i = 0 ; i < len ; i++) {
for (int l = 0 ; l <= 50 ; l++) {
if (i >= len-2) {
// 最後から2番目の場合は、そのまま1マス進む
dp[i+1][l] += dp[i][l];
} else if (dp[i][l] > 0) {
// 次のマスが空の場合
double p1 = (double)(100 - road[i+1]) / 100.0d;
dp[i+1][l] += dp[i][l] * p1;
// 次のマスが泥、その次のマスも泥の場合
double p2 = (road[i+1] * road[i+2]) / 10000.0d;
dp[i+2][l+1] += dp[i][l] * p2;
// 次のマスが泥、その次のマスは空の場合
double p3 = (double)((road[i+1]) * (100 - road[i+2])) / 10000.0d;
dp[i+2][l] += dp[i][l] * p3;
}
}
}
// （イカ略）
これで大丈夫でゲソ！
確率って難しいぜ・・・
修行が足りないでゲソ！
ぐぅ・・・