Hatena::Grouptopcoder

人生是睡眠 - 夢の中ではredcoder -

 | 

2010-02-04

過去問 SRM 408 Div 2 1000 MarblesInABag

00:57

やめないでー!パチョレック!(動画と本文は一切関係ありません。)

赤と青のマーブルチョコが入っているカバンから二人で交互にチョコを取り出す問題。

マーブルチョコの個数が奇数と決まっており、かつ最初に引くのは自分。

(という事は最後の1手は自分に回ってくる)

相手は必ず青をひくが、自分は運任せにひく。

最後に青を引ければ勝ちで、赤を引いたら負け。

このとき、勝てる確率はいくらか?

r = 赤の個数、 b = 青の個数とする。(r,bは最大で4000個)

はじめ、トップダウン式に考えて再帰+メモ化を試みたが、double型の4001 * 4001の二次元配列を

確保しようとしたら、メモリオーバー・・・

仕方ないのでDPでボトムアップ的に考えてみた。

チョコの総数が1の時、3の時、5の時・・・とやっていくと、メモリ領域は8000 * 2 で済む。

(最大で4000個、3999個なので)

よーし。でも提出するまえにぽかミスをしてた。てへ。

境界値のチェックはちゃんとしようね。

public class MarblesInABag {
    public double getProbability(int r, int b) {
    	double [] a1 = new double[r+b+1];
    	double [] a2 = new double[r+b+1];
    	a1[0] = 1;a2[0] = 0;
    	for(int i = 3; i <= r+b;i += 2){
    		for(int j = 0; j <= i; j++){
    			if(j == 0)
    				a2[j] = a1[j];
    			else{
    				a2[j] = ((i -j) / (double) i ) * a1[j] + (j /(double) i ) * a1[j-1] ;
    			}
    		}
    		for(int k = 0; k < i;k++)
    			a1[k] = a2[k];
    	}
    	return a1[r];
    	
    }
}

 |