情報オリンピック参加者の皆さんへ
情報オリンピックに参加した皆さんこんにちは。僕はqnighyです。一応すごい人です。
予選で終わってしまった人も、本選で終わってしまった人も、これから合宿に行けるという人もいると思いますが、これ以降も競技プログラミングに精進したい！という人のために、いち競技者としての経験から、ちょっとアドヴァイスを書いていきたいと思います。(僕自身実践できていないものもあります。)
いろいろな大会に参加しましょう。
情報オリンピック以外にも、さまざまな競技プログラミングの大会が存在します。その一例を挙げますから、ぜひとも臆せず参加してみてください。
大会に参加したり、練習したりしないと、競技プログラミングの腕は上がらないようです。
SuperCon
東工大と阪大が主催する高校生向けのコンテストです。このコンテストの最大の特徴は、大学のスーパーコンピューターを借りてコンテストを行うということです。
SuperConは、主として厳密解の求まらない難しい問題をスーパーコンピューターの怪力と自分たちのコーディング力を使ってガリゴリ解く感じです。1チームは2,3名で、1問を約4日間かけて解くという、ビッグな問題構成です。
プログラミング言語はCです。
6月頃に予選問題が発表されるのでメールで提出し、選ばれた約20チームが8月にいずれかの大学にて本選に参加する、というスケジュールです。
Supercomputing Contest - Supercomputing Programing Contest Official Site
パソコン甲子園 プログラミング部門
会津大学が主催する高校生向けのコンテストです。後述するICPCを意識したものと思われます。賞金がとてもおいしいです。
1チーム2名で、10問以上ある問題を短い時間で解きます。近年はその場で正誤判定が出る仕組みのようです。
7月頃に申し込み、9月に各校で予選を実施し、11月に会津大学で本選が開催されるというスケジュールです。
Google Code Jam
Google社が開催している一般向けのコンテストです。インターネット上で受けられます。オンライン予選ののちどっかの国に招待されますが、18歳未満の場合オンライン予選まで受けられます。
GCJは任意のプログラミング言語で受験できます。
問題は3〜4問ほど出題され、入力をダウンロードしてから規定時間以内に出力ファイルをアップロードします。ちなみに問題文は英語です。
5月頃から予選が3次まで開催され、それを通過すると7月にオンサイトに出場できます。
また今年はGoogle Code Jam Japanが開催されるようです。こちらは一見したところ日本語で受けられるようです。
TopCoder SRM
TopCoder社が定期的に開催しているオンラインコンテストの1つです。インターネット上で受けられます。TopCoderの最大の特徴は、Challengeという独特の仕組みにあります。最近似たようなコンテストは増加しているようです。
問題は3問出題され、75分間という短い時間で解きます。正解の場合には解くのにかかった時間に応じて点数が貰える仕組みですが、もう1つ得点を得る方法があります。それがChallengeです。
コーディングが終わると、他の人のコードが見られるようになります。そのときに、誰よりも早くバグのあるコードを発見し、それを指摘することで得点を得ることができます。
この特徴的なシステムのおかげもあって、TopCoderはプログラマーのためのネトゲとして高い評価を受けているようです。
問題点は、問題文が英語であることと、日本においてはほぼ深夜か昼間に開催されるので、学生にはやや辛いということです。ただ、問題文はかなり平易な英語で書かれていますし、Yahoo!翻訳でも十分対応できるようです。
Programming Contests, Software Development, and Employment Services at TopCoder
ACM/ICPC
ACMというコンピューターの学会が毎年開催している、由緒正しい伝統的なプログラミングコンテストです。
ICPCは「大学対抗プログラミングコンテスト」の略であり、その名前が全てを物語っています。
オンラインジャッジを活用しましょう。
オンラインジャッジとは、ソースコードを提出すると正誤を判定してくれるWebサイトのことです。
これを使えば、大会が無いときでも、簡単に練習することができます。
代表的なものを挙げます。
POJ (PKU JudgeOnline)
北京大学が運営しているオンラインジャッジです。ICPCで出題されたものを中心に、2000個を超える問題が掲載されています。
問題は英語で掲載されていますが、一部は有志によって翻訳
情報を集めよう
Twitterなどの便利なツールによって、今や優秀な参加者の多くが情報発信をしています。彼らの情報に耳を傾けることは、意識の向上にも繋がるかもしれません。ちなみに僕のTwitter idは@qnighyです。
ただ、余計な情報も多いような気がしますから、駄情報の波に溺れるくらいなら見ない方がましかもしれません。僕は溺れています。
情報を発信しよう
「情報をアウトプットしただけ、人間は成長する」みたいなことを言っている人もいます。まあそこまで正しいかはわかりませんが、書くに越したことはないでしょう。「情報を発信するところに、情報は集まる」とも言います。
せめて、大会に参加した記録くらいは、ブログに書いて欲しいものです。それを見てにやにやするのが僕の趣味ですから。
蟻本を買おう
↓これです。
- 作者: 秋葉拓哉,岩田陽一,北川宜稔
- 出版社/メーカー: 毎日コミュニケーションズ
- 発売日: 2010/09/11
- メディア: 単行本（ソフトカバー）
- 購入: 52人 クリック: 1,402回
- この商品を含むブログ (80件) を見る
高いのは専門書ですから我慢しましょう！
コンテスト中の具体的な戦略
だいたい言うことは言ったつもりなので、あとはコンテスト中の具体的な戦略としてありがちなことをメモっておきます。
必ず部分点は取ろう
ありがちなのが、満点解法が思いつかないときに、部分点すら捨ててしまうことです。
部分点に泣くのは悲しいことですから、取れる部分点は貪欲に取りましょう。
二分探索
最大値を求める問題では、二分探索を疑いましょう。二分探索を適用した場合、増えるコストはたかだか20倍程度ですから、とりあえず二分探索ありで考えればいいと思います。
注意しなければいけないのは、二分探索が実は適用できない場合です。「aで可能なときは、a-1でも可能」が成立するかを、きちんと確認しないといけません。
グラフ
グラフはいくつかの著名なアルゴリズムを覚えておきましょう。覚えるには実装するのが一番です。
「深さ優先探索」「幅優先探索」「Dijkstra」「Warshall-Floyd」「PrimまたはKruskal」「トポロジカルソート」「強連結成分分解」などは覚えておくとよいでしょう。また、余裕があればさらに「反復深化」「Bellman-Ford」「橋」「関節点」「最小共通先祖」など、覚えるべきものはいろいろあります。
データ構造
通常、優先順位つきキューやSet,Mapはプログラミング言語付属のものを使用すればよいでしょう。ただ、これらの実装方法を知っておけば理解が深まるかもしれません。データ構造ではありませんが、ソートアルゴリズムについても同様です。
情報オリンピックでよく書く必要があるのが、Union-Findおよび、多様なSegmentTreeです。
SegmentTreeのなかでも、和クエリを実現するBIT(Binary Indexed Tree)および最小値クエリを実現するRMQ(Range Minimum Query)は頻出のようです。また、JOI合宿の過去問で2度出現した、通称「Starry Sky Tree」が組めるようにしておくとかなりグッドです。
証明とテストをしよう
人間はアホなので、適当に書くと一定確率でバグに当たります。
1つめは、それで正しく動作するかどうかを、数学的に証明できること。証明を実際に書かなくても、頭の中で証明できるようになるとグッドです。
2つめは、自分でテストケースを作ってテストすること。コピペミスによるバグとかも怖いですしね。これをするかしないかでバグの検出率はかなり変わると思います。
バグ…悲しいですよね…
オーダーの推測をしよう
- N = 100000なら、O(N log N)の線が濃厚です。
- N = 1000なら、O(N^2)の線が濃厚です。
- N = 100なら、O(N^3)あたりでしょうか。
- N = 20なら、O(2^N)とかO(2^N*N)などが考えられます。
問題文の条件から貪欲に情報を読み取り、推理するのも、競技プログラミングの大事な能力です。
まとめ
気合があればなんでも出来ます。大丈夫です。問題ありません。Don't worry, be happy.
