どうもです。
日本時間の4月13・14日にかけてGoogle Code Jam 2013の予選が開かれました。
完全に忘れててTwitterのTLで偶然思い出して滑りこみ参加。
予選は特に通過人数の制限もないようで、35点取ればいいらしいので、一時間くらいで解けそうな問題解いてRound 1の参加権だけとってしまいました。
今回はGoogle Code Jam 2013 予選（https://code.google.com/codejam/contest/2270488/dashboard）の参加記録です。
ちなみに言語はJavaで書きました。
問題A
4×4のOXゲームの勝利判定問題。
ワイルドカードを含めて縦横ななめでOかXが一列並んだほうが勝ち。
勝利パターンが10パターンしかないので、全探索してしまえばいい。
問題B
芝刈り機問題。
一直線に端から端まで刈ってしまう芝刈り機で、1ラインを刈り切るまで途中で芝刈り機の刈り取る高さは変更できない。
で、入力パターンの高さ（模様）になるようにかることができるかを判定できるかという問題。
［僕の回答］
刈り取るエリアは最大で100x100。芝の高さは1mm〜100mm
例として
2 1 2
1 1 1
2 1 2
はYesで、
2 2 2 2 2
2 1 1 1 2
2 1 2 1 2
2 1 1 1 2
2 2 2 2 2
はNoなので、
アルゴリズムとしては以下のようにしました。
０．テストケースの中のMAXとMINを求める
１．縦横のラインですべての数字が等しいラインが存在するかどうか判定
→ 存在しなければ、即No
２．すべての数字が等しいラインの数字がMINの場合、そのラインの数字を＋１
３．２のあと配列にMINが存在するかどうか判定
→ 存在する場合は １．を行う
→ 存在しない場合は MIN＋＋して１．を行う。
以上をMIN==MAXになるまで回して、NoでなかったらYes
このアルゴを実装して、Smallケース、Largeケースともに正解
この時点で３５点を超えたので、問題C以降は大して考えてないです。
［問題C］
回文問題
１２１のようなに左か読んでも右から読んでも同じ場合を回文という。
さらに、１２１は11x11で回文^2のようになっている。
このようにX＝回文かつX=回文^2のようなXをfairと呼ぶことにする。
２つの自然数A,Bが与えられ、AとBの間のfairな自然数の個数を答えよという問題。
この問題の最大の課題はA,Bが非常に大きな数字であることA = 10^100までの可能性がある。
なので、通常の平方根 sqrt(A) が使えない。
そこで、２分探索で平方根を出す関数BigSquareを作成。
で、BigSquare(A)<= X <= BigSquare(B) なXを対象に
１．X=回文
２．X^2=回文
の２つを判定するアルゴを実装。
これでサクッとSmallはとける。
しかし、１．が思ってるより時間がかかってしまうことが判明。
Largeは制限時間内に解くことができなかった。
改良策としては、１．のようなXを瞬時に生成する必要がある。
とりあえず思いつくところとしては、桁数を決めて回文なXを生成してしまう。
ざっと計算量を考えてみる。
最大でA<=10^100
BigSquare(A)<=10^50
BigSquare(A)以下の回文の個数 <= 10^25
うーん、でかい。
これじゃ終らない。
後日、ちょっと考えて、制限時間内に解くことができました。
「２乗した時に各桁で繰り上がりが発生したら無視する」
繰り上がりが起きるのは以下の場合です。
１．各桁のどれかが４より大きい
２．各桁の総和が１０以上
３．各桁に「２」が３個以上（３は論外）
これで、計算量がどの程度になるかというと、
２．で１０＾５くらいになります。
これなら余裕で計算出来ます。
しかし、１０＾５を１０００回やるのは得策ではないので、
10^100までのfairな数をすべて生成してしまいます。
（この際に、fairな数がintを超えてしまうとまた考えないといけませんが、今回は４００００個ほどで、特に問題はありませんでした）
fairな数のリストが出来たら、A<=X<=B (X is fair)なXをカウントしていくだけです。
以下にgithubにソース起きました。
https://github.com/taharactrl/google-code-jam-2013-practice-c/blob/master/MainC.java
これが本番中にできるようにならないとなあ
日本時間の4月13・14日にかけてGoogle Code Jam 2013の予選が開かれました。
完全に忘れててTwitterのTLで偶然思い出して滑りこみ参加。
予選は特に通過人数の制限もないようで、35点取ればいいらしいので、一時間くらいで解けそうな問題解いてRound 1の参加権だけとってしまいました。
今回はGoogle Code Jam 2013 予選（https://code.google.com/codejam/contest/2270488/dashboard）の参加記録です。
ちなみに言語はJavaで書きました。
問題A
4×4のOXゲームの勝利判定問題。
ワイルドカードを含めて縦横ななめでOかXが一列並んだほうが勝ち。
勝利パターンが10パターンしかないので、全探索してしまえばいい。
問題B
芝刈り機問題。
一直線に端から端まで刈ってしまう芝刈り機で、1ラインを刈り切るまで途中で芝刈り機の刈り取る高さは変更できない。
で、入力パターンの高さ（模様）になるようにかることができるかを判定できるかという問題。
［僕の回答］
刈り取るエリアは最大で100x100。芝の高さは1mm〜100mm
例として
2 1 2
1 1 1
2 1 2
はYesで、
2 2 2 2 2
2 1 1 1 2
2 1 2 1 2
2 1 1 1 2
2 2 2 2 2
はNoなので、
アルゴリズムとしては以下のようにしました。
０．テストケースの中のMAXとMINを求める
１．縦横のラインですべての数字が等しいラインが存在するかどうか判定
→ 存在しなければ、即No
２．すべての数字が等しいラインの数字がMINの場合、そのラインの数字を＋１
３．２のあと配列にMINが存在するかどうか判定
→ 存在する場合は １．を行う
→ 存在しない場合は MIN＋＋して１．を行う。
以上をMIN==MAXになるまで回して、NoでなかったらYes
このアルゴを実装して、Smallケース、Largeケースともに正解
この時点で３５点を超えたので、問題C以降は大して考えてないです。
［問題C］
回文問題
１２１のようなに左か読んでも右から読んでも同じ場合を回文という。
さらに、１２１は11x11で回文^2のようになっている。
このようにX＝回文かつX=回文^2のようなXをfairと呼ぶことにする。
２つの自然数A,Bが与えられ、AとBの間のfairな自然数の個数を答えよという問題。
この問題の最大の課題はA,Bが非常に大きな数字であることA = 10^100までの可能性がある。
なので、通常の平方根 sqrt(A) が使えない。
そこで、２分探索で平方根を出す関数BigSquareを作成。
で、BigSquare(A)<= X <= BigSquare(B) なXを対象に
１．X=回文
２．X^2=回文
の２つを判定するアルゴを実装。
これでサクッとSmallはとける。
しかし、１．が思ってるより時間がかかってしまうことが判明。
Largeは制限時間内に解くことができなかった。
改良策としては、１．のようなXを瞬時に生成する必要がある。
とりあえず思いつくところとしては、桁数を決めて回文なXを生成してしまう。
ざっと計算量を考えてみる。
最大でA<=10^100
BigSquare(A)<=10^50
BigSquare(A)以下の回文の個数 <= 10^25
うーん、でかい。
これじゃ終らない。
後日、ちょっと考えて、制限時間内に解くことができました。
「２乗した時に各桁で繰り上がりが発生したら無視する」
繰り上がりが起きるのは以下の場合です。
１．各桁のどれかが４より大きい
２．各桁の総和が１０以上
３．各桁に「２」が３個以上（３は論外）
これで、計算量がどの程度になるかというと、
２．で１０＾５くらいになります。
これなら余裕で計算出来ます。
しかし、１０＾５を１０００回やるのは得策ではないので、
10^100までのfairな数をすべて生成してしまいます。
（この際に、fairな数がintを超えてしまうとまた考えないといけませんが、今回は４００００個ほどで、特に問題はありませんでした）
fairな数のリストが出来たら、A<=X<=B (X is fair)なXをカウントしていくだけです。
以下にgithubにソース起きました。
https://github.com/taharactrl/google-code-jam-2013-practice-c/blob/master/MainC.java
これが本番中にできるようにならないとなあ
