コンテストそのものの紹介と、予選のときのお話 ⇒ Google Code Jam 2013（予選）に参加しました
本戦の第１ラウンドは、1A、1B、1Cの３回が開催され、各回の上位1000人（合計3000人）が第２ラウンドへ進出というルールです。
3回ともチャレンジしたのですが、結局いずれの回でも1000位に入ることができず、第１ラウンドで敗退してしまいました。今回は初参加ですので、大目に見て下さい。。来年は第２ラウンド進出を果たしたいと思います。そして、あわよくばＴシャツを貰いたい…（第２ラウンドで上位1000人に入ると貰えます）。
それでは各回の振り返りを。
※各回とも、問題はA、B、Cの３問があります。
Round 1A
豪州東部時間（AEST）の4月27日(土)午前11時から2時間半の戦いです。日本時間だと午前10時から。
結果は100点満点の11点で、「0点ではない人」5917名のうち、およそ5000位。ダメですね。噂によれば、0点の人を含めると7000人から8000人程度の参加者が居たそうです。
Round 1A - Problem A ： Bullseye（雄牛の眼→同心円）
問題へのリンク
同心円状に、一定の半径幅（？）で塗る領域と塗らない領域を作っていくとき、与えられたインクの量だとどこまで塗ることができる？という問題です。もちろん、消費するインクの量は面積に比例します。
n個目（nは非負整数）の帯を塗るときに必要なインクの量はカンタンに求まります。開始地点からn個目までの帯を塗るのに必要な合計のインクの量も、カンタンに求まります。これはnの2次式になります。
このnの2次式の値が与えられたインクの量を超えないときの、最大の整数nの値を求めれば良い訳です。
ここで僕は何を思ったのか、2次方程式の解の公式を使って、nの値を導出しようとしてしまいました。
もちろんSmallは楽勝で正解できるのですが、Largeでは計算途中の値が大き過ぎて、正確に平方根の値を計算することができずに誤答してしまったのです。
結構な時間を、平方根の計算の精度を上げるために消費してしまいました。
もちろん、一般的な答えは二分探索法による解nの検索、ということになります。
Round 1A - Problem B ： エネルギー節約
問題へのリンク
たぶん問題文を僕自身が理解できていないので、無理して文章を書くのは良い結果をもたらさないでしょう。
もちろんコンテスト中はコードを書きましたが、サンプルデータすら通らなかったのでパス。。
解説もまだ読んでません。
Round 1A - Problem C ： 数字当てゲーム
問題へのリンク
２人でやるゲーム。Maryamさんが適当に選んだ数字を一定のルールに従って計算し、その結果をPeilingさんに伝え、Peilingさんは当初選ばれた数字を言い当てる、というゲームがあります。このPeilingさんに成り代わってコンピュータで言い当てましょ、という問題です。
わからん。。。
こちらもまだ解説を読んでいません。
Round 1B
豪州東部時間（AEST）の5月5日(土)午前2時から2時間半の戦いです。日本時間だと午前1時から。眠くて仕方ない！（言い訳）
結果は100点満点の0点で、完全なダメ人間と化してしまいました。それにしても、0点であることを人に告げることって勇気が要りますね。
提出した答案は全てincorrect判定を喰らいました。
0点の人間には問題を語る資格無し！
Round 1C
豪州東部時間（AEST）の5月12日(日)午後7時から2時間半の戦いです。日本時間だと午後6時から。今度は最高の時間帯です！
結果は100点満点の18点で、やはり落第点です。順位は「0点ではない人」4482人のうち、2048位タイ。順位が確定した瞬間は今回の第１ラウンドの中で、最も僕が輝いていた瞬間です。そう、2048と言えば2の11乗。極めてキリの良い数字です。
Round 1C - Problem A ： 子音（しいん）
問題へのリンク
ある種族では、名前（アルファベット）の中に連続した子音が多くあればあるほど社会的地位が高いことの証なんだとか（もちろん架空の種族ですよ）。その種族の名前の一覧を見て、それぞれの社会的地位を数値化しましょう、という問題です。
コンテスト中は、どう考えても時間計算量 O(n^2) な方法（全ての部分文字列を検証する）しか思い浮かびませんでした。当然ながらSmallはcorrect判定で8点ゲット。しかしデータ量的に O(n^2) な手法では無理がある問題です。CPUパワーの力任せで試行しましたが、やはり8分で終わる処理ではないですね。
コンテスト終了後、いろいろ工夫できそうなポイントを見つけました。実装はしていませんが。
- 始めに、与えられた文字列から条件を満たす子音の連続を抜き出し、それが何回登場するかを数える方法。 時間計算量 O(n) で済む？？
- 処理の途中で条件を満たす子音の連続を見つけたら、そこで探索を途中まですっ飛ばす方法。これは最悪で O(n^2) だけど、当初の奴よりは相当有利なはず。
後日時間ができたら実装してみたいものです。
Round 1C - Problem B ： Pogo-Stick（ホッピング）
問題へのリンク
ホッピングでジャンプすると、その距離が階差数列（階差？は1）になるものがあります。このホッピングを使って、指定された座標へ行く為の
- 500ジャンプ以内で到達できる方法（Small問題）
- 最短経路（Large問題）
を求めよ、という問題です。
x方向、y方向共に、座標を1つ移動させるためには連続した2回のジャンプを正反対の方向に向ければ良いので、単純にそれを積み重ねて行くという方法でSmallを解くことができます。Smallでは最も遠い座標で(100,100)ですから、このときのジャンプ回数は200回*2で400回となり、条件を満たします。Smallはカンタンです。
Large問題の最短経路。どうすれば良いんでしょうねぇ？？？
今後の修行
という訳でGCJ2013は完全に負け戦でした。
今後こういうコンテストで一矢報いるためには、まず次のようなスキルを身につけないとなー、と思いました。
- 各種、基本アルゴリズムを何も見ずに実装する力：有名なものについては「知らない」訳でもないのですが、コンテストという限られた時間で無意識にサササッとコードを書くには、やはり練習が必要です。勉強と言うよりかは練習。
- 経路探索系：この系統はほぼ完全に無知なので、初歩からの勉強が必要です。予選の宝箱問題とか、Round-1CのホッピングのLargeとか。こういう問題を解けないとダメですね。
- えいご：文章を読むスピードが遅いのでは、勝てません。日本人のコンテスト参加者の中には問題文（本文）をほとんど読まずにInputとOutputとサンプルデータだけ見て実装する強者も居られるらしいですが、個人的な美学として、そういう戦い方はあまりしたくありません（そういう人の存在を否定するつもりはありませんが）。やはり、問題文をしっかりと読み、時々紛れ込んでいるジョークを鼻で笑いつつ、戦っていきたいものです。
来年も頑張ります。
