SRM513 Div1 Medium解いてみた

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;
    }
};

わかりにくい説明で申し訳ない.