kagamihogeの日記

kagamihogeの日記です。

目指せ!プログラミング世界一―大学対抗プログラミングコンテストICPCへの挑戦

プログラミングでたいせつなことはすべて ICPC で学んだ。そういっても過言ではないくらい、ACM/ICPCACM/International Collegiate Programming Contest)国際大学対抗プログラミングコンテストは俺のプログラミング感に影響を与えている。書店でこの本を見つけたとき、経験者としてこれは書籍感想を書かざるを得ないだろうと思った次第です。ちなみに本書はサラッと流し読みした程度で、ある種の衝動に突き動かされるようにこのエントリを書いています。

ACM/ICPC とは、プログラミングコンテストの一種です。制限時間内にどれだけ多く、どれだけ早く問題を解いたかをチーム単位で競うものです。大学対抗と銘打ってあるとおり大学生を対象としています。チーム単位で、と書いた通り、コンテストには 3 人のチームで臨みます。更に 1 チームには 1 つの PC しか使うことが出来ません。ここが ICPC の大きな特色のひとつで、個々人が高い能力を持っていれば有利なのは勿論のこと、チーム戦の要素があります。そのため、チームを活かすことがより上位を狙うキーポイントでもあると同時に、個人の能力が上位チームのそれに比べて劣っていても上を狙うチャンスがある、ということでもあります。

ところでお前はどの程度の成績残したんじゃい、ってトコですが、俺の所属していたチームはアジア地区予選にギリギリ出場できた程度の能力です。しかも俺はチーム内で一番プログラミング能力がヘボかったという始末。他 2 人に連れて行ってもらったようなモンですね。ただ、先にも書いたとおり ICPC はチーム戦なので、そんな俺にも役目があったのです。

俺の居たチームのコーチ(所属研修室の教授)は、チームには 3 つの役割がある、という戦術方針を立てていた。それぞれ、プログラマ・リーダー・デバッガ。プログラマは、1 台しかない PC を使用してとにかくスピード重視で問題をコーディングする人。アイデアを即コードに落とし込む能力が問われるためチームの要となる。リーダーは、Reader と Ledaer を兼ねている。問題を読み込んでその意味や、解くために必要なデータ構造とアルゴリズムの方針を組み立てる。また、誰に問題を解いてもらうか・読んでもらうか・ペアプロが必要か、などの状況判断を行う。デバッガは、プログラマと一緒に―プログラマの要請、リーダー・デバッガの判断に応じて― PC に向って細かいミスの発見―変数の初期化漏れなど、焦っていると見落としがちなものの処置―や問題の読み違えや読み落としの実装漏れの指摘を行う。

チームが 3 人なので、それぞれがそれぞれの役割をずっと担当するかというとそうでもない。状況に応じて誰がどの役割の帽子をかぶるかは常に変動する。プログラマが問題を解き終わって PC が空いたら、その人は別の問題を解くための準備に入る。そして、プログラマが問題を解いている間に目安のついた問題があればリーダーかデバッガが PC に向う。誰がどの問題を解くかの判断も、一応はリーダーが音頭を取るけども、合議で行う。

ちなみに俺は 3 人の中でプログラミングの速度が最も遅かった。なので自然とチーム内で役割分担が生まれていた。最も手が早い A 君は、プログラマ・リーダー・デバッガの割合が 8:1:1 ぐらい。次に手が早い B 君が 5:3:2 ぐらい。んでドンガメの俺は 1:4:5 ぐらい。俺はコンテストの時間中はほっとんどキーボードに向ってなかったです。なので、正直、足を引っ張っているんじゃないか……と何時も思い悩んでいたものです。でも、たぶんそれは間違いで、重要なのは役割に固執することではなく、チームで今必要な役割は何かを考えて、状況に応じて適切な行動を取ることだと俺は思う。

このように、ICPC はチームでプログラミングを行うことはどういうことか、ということを教えてくれた。

そして同時にドンガメではあったけれどプログラミングのたのしさを教えてくれたのも ICPC だった。ICPC は、オンラインジャッジというシステムがインターネット上に用意されている。これは Web からソースを投稿すると正解か不正解かを自動判定してくれる。ウチの研究室ではプログラミングの基礎能力向上も兼ねて、毎週教授が「(オンラインジャッジに掲載されている問題集に付けられている番号の)○番と×番解いてくるよーに」とお題を出していた。

問題を解くにはまず、当然のことながら問題文を読みこなす必要がある。図入りだと比較的イメージが沸きやすいんだけど、そうでない問題も多く、そもそもどんな問題なのかを把握するのに時間がかかることもあります。問題が把握できたら、次に方針であるところのデータ構造とアルゴリズムを練りにかかります。経験的にデータ構造のイメージが沸くかどうかが要です。アルゴリズムでカバーしようとすると、どうしてもロジックが複雑になりがちな傾向があるからです。そして、その方針に沿ってコーディング。細かいミスをデバッグで潰し、問題の仕様を満たすためのテストケースを洗い出していく。これら一連の課程で問題文の細かい見落としを発見してたり、テストケース作ってて漏れてるロジックに気付いた場合は、コーディングをやり直したり、時にはデータ構造とアルゴリズムの再構築を行います。それでも Wrong Answer(不正解のこと)が返ってくる時は返ってくる。どうしても解けないときは……問題文をイチから読み直したり、研究室の友人に「あれの解き方教えてくれ!」と懇願しにいってました。

研究室ではパズル感覚でコレに取り組んでいて、一時期は本当に夢中に Accepted (正解のこと)を求めて日夜唸り続けていた。熱中してたころは夢の中でデバッグしてたり、風呂に入った瞬間解き方思いついてずぶ濡れでコーディングしたりとか……ホント良い思い出です。

このように、ICPC はプログラミングを行うことはどういうことか、そして、たのしさを教えてくれた。

とまぁ、ICPC に対する個人的な経験を書いたのだけど、本書が出たことには賞賛の意を送りたい。というのは、研究室が ICPC に取り組んでいた当時は本当に情報が少なかったことが一つ上げられる。当時はネット上にもまだまだ文献は少なかった時代でした*1。俺が研究室に入った頃には偉大な先輩たちが苦心して積み上げたオンラインジャッジのデータがそこそこ揃っていて、随分と楽をさせて頂いた。俺が研究室に入る数年前の先輩方は、どの問題がどの程度難しいかなんて分からないので、サイコロを振って解く問題を決めていたなんて話も聞いた。ICPC を勝ち抜くには、ある程度の積み上げが必要になる。そういう背景事情を知っていることもあり、本書によって ICPC の裾野が広がることを俺も期待しています。

プログラミング能力を向上したい、という大学生は本書を手に取り、是非 ICPC に挑戦してみてください。京都大学東京大学東京工業大学クラスに太刀打ちできるほどの力は得られないかもしれません。だけど、挑戦するだけの価値は必ずあります。ICPC に取り組むことで、プログラミング能力は確実に向上するからです。

目指せ!プログラミング世界一―大学対抗プログラミングコンテストICPCへの挑戦

目指せ!プログラミング世界一―大学対抗プログラミングコンテストICPCへの挑戦

*1:この場を借りて金沢工業大学の中の人には感謝しておきたい http://pegasus.infor.kanazawa-it.ac.jp/~koblab/home/d1504310/acm/index.html