- 競プロ難しすぎね？
144 ：名無しさん＠お腹いっぱい。[]：2019/12/09(月) 19:00:05.55 ID:S8JXgmCs0 - 2人ゲーム
N個の石があってプレイヤーが交互に1〜K個までの石を取っていき最後の石を取ったほうが勝ち(石を取れなくなったほうが負け)
(問題1)
NとKが与えられる
先手も後手も勝率が高い石の取り方をしていった場合に先手と後手で勝つほうを答えよ
勝率が同じ取り方が複数ある場合、取る石が最も多い手を選ぶとする
勝率とは合法手の総当りの中で勝利になる手の割合である
例 N=3, K=3 のとき
先手は石を1個、2個、3個のいずれかを取る合法手がある、このときの先手の各勝率は
先手が最初に1個を取る場合、後手が2個取り後手の勝利、後手が1個取り先手が1個取り先手が勝利、と２通りあり先手の勝率は 1/2=50%
先手が最初に2個を取る場合、後手が1個取り後手の勝利、と１通りあり先手の勝率は0/1=0%
先手が最初に3個を取る場合、先手の勝利、と１通りの勝率は1/1=100%
50%,0%,100%となりこのとき先手は勝率の最も高い100%の手である3個の石を取る
例 N=4, K=3のとき
先手は石を1個、2個、3個のいずれかを取る合法手がある、このときの先手の各勝率は
先手が最初に1個を取る場合、
後手が3個取り後手の勝利、後手が2個取り先手が1個取り先手の勝利、
後手が１個取り先手が２個取り先手の勝利、後手が１個とり先手が１個取り後手が１個取り後手の勝利
と４通りあり勝率は2/4=50%
先手が最初に2個を取る場合、後手が2個取り後手の勝利、後手が１個取り先手が１個取り先手の勝利、と2通りあり先手の勝率は1/2=50%
先手が最初に3個を取る場合、後手が１個取り後手の勝利、と１通りの勝率は0/1=0%
50%,50%,0%となりこのとき先手は勝率の最も高い50%の手を選ぶが同率が２つあるため取る石の多い2個取る手を選ぶ
(問題2)
NとKが与えられる
先手は(問題1)と同様の勝率の高い石の取り方をしていく
後手は先手の戦法を知った上で最適な石の取り方をしていく
後手が勝てるか答えよ
(問題3)
NとKが与えられる
後手は(問題1)と同様の勝率の高い石の取り方をしていく
先手は後手の戦法を知った上で最適な石の取り方をしていく
先手が勝てるか答えよ
|
|