本履歴

購入した古本の履歴と時々プログラミング

プログラミングコンテストの練習

とっておきの数学パズルから次の問題。

一列に50個のコインが並んでいて、先手後手が両端いずれからか一つコインを取っていきそのコインに書かれている金額を得る。最後のコインを取った時に総金額が多いほうが勝ちとする。この時、先手が負けない戦略を考えよ。


全部同じコインだと引き分けで勝てないパターンがあるので負けない方法。解答はコインの並びの偶数ポジション、奇数ポジションの総和を考えればOK。
さて、これをどうやってプログラムでうまく解くんだろうと思っていたら(全パターンは2^50)、DP使えば簡単なことに気づいた。
dpの返り値が正数なら先手が最適選択すればそれだけ後手よりより多く金額ゲットできる。
さて、N=50だと先手ほぼ必勝。N=49だと、後手が9割くらい必勝。奇数の場合N、MAXで割合ブレるんだろうけど、これは面白い。

require "memoize"
include Memoize

N=50
MAX=10

$coins=N.times.map{
  rand(MAX)
}

#given the sub $coins[x..y], return the 1st player's max score if both players play optimally
def dp(x,y)
  if x==y
    $coins[x]
  else
    [$coins[x]-dp(x+1,y),$coins[y]-dp(x,y-1)].max
  end	
end

memoize(:dp)

p $coins
puts
p dp(0,N-1)