Dashboard - Qualification Round 2016 - Google Code Jam

AとBはSmallとLarge、CとDはSmallだけ通した。

Problem A. Counting Sheep

ある数を1倍、2倍、3倍…と増やしていった時に0から9すべての数字が現れるまで数える。

証明はわからないけど0じゃなかったら必ず停止するだろうと勝手に予想して、愚直に実装。

Problem B. Revenge of the Pancakes

スタックの上から任意の枚数だけ反転する操作で、すべてを表向きにするには何手かかるか。

表と裏が切り替わるところで毎回反転してやる必要があって、それを最後までやって、最後に裏向きだったら全体反転させる。

Problem C. Coin Jam

01だけでN桁の数を2~10進数で解釈した時にどれも素数じゃない場合をジャムコインとして、自明じゃない約数を列挙する。

桁数がLargeだと32と多くて、素数かどうかの判定自体はRubyのPrimeライブラリのprime?メソッドで結構速く判定できるのだが、約数を求めるprime_divisionにかなり時間がかかる場合があって、どうしたらいいかわからず…。

Problem D. Fractiles

ある規則に基づいてタイルを変換していったときに、どのタイルを調べればゴールドが含まれているか調べることができるか?

Smallは元のタイルの数だけ調べることができるので必ず解ける。Largeはよくわからず…。

解説が公開された

解説