問題
2N枚のカードが渡される。このカードには1~2Nまでのカードが書かれている。自分と相手プレイヤーにそれぞれN枚のカードが渡される。カードを出しあい数字がでかい方が勝者となり1pointもらえる。自分の手札はhand、相手のカードを出す順番はsotheである。sotheの要素が-1の場合は、どんなカードを出すのかが分からない時である。この時の自分のポイントの期待値を最大となる戦略を考え、その時の期待値を求めよ。
解法
- 1以外の要素の箇所では、勝敗を決定できる。余ったカード同士で勝つ確率を求めることで期待値が求まる。
計算量
O(N^2)