hotpepsiの練習帳

Google Code Jam 2016 Qualification Round

23:36

https://code.google.com/codejam/contest/6254486/dashboard

A. Counting Sheep

問題

• 数Nからはじめる
• Nの2,3,4,...倍を数える
• それまでに数えた数値に0から9まで全て出現したら終了
• 終了する数を求める
• 終了しない場合はINSOMNIAと出力する

方針

• 0はINSOMNIA
• 1以上はいつか必ず終了する
• 各桁Dごとに最初に出現する数を求め、それらの最大値が答え
• SmallはClojureで
• 無限リストを生成して、Dが出現する数をフィルタし、それの最初を取る
• https://github.com/firewood/topcoder/blob/master/gcj_2016/QR_A.clj
• LargeはHaskellで
• https://github.com/firewood/topcoder/blob/master/gcj_2016/QR_A.hs

B. Revenge of the Pancakes

問題

• N枚のパンケーキが積まれている
• 表が+、裏が-
• 上から任意の枚数をひっくり返すことができる
• 全てを表にするのに必要な最小操作回数を求める

方針

• 一番深い-の位置でひっくり返していく
• SmallはJavaで
• https://github.com/firewood/topcoder/blob/master/gcj_2016/QR_B.java
• LargeはScalaで
• https://github.com/firewood/topcoder/blob/master/gcj_2016/QR_B.scala

C. Coin Jam

問題

• jamcoinは0か1だけからなる2以上の長さの数値で、2から10までのどの基数で解釈しても素数ではない
• 長さNのJ個の異なるjamcoinを生成する

方針

• 素数表を生成しておき、乱数で生成して判定する
• SmallはJavaScriptで
• https://github.com/firewood/topcoder/blob/master/gcj_2016/QR_C.js
• LargeはC#で
• https://github.com/firewood/topcoder/blob/master/gcj_2016/QR_C.cs

D. Fractiles

問題

• 古代遺跡でタイルの列が発見された
• タイルはLとGの二種類ある
• タイルの列は、K個からなるオリジナルパターンと、複雑さCから生成される
• 複雑さ1の列は、K個のパターンそれ自身
• 複雑さX+1の列は、複雑さXの列から生成される
• X列の1個のタイルLは、K個のオリジナルパターンに置換される
• X列の1個のタイルGは、K個のGに置換される
• タイルは汚れていて判別不能で、S個だけきれいにできる
• 列に少なくとも1つのGが含まれているかどうかを知るため、何番目のタイルをきれいにすればよいかを求める

方針

• SmallはK=S
• オリジナルパターンの左端がLの場合、左からK個は常にオリジナルパターンとなる
• なので、左端のK個をきれいにすればGが含まれているかどうかわかる
• Goで
• https://github.com/firewood/topcoder/blob/master/gcj_2016/QR_D.go
• Largeは未着手

結果

ooooo-

昼からやって半日かかってしまった。Goが難しかった。

http://togetter.com/li/960339