GoogleCodeJam2004
この文章は、2004/09/18から2004/09/25のブログを編集したものです。
QualificationRound
Google Code Jam というのは、Googleが人材発掘を目的としてTopCoder上で行っているプログラミングコンテストです。去年もやっていたらしいです。
申し込み > Qualification Round > Round1 > Round2 > Championship Round
という流れで、今は Round1 の手前です。
とりあえず Qualification Round は通りました。1000点問題で大失敗したのですが、400点問題が難しかったので運よく通った感じです。
失敗というのは、コーディング速度を求めるコンテストなのに、最適なアルゴリズムを考えてしまったこと・・・。普段の仕事ではトロいアルゴリズムなんて使い物にならないので、ついやってしまいましたが、ベタな方法で実装してしまうほうが良いようです。とりあえず、総当りにしておいて、それでタイムアウトしてしまうようだったら、簡単なチェックを入れてみるという作戦が良さそう。
ちなみに、参加者向けに詳しく言うと、ギア比問題で、総当りではなく、数学的に解こうとしてしまいました。総当りで解くと非常に簡単ですが、マジメに解くと難しい問題です。
もう一問は、アンチエイリアス問題、こちらの方が1000点問題よりも面倒で、参加したRoomの正答者が少なかった原因のようです。
次回のRound1は、9/20 9:00 PM ETです。日本時間にすると、9/21 10:00 AM JST です。やっぱり日本からだと参加しにくい時間ですね。
まぁ、実力的にTOP50は無理だろうけど（というか海外まで行く気ないし）、Round2までは残りたいところです。
使用言語
TopCoderのコンテストでは、C++, C#, Java, VBが使用できます。
どの言語を使用しているかは、Summaryの各スコアの色で判断することができます。もちろん、直接コードを見てもわかります。
ちなみに、
黄色 C++
青色 C#
緑色 Java
水色 VB
です。
せっかくなので、参加者の使用言語について調べてみました。各RoomのTOP16（合計160名）の使用言語です。
C++ 107人 (66.8%)
Java 44人 (27.5%)
C# 8人 (5.0%)
VB 1人 (0.6%)
あくまでもコンテストに参加した中で正答を早く出せた人の統計です。
個人的な感想としては、C++が健在でちょっと安心しました。C#を使う人は意外と少なくて、熟練度の低い人が多いようです。逆に考えると、新しく言語を覚える人がC#から入ることが多いのかもしれません。VBはやはり少ないようです。Javaは妥当なパーセンテージでしょう。ポストC++としてC#が普及するためには、Microsoft以外がもっと頑張らないとダメかもしれません。
ちなみに、QualificationRound の参加者は2564人、時間内に正答を出せた（ポイントが１以上）人は1197人(46.7%)でした。
素早いコーディング
ソースを見ていて、マクロを使う人が多いことに気が付きました。
しかも、
#define FORI(A,B) for (int i = (A); i < (B); i++)
のような通常では使わないようなマクロです。
考えるに、これは素早いコーディング、つまりタイプ量を減らすための手法なのでしょう。
通常のコーディングでこんなことをしたら、可読性の低いコードを書くな、と怒るところです。
マクロの使用は、その可読性の低下を考慮しても他の利益が大きいときや、展開して書いた方が可読性が下がるときに限るべきです。
しかし、コーディング速度を競うときに最も優先されるものは速度ですから、メリットが大きい、つまり使っても良いと考えられます。
おそらくTopCoderに慣れている人なのだと思いますが、大量のマクロを従えてコンテストに望んでいる人もいます。
もはや、C++ではなく、C++をベースにした新しい言語と言ってしまっても良い感じです。
Round1
またしても大失敗。
250点問題で、入力条件を読んでませんでした。タイムアウトするような問題ではないから、大丈夫だろうと思って見ませんでしたが、int では入らないという罠がありました。long long か doubleにしないとダメでした。
やっぱり英語の壁は大きいかなぁ。
って、単に注意力が足りないだけか。
1000点問題は非常に厳しい問題でした。
単純な総当りだと多分タイムアウトするし。
実際に1000点問題をクリアした人は、20人しかいません。しかし、上位の人のソースは滅茶苦茶短い！絶妙なアルゴリズムで解かれています。このソースを見るために参加していると思っても良いくらいです。有休とって参加してる甲斐があります（笑
1000点問題は以上の通りですが、250点、500点問題も、かなりの人がsystem test を通ることができなかったようです。結果的に、次のラウンドへのボーダーラインである250位は、188.85点と低い点数でした。そのため、500点問題をクリアした人は、数人の例外を除いて250以内に収まっています。
私も、成績については非常に不満足ですが、またしても運よく通過できました。
Round2で50位以内に入るには、1000点問題に挑戦しなければダメでしょうね。まぁ、時間に追われる緊張感を楽しみたいと思います。って、また有休ですか・・・（ちなみに今日は、役所に行くという用事もありました）
日本からの参加者
今回の統計（勝手に調べてます）
Round1の総参加者数は442人(参加率88.4%)でした。
さて、日本からの参加者数はどれくらいいるのでしょうか。
参加者の登録国名が見られるので、それで日本からの参加者を数えてみました。
・Qualification通過 9人(全体に対する割合1.8%)
・Round1通過 4人(1.6%)
Qualificationの参加者数は面倒なので調べてませんが、比率で言えば、45人前後だと思われます。
ちなみに、登録国名であって、日本人かどうかは分かりません。日本からの参加者でトップの人は、おそらく日本人じゃないし。
そういえば、TopCoderの統計（オフィシャル）で、国別のランクがあるのですが、そこに日本はありません。どうやら日本からの関心は低いようです。日本人技術者の非グローバルさが反映されているような感じがします。
1000点問題＆解答
1000点問題の解説です。
ちなみに1000点問題は、こういう問題でした。
=========
ファイルをHDDに格納するとき、連続ではなくフラグメントが発生することがあるが、これをファイルごとに連続したセクタに直せ。
ディスクのデフラグ前のセクタ配置情報がvector<string>で渡される。各stringが１つのファイルを表し、１つの半角スペース区切りの整数値でセクタを示す。たとえば、"4 9 6 59 41"は、ファイルの先頭がセクタ4に格納されていて、次に9, 6, 59、最後に41と格納されていることを表す。この場合、デフラグではセクタ4-9に並び直せばよい。
また、ディスクの総セクタ数がint n で渡される（セクタ0からn-1まで使用できる）。
セクタ２つ分を格納できるメモリがある。
このとき、セクタの移動回数の最小値を返す関数を作れ。
総セクタ数は、10から100。
ファイル数は、1から12。
１つのファイル情報は、1から50文字。
=========
以下、解き方の概要です。
一部のファイルの配置についての、部分問題に分けて考えるのがミソです。
ただし、セクタの重複などが解決できるようなデータの持ち方をしないといけません。これがなかなか思いつきません。
配列 int [n + 1] を用意して（nは最大セクタ番号）、そのセクタ番号から新しいファイルを始める場合に必要なコストを格納します。[x]のコストが1の場合、[x+1]以降のコストも1となりますが、これは省略します。
たとえば、ファイルを何も配置しないとき、[0] = 0です。
ファイル1（初期状態で{5,8,7}）の場合、0から配置すると3つのセクタを入れ替える必要があるので、コスト3です。したがって、[3] = 3です。[0],[1],[2]はコスト∞です。同様に、5の場合コスト1なので、[8] = 1です。
このようにして、ファイル1とファイル2を独立に配置したとします。次にファイル1,2をあわせた配置を考えます。
最終的に、全てのファイルを配置したときの最適解が得られます。
O(2^(n-1))のアルゴリズムですが、nは最大で12、配置の組み合わせで言うと4096ですので、十分に使えます。（コンテストでは、実行時間が8秒を越えるプログラムは無効となります）
Round2
難しかった・・・
まず、問題を理解するのに時間がかかった。
これは英語力不足。
アルゴリズムが思いつかなかった。
これはプログラマとして話になりませんね。
しかも、375点問題は、いろいろ場合分けを考える気力が無かったという問題外の理由です。もうモチベーション落ちまくり。
結局、550点問題しか出来ませんでした。550点問題は、極小が最小になる関数の極値を求める問題だと思います。本当に極小が最小になるかは確認していませんが、雰囲気的にそんな感じ。適当な数値計算をすればいいのですが、もの凄く原始的な方法で解きました。仕事で使うこともあるのに・・・。 Challenge Phase がちょっと恥ずかしかったです。
825点問題は、遅そうなアルゴリズムしか思いつきませんでした。
問題的には、おそらく
・375点問題 場合分け
・550点問題 数値計算
・825点問題 最適化
という感じです。
今回のボーダーラインは820.48点でした。825点を確実に解いて、他の問題でプラスしないと通れません。
話は変わって、今回の参加者数ですが、Round2は自動登録なので、本当の参加人数は不明です。アクセスしなくても0ポイントとして結果が出ます。
日本から参加者では、御二方は不参加でした。
残りの二人も最終ラウンドには残れませんでした。
総評
こういうシステムのプロコンは初めてだったので興味深かったです。速く書くスキルが一番重要視されるのですが、他の人のコードを読んでバグを探すスキルも必要な点が面白いです。ただ、このシステムって特許が取られているという話なので、自前で作るわけにはいかなんですよね。また、上位の人たちは、レベルが違う感じでした。
出題は、（特に高得点問題で）最適化問題が多くてちょっと戸惑いました。というか、解けませんでした。これは、今後の課題にしたいと思います。
ついでにいうと、英語がまるでダメなのが露見した感じ。これで相当に損をしてます。
TOPCODERのCompetitionで日曜開催のものや、午前中（日本時間だと午後）に開催されるものなら気軽に参加できるので、今後も適当に参加してみようと思います。
補足
Round2の不参加人数を数えてみました。
全問題unopenの人は17人でした。
