Programming Magic

ハル研究所のプログラミングコンテストは、毎年11月下旬～1月上旬に開催される学生向けのプログラミングコンテスト。使用言語はC言語、またはC++。ハル研究所のプログラミングコンテストの面白いところは、期間中プログラムをいつでも提出できて、そのプログラムは自動評価されスコアがわかるところだ。自分のスコア以外にも参加者上位のスコアを見ることができる。

作るプログラムは毎年違うが以下のような感じ。(詳細はリンク先参照。)

私が参加したのは2006年から。(当時は別の名前で参加していたが、上位に入ってはいなかった。)それ以前の問題は、ページが既に消えているのでうろ覚えだが、2005年が橋を渡る問題で、2004年が肉を焼く問題。問題には、時間内に点数ができるだけ高くなるように一定数の問題を解くタイプ(2008年、2006年)とできるだけ早くたくさん問題を解くタイプ(2007年)がある。問題を解くこと自体は簡単で、どれだけスコアを高くするかがポイントとなる。

コンテスト期間が始まるとチェックプログラムが配布され、その中に含まれるanswer.c(もしくはanswer.cpp)に書かれている関数を実装して提出する。2008年の場合は、１対戦ごとに呼ばれるInitPlayer関数と毎ターン呼ばれるThinkingを実装した。

void InitPlayer(const Farm *farm, Position2D position, int playerID){
}

Command Thinking(const Farm *farm, const Position2D position[], int playerID){
	/*
		ここには最初からサンプルの思考ルーチンが実装されているので、それを書き換える。 
		そのサンプルをそのまま提出してもスコアは入る。
	*/
}

ちなみに、標準ライブラリはほぼ全て使えないが、一部だけ使うことができたり、必要そうな標準ライブラリの関数を実装したコードがサンプルに含まれていることがあるので、あまり問題にはならない。

ハル研のプロコンは、それほど高いプログラミング能力や知識がなくても、その分時間を使うことでカバーできるので、頑張れば大学1年生や専門学校生でも上位に入れるんじゃないかと思う。今年、上位に入れなくても来年のためになることもあるので、時間に余裕のある学生は参加するといいと思う。

頑張れば上位に入れるとは言ってもアルゴリズムを全く知らなければ難しいのは当然だ。そこで、参加前に予習しておくと良さそうなアルゴリズムを挙げてみる。

1. 深さ優先探索・バックトラック法
   何らかの探索をする可能性が非常に高いため簡単な探索アルゴリズムくらい知っておく必要がある。ちなみに、幅優先探索や最良優先探索のようなアルゴリズムは、標準関数やnewが使えないのでメモリの動的確保ができず、実装するのが難しい。(不可能ではないが。)
2. バケットソート・基数ソート
   探索と同様にソートをする可能性も非常に高い。ソートアルゴリズムの中で高速、かつ実装が簡単なこれらのアルゴリズムを知っておくといい。メモリを大量に使うことにはなるが、2008年の参加で26*9000*4byteの配列を作っても問題はなかった。(ただし、ローカル変数として巨大な配列を作ると遅いので、グローバル変数にする必要はあった。)
3. バブルソート・挿入ソート・クイックソート
   バブルソートや挿入ソートはそれほど速くはないが、チェックプログラムやサンプルプログラムに使われていたり、テスト用の実装で使うこともある。クイックソートは、バケットソートの方が（たぶん）高速であるためあまり必要ないかもしれないが、過去の上位入賞者で使っている人もいた。
4. 二分探索
   あらかじめソートしておくことで高速に探すことができるということは知っておけば何かに応用できる可能性が高い。
5. ミニマックス法
   このアルゴリズム自体を使うということはないと思うが、このような方法で探索量を減らすことができるということを知っているといいかもしれない。ハル研のプロコンではほぼ毎回、高速化が必要になるため、探索を使うなら探索量を減らす必要がある。
6. グリーディ法・山登り法
   最適解の求められない問題ではよくあるアプローチなのでこれも知っておくといいかもしれない。

この他には、アルゴリズムではないが、再起関数をループに書き直す練習をしておくといい。このとき、できればgotoは使わない方がいいが、どうしてもできなければgotoを使ってもいい。再起関数の展開は、高速化のために使われる可能性が非常に高く、その効果は大きい。

ちなみに、これらは予習しておくと良さそうなものなので、コンテストが始まってから調べても意味がないものもある。コンテストが始まってしまったら、コンテストに必要そうなものだけを調べればいい。

1. チェックプログラムをダウンロードして、サンプルを提出
   まずはサンプルを提出して、サンプルのプログラムでどの程度のスコアになるのか確認する。自分の環境でチェックプログラムを実行するのと、提出先で判定するのでは、実行環境や乱数の種が違うためどの程度の違いがあるのか把握しておく必要がある。
2. サンプルをいじってみる
   問題文を読んだだけでは詳細がわからず、何か誤解している可能性もあるので、それを確認する意味も含めて、最初はサンプルをいじってみるのが良い。この時点で、問題やプログラムを見なくても、どうやって解こうか頭の中で考えられるようにしておきたい。
3. チェックプログラムを読む
   チェックプログラムのソースコードを読んでみると問題文には書かれていない情報がたくさんある。例えば、2008年の問題では、「農園の種類が3種類ある」「桂馬のAIは他のAIよりも出現しやすい」「最終的なスコアは各対戦のスコアの合計の1/50」などがあった。コンテストのプログラムを書くにはanswer.cとanswer.hさえ見れば十分だが、その他のソースコードも重要なので必ず見ておくこと。
4. チェックプログラムを書き換える

   問題をよく理解できたら次は、自分の書いたコードを分析しやすくするためにチェックプログラムを書き換える。 例えば、チェックプログラムはログをコンソールに出力をしてくれるが、それでは変更の前後でログを比較したり、長いログを見ることは困難なので、ファイルにもログを出力するように変更する。『printf関数をラップする ［C言語]』にあるようなコンソールとファイル両方に出力する関数を作ると便利だ。さらに、出力は「/log/(バージョン番号)/(年月日時分秒).txt」というようにログフォルダにバージョンごとにファイル名に時間を付けてやると、後で前のバージョンの結果と比較がしやすい。

   その他に、2008年の問題では、プレイヤーとAIの「移動と収穫の割合」や「収穫の失敗率」などを集計したり、「n回実行した平均を表示する機能」や「タイムアウトしても最後まで実行を続ける機能」などを実装したり、ログの出力が見やすくなるように変更したりしていた。

   (※チェックプログラムを書き換えるときは、チェックプログラムがおかしくならないように注意。)

2008年の参加では実際に上記のようにした。この作業には時間がかかったが、その分の効果はあったと思う。

• ローカルで実行するのと提出先では実行環境が違う
  これが意外と重要で、この違いに苦労することが何度もあった。例えば、自分の環境ではほとんど速度の変わらない変更が、提出すると明らかに遅くなっているということがあった。逆に、自分の環境ではほとんど速度の変わらなかったのに、提出すると明らかに速くなることもあり、もし提出しなければ気づかなかった。(これは私の予想だが、提出先の実行環境がWiiであるという以外に、提出先のコンパイラではあまり最適化がされないというのがその差が生まれる理由の一つではないかと思った。)
• できるだけ速い実行環境で実行する
  点数を競うタイプの問題であれば、乱数の影響をあまりうけないようにしたり、様々な問題を解くようにするため、数回実行した平均を取ると良い。ただし、その場合、繰り返し回数を増やすと時間がかかるため、できるだけ速い実行環境で実行することで、そのコストを減らす。また、時間内にたくさん解くタイプの問題では、速い実行環境であれば制限時間を減らしてもいいかもしれない。
• 序盤の異常なスコアは不正かも？
  コンテスト序盤にはよく不正をして高いスコアを取る人がいる。それを見てそんな高い点数取れないよと諦めないように注意。不正をしていれば数日中にはランキングから突然、消える。2008年のコンテストでは、配列の範囲外アクセスをして偶然（？）に高いスコアを取った人がいたようだが、数日後に消えた。
• できるだけ速く上位に入る
  上位と大きく離されると途中で諦めてしまおうとか考えてしまうこともあるし、逆に上位にいれば抜かれそうになったり、抜かれたりしたときに頑張ろうとするので、できるだけ上位をキープしておきたい。早い時期であれば上位にも入りやすいので、早いうちに上位に入っておくようにする。
• 少し暇があるときには考える or コーディングをする
  一ヶ月以上あるのは長いと思うかもしれないが意外と短い。自分のアイデアを全て実装するには時間が足りない。できるだけ早いうちから時間を作って少しずつでも考えたり、コーディングするといい。自分の能力が足りない分は時間をかけることでカバーできる。
• 年末・年始は多くの参加者がスコアを伸ばす
  年末・年始は時間が取りやすいので多くの参加者がスコアを伸ばす。ハル研社員の参加者たちはこの時期に大きくスコアを伸ばす人が多い。中盤で上位に入っていたとしても油断しないようにすること。本番は年末・年始で、それまではフライングスタートしていると考えるのが良い。
• コンテストの最後の２、３日は評価待ち時間が長い
  コンテストの最後の２、３日は、新しくアルゴリズムを考えて実装している暇がないため、パラメータを調整したりして、細かいチューニングをすることが多い。その期間は参加者の多くが提出してくるので、その評価待ち時間が長くなる。最終日に関しては評価待ちが10件というのも珍しくない。１つ１分としても自分のプログラムが評価されるまで10分も待たされることになる。そのため、最終日にはほとんど提出できないものと考え、少し早めにラストスパートするのが良い。