きままにものづくり

日々の気付いたことなんかを書いてます。

SRM637Div1Easy

問題

2N枚のカードが渡される。このカードには1~2Nまでのカードが書かれている。自分と相手プレイヤーにそれぞれN枚のカードが渡される。カードを出しあい数字がでかい方が勝者となり1pointもらえる。自分の手札はhand、相手のカードを出す順番はsotheである。sotheの要素が-1の場合は、どんなカードを出すのかが分からない時である。この時の自分のポイントの期待値を最大となる戦略を考え、その時の期待値を求めよ。

解法

  • 1以外の要素の箇所では、勝敗を決定できる。余ったカード同士で勝つ確率を求めることで期待値が求まる。

計算量

O(N^2)

コード