CodeIQ：賭け事はお好き？

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「賭け事はお好き？」（CodeIQ）を参照してください。

問題の概要

問題を引用します。

N個(1 プレイヤーは１回サイコロを振り、出た目の数（1～N）だけ賞金を$として受け取るか、やり直すかを決められる
何度でもやり直すことが可能だが、やり直す度に罰金として1$を払う必要がある
ここで、もし貴方が次のようなルールで意思決定をするとしたら、

出た目の数が閾値(T)以上なら、賞金として受け取り、T未満ならやり直す
所持金に関わらず、出た目の数がT未満なら何度でもやり直す
任意のNに対し、閾値(T)をどのように定めたら、報酬（賞金-罰金）を最大化できるでしょうか？

(中略)

標準入力からNの値が送られる。Nは1<N<30となる整数とする
Eを最大化するTを改行込みで標準出力に送る。Tは必然的に1<=T<=Nとなる整数である
なお設問では、Eを最大化するTは、１つに絞られるものとする。
何故ならTが複数解があるケースを許容してしまうと、誤差を伴うモンテカルロシミューションでは求められなくなるため。
よって、N=6のような条件を考慮する必要はないが、どうしても考慮したい場合は複数解の中で最も値が小さいTを出力すること。

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

def play(t, n)
	sum = 0	# 合計値
	d = 0	# ダイス目
	while true
		d = 1 + Random.rand(n)
		if d >= t then
			sum += d
			break
		else
			sum -= 1
		end
	end
	return sum
end

def test(n)
	mx_p = (30*40000) / n	# 最大試行回数
	mx = 0
	mx_n = -1
	for t in 1..n
		sum = 0
		for _ in 0...mx_p
			sum += play(t, n)
		end

		if mx < sum then
			mx = sum
			mx_n = t
		end
	end
	return mx_n
end

# main
while line = gets
	line.strip!
	if line.empty? then next end

	n = line.to_i

	p test(n)
end

解説

自動採点のプログラムテストではかなり珍しいと思いますがモンテカルロシミュレーションでの回答を期待されています（中略部分で言及があります）。試行回数が少ないとプログラム的には正しくても結果を間違える可能性があるので微妙ですが、モンテカルロシミュレーションでやってみました。

基本的な考え方

モンテカルロシミュレーションなのでやり方は単純です。入力値Nによって1〜Nまで閾値を変化させながら実際に何回かプレーしてみて最善の結果になった閾値を出力すれば良いのです。

play()

実際にプレイします。引数tが閾値、nがダイスのサイズです。乱数は何も考えずRandom.rnd()を使ってしまいます。あとはルール通りの実装です。結果として賞金総額を返します。

test()

閾値を変化させながら何回かplay()を実行し最も結果の良かったものを選びます。変数mxがそれまでの閾値で最も賞金総額が大きかったもの、mx_nがその時の閾値の値です。
試行回数が一定なので獲得賞金の平均値にする必要はなく、合計値で比較します。

問題は試行回数です。多ければ多いほど良いのですが時間がかかります。私は合計で1,200,000回試行するようにしましたが、これはローカルで試験してみてCodeIQの環境で0.9秒くらいで終わりそうな回数ということで設定しました。

雑感

プログラム自体は正しいのですが、テストケースのN=20の時に時々間違えます。実施に投稿したプログラムでは最初は合計1,200,000回試行ではなく10,000回ずつ試行だったのですがこの回数では前述のパターンで間違える頻度が高すぎた（3回に1回くらい間違える）ため修正して上記のコードになりました。
もう少し頭良く、10,000回くらいから始めて有意に差がない場合はその部分だけ試行回数を増やすとかすれば良いのかもしれませんが、これは結構難しいと思います。