google code jam 2015 qual - れどこだ目指すよ！　(；`・ω・）

だらだら参加してしまって非常によくない。けど、とりあえず通過。
oo oo o- o- 57pt 2369位

A. Standing Ovation

問題

立っている人がi人いたら自分たちも立つという人がSi人いる。
iは0〜(1+Smax)まであり、Siは0〜9まで与えられる。
このとき、自由にi人いたら自分も立つような人数を増やすことができる場合、最終的に全員を立たせるために追加しなければならない最少人数を答える

テストケース数<=100
small Smax<=6
large Smax<=1000

解いた方法

貪欲。

iが少ないほうから、条件を満たすかどうか確認し、満たしていれば追加する必要はない。
満たしていない場合は、i人になっていなければならないので、i-それまでの合計人数を追加してあげる。

B. Infinite House of Pancakes

問題

D人がそれぞれパンケーキPi枚持っている、という情報が与えられる。
パンケーキを食べたい人は無限に存在し、今、二つの操作が許されている。
①何もしない(パンケーキを持っている人が全員1枚1分で食べる)
②食べるのを止めて、1回1分でパンケーキを移す(パンケーキを1枚以上持っている人から任意枚選んで、他の1人(パンケーキを持っている人でも持っていない新しい人でも)に移数)
すべてのパンケーキを食べるのに必要な最小の時間を返す。

テストケース<=100
small D<=6,Pi<=9
large D<=1000,Pi<=1000

解いた方法

Piが大きいとき、「①を行ってから②を行う」ようなケースと「②を行ってから①を行う」ようなケースでは後者の方がパンケーキを減らせるペースが速いと考えられる。
なので、②をまとめて最初に行ってパンケーキを分配し、そのあとで①をまとめて行えばよい、と考えられる。
①を最後に行う回数をx回とすると、最初にまとめてすべてのパンケーキをx枚以下になるように最小回数y回で分割すれば、(x+y)回で最小となるものが答えになる。
xはPiの最大値までしかないので、O(Piの最大値*D*x以下に分割する操作)程度。

C. Dijkstra

問題

クオータニオンのように1,i,j,kに対して「i*j=k」のような変換ルールが与えられる。
今、i,j,kからなる文字列Sが与えられる。(strと繰り返し回数Xが与えられ、strをX回つないだものがS)
これを変換ルールを適用して「ijk」できるか否かを答える。

テストケース数<=100
strの長さ<=10000
small X<=10000,Sの長さ<=10000
large X<=10^12,Sの長さ<=10^16

解いた方法

smallだけ。

実際に、Sを作って、「先頭〜i」がi、「i+1〜j」がj,「j+1〜終端」がkになることを確認する。
しかし、そこそこサイズが大きいため、無駄な探索がなくなるように以下の条件を追加したら通った。
すべての文字列を変換した場合、「ijk」は「-1」になるはずなので、それを確認し、なっていなければ「ijk」にはなりえないので、NOを返す。

D. Omunous Omino

問題

リチャードとガブリエルが、Xオミノ(1の場合は、1x1のセル。4の場合は、テトリスの4セルで構成されるやつ)をR*Cの長方形にぴったりあてはめるゲームをしている。
リチャードは、Xオミノから1つだけガブリエルが必ず1回は使わなければいけないXオミノを指定できる。ガブリエルは指定されたXオミノを必ず1回以上使用、その他のXオミノは任意枚数、反転、回転してよく、R*Cに敷き詰められるならばガブリエルの勝ち、そうでなければリチャードの勝ちとなる。
X,R,Cが与えられるので、どちらが勝つことができるか返す。

small テストケース数<=64, X,R,C<=4
large テストケース数<=100, X,R,C<=20

解いた方法

smallだけ。

全パターンを列挙できる。
X=1の場合は、どんなR*Cでも置くことができるので、ガブリエルの勝ち。
X=2の場合は、R*Cのセル数が奇数でなければ置くことができるので、ガブリエルの勝ち、それ以外はリチャードの勝ち。
X=3の場合は、R