Round 1A

3時間だろうし、半分くらい解ければ通るから適当にやればいいや、と思っていたら2時間半で色々とひどい目にあいました。

A

ゲームをN回以下やったら、その時の勝率がちょうどP％で、その前の履歴を含めても全体の勝率はちょうどQ％になった。という証言は正しいか否か答えよ、という問題。

Nが100以上なら100だったと思うことにして、1以上N以下について勝率がP％になるような状況を考える。全体の試行はとても大きい(たとえば1000000)として、Q％の勝率とする。今回の試行分を引いてみて、勝利回数が0未満になったり、試行回数を上回ったりしなければ正しい。

B

辞書が与えられる。一つの単語を選び、全部の文字を伏せる。相手がアルファベットの中の任意の文字を言うので、あっているところを公開する。相手は可能な文字列があるものの中から、自分が好きな文字の順番にアルファベットを選択する。相手が言うアルファベットの順番が与えられるので、一番相手が言った文字があたらない文字列を答えよ、という問題。

文字を言うたびに辞書を分割していけば良さそう。相手が言う文字が文字列中に出てくるパターンで分割してやる。文字が出現しない回数が最大になるような分岐をした文字列を答える。

C

N枚の手持ちカードと、M枚のこれから引けるカードの順列が与えられる。カードには、A枚カードを引く、B点のスコアを獲得する、残りターン数をCターン増やす、という指示があるので、最初のターン数が1として、スコアを最大化せよ、という問題。

ターン数が増えるカードはグリーディに使って良い。カード数が増えないカードは、最後に残ったターン数だけ引けばいい。なので、カード数が増えるカードについてだけ考える。

smallはカード数は1枚ずつしか増えないので、カード数が増えるカードのうち、今使えるカード群から一番スコアが大きいヤツを使う、というのをK回繰り返す。後はKを可能な限り探索するだけ。

largeはカード数が1枚または2枚ずつ増えるので、これらのパターンを全探索するようにしたい。このとき、一番スコアのいいカードが手持ちにあるのであれば、分岐する必要ない。どちらのパターンも一番スコアのいいカードが手持ちになければ、分岐して、片方のカードがより良いスコアのものが使えるようになるまで使う。というようなことを思ったけれど、終わらず。