Easyに時間かかりまくった上にFailedSystemTestなうえに,Ratingが100以上下がるというトラウマ回.反省は,「制限ちゃんと見て,オーバーなコード書かないようにしようぜ」.Easyの嘘解法(その時は正解だと思っていた)を書いた後に,Medium開いたら「あれ?簡単じゃね?」と思ったので,PracticeRoom開いてから解いた.
問題概要
完全記憶能力をもった子がN*M枚のカードを使って神経衰弱をする.(N,Mの少なくとも片方は偶数)N*M/2組同じカードがある.この子が神経衰弱を終えるのに必要な手数の期待値はいくつか.(2枚ひっくり返すのを1手と数える)
解法
どう見ても確立のDP.
dp[i][j] := i組のカードが残っていて,そのうちj種類のカードの片方の場所を知っているときにかかる手数の期待値
0<= j <= i <= N*M/2, dp[0][0] = 0
戦略は,まだめくっていないカードをめくって,もう片方の場所を知っているカードをめくったら,そのカードをめくってとる.もう片方を知らないカードだったら,まだめくっていないカードをさらにめくる.めくったカードが,片方の場所を知っているカードだったら,次の時に確実に取れる.また別のカードが出たら,場所を知っているカードの数が増える.また,偶然一致してとれることもありうる.
それぞれの確立を計算する.
カードがi組残っている=カードがi*2枚残っている
j種類のカードの場所を知っている→i*2-j枚の中身は知らない
まだめくっていないカードをめくり,すでに片方の場所を知っているカードが出てくる確率は,j / (i * 2 - j)(=p1),まだ見つかっていないカードが出る確率は(i * 2 - j * 2) / (i * 2 - j)(=p2)
すでに片方の場所を知っているカードをめくった場合,そのカードは確実にとることができる.
まだ見つかっていないカードをめくった場合は,さらに未確認のカードをめくる.
その時に,偶然カードが一致する確率は1 / (i * 2 - j - 1)(=q1),すでにもう片方を見つけたカードが出る確率はj / (i * 2 - j - 1)(=q2),さらに場所を知らないカードが出てくる確率は,(i * 2 - j * 2 - 2) / (i * 2 - j - 1)(=q3).
1回目の選択で,すでに他方の場所を知っているカードをめくった→dp[i-1][j-1]を加える.
1回目の選択で,まだ見つかっていないカードをめくった上で,
- 偶然一致した →dp[i-1][j]を加える.
- 他方の場所を知っているカードをめくった→次の手順でそのカードをとる→dp[i-1][j] + 1を加える.(jに1が加わるが,同時に減る.)
- さらに見つかっていないカードをめくった→dp[i][j+2]を加える
それに,今回めくった手数である1を加算する.
以上から,漸化式に落とすと,
dp[i][j] = p1 * dp[i-1][j-1] + p2 * q1 * dp[i-1][j] + p2 * q2 * (dp[i-1][j] + 1) + p2 * q3 * dp[i][j+2] + 1
以上でdpをする.dp[N*M/2][0]が求める答えになる.
問題点としてi=1, j=1の時に,分母が0となってしまうことがある.
0除算を回避するには,
- dp[i][i] = iとして計算を行う.
- 確立が0になるときはif文で回避して計算を行わない
- dp[1][0] = dp[1][1] = 1とし,iが2以上から始める
などが考えられる.
ソースコード
ここでは,dp[i][i] = iとして計算を行っている.
#include <algorithm> #include <iostream> #include <sstream> #include <string> #include <vector> #include <queue> #include <set> #include <map> #include <cstdio> #include <cstdlib> #include <cctype> #include <cmath> #include <cstring> using namespace std; #define MAX (60 * 60 / 2) double dp[MAX][MAX]; class PerfectMemory { public: double getExpectation(int N, int M) { double res; memset(dp, 0, sizeof(dp)); for(int i=1;i<MAX;++i){ dp[i][i] = i; for(int j=i-1;j>=0;--j){ double known, unknown, succ, faila, failb; known = (double)j / (i * 2 - j); unknown = 1.0 - known; succ = 1.0 / (i * 2 - j - 1); faila = (double)j / (i * 2 - j - 1); failb = 1.0 - succ - faila; dp[i][j] = 1 + known * dp[i-1][j-1] + unknown * succ * dp[i-1][j] + unknown * faila * (dp[i-1][j] + 1) + unknown * failb * dp[i][j+2]; } } res = dp[N * M / 2][0]; return res; } };
わかりにくい説明で申し訳ない.