ICPCの戦い方 〜d3sxpの場合〜
これは Competitive Programming Advent Calendar に投稿された記事です。
この記事では、d3sxpというチームが2007年に結成されてから、2010年の世界大会に出場するまで、どのようにして練習してきたか・戦ってきたかについて、'時系列に沿って'紹介します。
d3sxpの'最終的な'戦い方については、チームメイトのid:kamingさんが書いた記事であるd3sxpにいた頃、意識していたことをご覧ください。
はじめに
私たちがチームを結成したときは、メンバーの誰一人として競技プログラミングに関する知識を持っていませんでした。ダイクストラ法も、動的計画法(DP)も、そんな名前は聞いたことがありませんでした。そんなチームメンバが、どのように練習をして、どうやって(少しずつ)強くなっていったか。また、その時自分がどう思っていたかについて、ここに残しておきます。
以下ではd3sxpの活動を1年ごとに区切り、どのようにコンテストを戦ったか・練習したかを書き、今振り返って良かったところ・悪かったところをまとめてみたいと思います。
ちょっとその前に
ICPC(国際大学対抗プログラミングコンテスト:右ロゴ)をご存知でない方のために、簡単に説明をしましょう。
ICPCは、同じ大学の3人1組で戦うチーム戦で、TopCoderのSRMやCodeforcesのように、「解が存在し、適切なアルゴリズムを実装すれば一定時間内(3秒とか5秒とか)に計算できる問題」が3-5時間で6-10問ほど出題される、プログラミングのコンテストです。
3人1組で戦うのですが、コンピュータはチームに1台しか割り当てられません。そのため、チーム内でのコンピュータの融通や、コンピュータに向かっていない人の行動が、その結果を大きく左右する、個人戦とはちょっと変わったコンテストになっています。
日本では、国内予選が7月に行われ、そのうち27チームほどが11月頃のアジア地区予選の日本大会に進出します。アジア地区予選はアジア各地(20箇所ぐらい？)で行われていますが、そのうち日本で行われる大会に出場できる、ということです。
さらにそのアジア地区予選で優勝したり、それなりにいい成績を取ると、翌年4月ごろ行われる世界大会への出場権を得ます。日本の予選には約300チーム、世界中の予選の合計では約8,000チームが参加する、非常に大きなプログラミングコンテストとなっています。
さて、話を戻したいと思います。
登場人物紹介
- kamae (nkamae)
- miracと高校が同じ。高校時代からプログラムが良く出来る人。10年前からスマートフォンを持っていたつわもの。
- mirac (miracjp)
- kaming (bakaming)
- miracと学科が同じ。大学に入ってからプログラミングをはじめた人。実は体育系のアーチェリー部でも実績を残している。
- 3人とも: 1987年生まれ。競技プログラミングにハマった人たち。
左からkamae、kaming、miracの順。2009年のアジア地区予選東京大会にて。
d3sxp 結成前 (2006年、大学1回生)
kamaeとmiracは、(kamingとは別の)もう1人の同級生と一緒に、ku.HAKというチーム名で国内大会に参加しました。このときは3人がそれぞれ別々の問題を担当したため、コンテスト中にも関わらずコンピュータを奪い合うという事態が発生しました。最終的に1問しか解けず、見事に惨敗しました。
このように3人がそれぞれ別々の問題を担当するというのは多くのチームで採用されている仕組みだと思いますが、コンピュータが1台しかないという制約などから、各自の才能をうまく活かすことがでないと思います。これを身を持って理解したことが、私達がこの年得た大きな成果でした。
d3sxp 初期 (2007年、大学2回生)
国内予選
kamaeとmiracはkamingと出会い、3人で国内予選に参加しました。この時、昨年の失敗を生かし、ペアプログラミングを実践しました。ペアプログラミングというのは、プログラムを書くコーダーの後ろに常に誰か一人が立っていて、バグを発見・指摘したり、不明な点を聞くことで、常に2人以上でプログラムを書いていくスタイルのことです。
実際にはkamingが問題を読み、内容を噛み砕いてkamaeとmiracに伝えます。コーディング担当のkamaeがプログラムを書いている後ろで、miracがそのソースコードを随時チェックし、バグを発見・指摘する係をやりました。kamaeのプログラミングスキルが突出していたので、miracはバグを指摘する以上に、kamaeのプログラムの分からないところをひたすら質問しつづけていた気がします。
この時、誰も競技プログラミングの知識を持っていなかったので、想定解法ではない方法でゴリゴリ解いていました。例えば、崖のぼりの問題(pdf)は、典型的な拡張ダイクストラの問題ですが、当時はみんなで必死に考えた結果、DFSのような不思議なアルゴリズムで解いていました。
国内予選からアジア地区予選まで
実はこの年は、ICPCのアジア地区予選が日本で開催されるようになってからちょうど10年の記念の年だったので、アジア地区予選への出場枠がいつもの約2倍になっていました。そのおかげで、私たちのチームも運よく、アジア地区予選への出場権利を得ることができました。
kamaeのプログラミングスキルと、(特に何も考えずに実施した)ペアプロによってバグを発見しやすい仕組みが出来たこと、さらにアジア地区予選の出場枠が2倍だったという、いろんな偶然が重なって出場権利を得ることができたのかなぁと思っています。
ただ、この頃の私たちはICPCに対してそんなに本気ではなかったので、あまり練習もしておらず、まともにやった練習といえばOB/OG会が主催してくださっていた模擬地区予選ぐらいであったように思います。
アジア地区予選 東京大会
実際に出てみたアジア地区予選は、もう感動の一言でした。このアジア地区予選に参加するまで、私たちのチームはオンラインで開催される国内予選しか知らなかったわけです。いや、国内予選も面白いのですが、アジア地区予選の面白さといったら、本当にすごい。
- 例えば、日本各地のいろんな大学から、プログラミング好きな人が集まっていること。
- 例えば、開会式のチーム紹介の中で、プログラミングの話が出てきたり、アニメの話が出てきたり、とにかくみんなが本当に楽しそうにしていること。
- 例えば、“アジア”地区予選なので海外からもチームが来ていること。
- 例えば、開会式や閉会パーティーが、(一般学生にとっては)とてもとても豪華なこと。
- 例えば、コンテスト中に1問解く度に、正解した問題を表す風船が各チームのテーブルまで運ばれてくること。
文章ではあまり伝わらないと思いますが、本当に感動しました。ICPCって、すごい大会なんだなぁと。
練習を十分にしていなかったのでコンテストの結果は良くありませんでしたが、来年もこのアジア地区予選に参加できるように、一生懸命頑張ろうと、3人で誓いあいました。
アジア地区予選後
大会の1ヶ月半ほど後に、関西からICPCに参加した人々が集まって、京都で忘年会が行われました。忘年会自体もいろんな大学の人が集まっていたので、とても楽しむことができました。
また、その2次会で(ボーリング場がいっぱいだったのでスターバックスか何処かに移動したのですが)、大学の先輩であるoxyさんのお話を聞くことができました。
oxyさんは、この年のアジア地区予選で優勝されていた、本当にすごい先輩です。
この時までは会うたびに恐縮してしまい、喋ったこともほとんどなかったのですが、前年出られた世界大会の話や、ICPC関係であった面白い話などを聞くうちに、自分もICPCに本気で挑戦したい、と強く強く思うようになりました。
帰り道に、「よし、これならICPCというコンテストに大学生活をかけても良いかもしれない」と思ったことを、未だにはっきりと覚えています*1。
(余談) 今大学生で、ICPCに向かって頑張っているあなたへ
今現在では、残念ながら、アジア地区予選に参加できるチームの数はかなり限定されています。そのため、アジア地区予選で私が味わった感動を、多くの人に味わってもらうのは難しいかもしれません。
ただ、最近では東京・京都・大阪・会津などで学生主体のコンテストやキャンプが開かれたりしています。これらのコンテストは、基本的に無料ですし、参加に制限もありません。ぜひぜひ、参加してみましょう。
これらのコンテストに参加すると、ICPCという共通の目的に向かっている人に出会うことができます。また、強いチームの人々と出会って、喋って、刺激を受けることは、モチベーションの維持のためにも素晴らしいと思います。
また、東京や近畿・会津の周辺に住んでいないという人でも、twitterなどでいろんな人とコミュニケーションがとれるようになってきました。初めは恥ずかしいと思いますが、いろんな人と知り合って、会話をして、是非是非同じ目標に向かう友達を作ってほしいと思います。
d3sxp 中期 (2008年、大学3回生)
国内予選まで
やる気になった私は、形から入ろうと思い、まずキーボードを買いました。Happy Hacking Keyboard Professional2というやつで、2万円ほどするものです。いや、2万円の出費は相当痛かったです。でも、この出費によって、自分自身に気合を入れようと、そういう気持ちで買いました。 *2
このキーボードを買ったもう1つの目的は、タッチタイピングができるようになりたい、と思ったことでした。そのため私が買ったキーボードは、キーに文字が書かれていない、無刻印のものです。この頃、私はキー配置をちゃんと覚えておらず、文字を打つたびにキーボードを確認していました。しかしICPCで強くなろうと思えば、タッチタイピングが出来たほうがよいのではないだろうか、と思ったのです。
今覚えば、この時タッチタイピングを覚えたおかげで、ICPCのときだけでなく、課題や研究などでパソコンに触れるときにも、文字を打つのが大変楽になりました。*3
さて、私自身のことばかりを長々と書いてしまいましたが、d3sxpはチームとしてこの時期どうしていたか、について触れたいと思います。まず2月ごろから、毎週1回、土曜日か日曜日のどちらかに集まって、みんなで問題セットを解くことにしました。これはoxyさんのチームechizen.batがしていた練習会に参加させてもらった形です。
当時はプログラミングコンテストチャレンジブック(以下アリ本)も発売されておらず、ほぼ手探りでアルゴリズムの勉強をしていました。そんな中で、初歩的なアルゴリズムをしっかり教えてくれる人がいたことは、とても幸運だったと思います。(今の方々は、アリ本を読みながら、分からないことはwebで調べたり、twitterで知り合いに聞いたりするとよいのではないか、と思いますよ。)
なお、はじめの頃の練習会では、10問用意して5時間練習しても、3問解けるか解けないか、といったような感じでした。練習中に解けなかった問題は、echizen.batのメンバーがいらっしゃれば教えていただいたり、自分たちしかいなければ終わってからネットで解法や解答例を探すなど、復習を頑張っていました。その中で少しずつ少しずつ、アルゴリズムの知識をつけていったように思います。
実は、この練習会の中で、私たちは初めて動的計画法(Dynamic Programming, DP)というものを知りました。ICPCに参加しはじめてから1年半(d3sxpとしては半年)、私たちは動的計画法というものも知らずに、プログラムを書いていました。今の方々は、アリ本を読んでいく中でこういう必要な知識が勉強できるので、本当にいい環境になったのではないかと思います。ちなみにアリ本52ページに説明がありますので、まだ知らない方はどうぞ。
また、計算量(オーダー)の概念も、ここで初めて教えていただきました。そもそも計算量なんて考えずに問題を解いていた私たちでしたが、以降は計算量を考えるようになり、TLEを出すことも減ったのではないかと思います。
このように週1回、全員で集まって問題を解くという習慣は、d3sxp後期に入り、各自が研究室で忙しくなるまで、約2年半程度続きました。たまには休みもありましたが、単純計算で100回程度はチーム練習をしたということですね。これは最終的に、チーム戦を戦うに当たっての役割分担や、各自のメンタルモデルを作るのに役立ったのかもしれません。
このように、国内予選までは週1回の合同練習をやりながら、各自の家で自主練習をしていました。自主練習にはPKU(Peking Online Judge, 現POJ)やUVA(Universidad de Valladolid)、ある程度力がついてくるとICPC Live Archiveなどのオンラインジャッジを解いていました。
国内予選
ダイクストラ法などの基本的なアルゴリズムを身に着け、チーム練習・自主練習で問題を大量に解いた私たちは、国内予選でもかなりサクサク問題を解くことができました。
あまりに上手く問題が解けたせいで、実はこの年の国内予選について、私はほとんど覚えていません。あえていうと、最後のチョコレートを分割する問題については記憶があるのですが、これは唯一のアルゴリズムが思いつかなかった問題なので、悔しくて覚えているのだと思います。
戦略としては、この国内予選でも、以前と同じようなペアプログラミングをしていました。コーダーのkamaeも後ろで見ているmiracも、1年間で多くの問題を解いてきたので、基本アルゴリズムに関してはほとんどバグをいれずに実装できたように思います。
また、去年はただ問題を読む係であったkamingも、問題をたくさん解いて実力がついてきたので、解法が思いつくようになっていました。問題を説明してくれるときに同時に解法も教えてくれたので、とてもやりやすかったです。
アジア地区予選まで
大学の夏休み中に、OB/OG会が主催している夏合宿に招待していただきました。
夏合宿は国内予選で上位に入った10チーム程度が招待され、参宮橋(東京新宿のあたり)にある国立オリンピック記念青少年総合センターという場所で、3日から4日程度泊り込み、毎日5時間10問程度のコンテストをやるという、なかなか激しい合宿です。
私たちはこれが始めての合宿参加だったのですが、その内容の濃さだけでなく、参加者の濃さにも驚きました。いつもTopCoderなどで見ている、RedCoder(とても強い人)の方が沢山いました。また、高校生時代に数学オリンピックなどに参加した人も来ているようでした。*4
朝からコンテストをやり、夕方にコンテストの解説を聞き、夜には解けなかった問題を実装するといった、競技プログラミング漬けの数日間を送りました。また、寝る部屋がランダムに割りふられているので、寝る前に同じ部屋の他チームの人と交流したり、カードゲームをしたり、タイピングゲームをしたり、とても楽しいものでした。
アジア地区大会では(悪く言ってしまえば)周りがみんな敵だということもあり、あまり友達を増やすような雰囲気ではありません。しかし合宿では、みんな競技プログラミング好きの大学生たちなので、みんなと友達になり、モチベーションも向上し、良い経験ができたと思います。
アジア地区予選 会津大会
右図: 会津大会でのチーム写真。コーチのoxyさんと共に。
国内予選でよい成績が取れたので、もしかすると世界大会に進出できるのではないかという期待を抱きながら参加したアジア地区予選でしたが、見事に撃沈しました。
理由を考えてみると、以下のようなものだと思います。
- そもそも実力が足らなかった
国内予選でよい成績がとれたので浮かれていましたが、数年経ってから落ち着いて考えてみれば、この時の自分たちの実力は世界大会に行けるようなものではありませんでした。
よく考えてみると、国内予選の問題レベルとアジア地区予選の問題レベルにはやはり違いがあります。私たちは練習で簡単な問題をたくさん解いていたので、国内予選の問題は上手く解くことができましたが、アジア地区予選の問題を一人で解くほどの実力はまだついていなかったのでしょう。
しかし実力のなさを考慮しても、結果と後味が悪すぎました。その理由は以下の3点だと思います。
- きちんとペアプロをしなかった
国内予選もいい成績だったし、そろそろ実力がついてきたんじゃない？と勘違いして、今までの大会に比べて適当なペアプロをしていました。今までは常にコーダーの後ろでチェックしていたのですが、「この辺は簡単だからいいよね」とか、そういうことをしたのですが、結果的にバグを量産していました。
- よそから持ってきたライブラリを理解せず使った
競技プログラミングの界隈でライブラリというと、頻出するソースコードをまとめた(ICPCの場合は紙に印刷した)もののことを指します。例えば最大流を解くDinicのアルゴリズムというものがありますが、毎回１から実装しているのは面倒ですし、特に初心者のころはバグを入れてしまう可能性があります。そこでDinicのアルゴリズムを事前に書いておいて(印刷しておいて)、コンテスト中にはそれを見て打ち込んだりすることがルールで認められています。
この年の問題を見ていると、私たちのライブラリを使うと上手く解けそうな問題がありました。そのライブラリはウェブにあったソースコードを印刷してきたもので、これを打ち込むだけでプログラムを書く量がかなり減らせることが分かりました。
しかし、実際にそのライブラリを使ってプログラムを書いてみると、出力がどうも一致しません。後で分かったことですが、この時ライブラリを作った人と私たちが思っていることに違いがありました。具体的には、物体を前から見るか、後ろから見るかの違いで、左と右が入れ替わっていたのです。
私たちはライブラリに問題があるとは思いませんから、ライブラリ以外の部分にバグがないか必死に探しました。最終的には上記の結論に達したのですが、ライブラリをきちんと理解せずに使ったために30分ほどの時間をロスしてしまいました。
- 焦っていた
もっとも大きな原因はこれです。始めの何問かが非常にスムーズに解けて、「世界大会にいけるかもしれないし、頑張っていっぱい解かないと！」と思ってしまいました。そのせいで、ペアプロも適当になったし、ライブラリも理解せずに使ってしまいました。また、3人の間であまり意思疎通が取れておらず、各自が各自のことで手一杯になっていた気がします。
結果として、私たちの2回目のアジア地区予選は、私たちの期待には程遠い結果に終わりました。しかしこの時、私たちは大切なことを学びました。
-
- ペアプロはちゃんとすること
- ライブラリはしっかり理解して使うこと
- 焦らないこと
この大失敗が無ければ、おそらく翌年も同じコトを繰り返していたでしょう。これに気づけたことが、この年会津大会に参加して得たもっとも大きなコトだと思います。
アジア地区大会の翌日
大会の翌日に、他のチームやコーチと交流するためのエクスカーションがあり、会津若松の鶴ヶ城などをめぐりました。その際、バスでの移動中にOBさん方と話す機会があり、自分が思ってもいなかったことを聞きました。
それは、「実力は解いた問題数に比例する」というものでした。当時の自分は全く信じていませんでした。だって単純な問題を解くのと、難しい問題を解くのでは、全く1問あたりの重みが違うだろう、と思ったからです。
しかし、いろいろ話を聞いていくうちに、どうもだいたい正しいようだ、と思ってきました。例えば世界大会に行ったあるチームのメンバーは1年に何百問解いたとか、あの人は今まで千問解いたとかいう話でしたが、どうも問題数と実力に大きな相関があるように思えたのです。
これはおそらくですが、ある程度問題を解いて強くなってくると、簡単な問題では満足できなくなって、どんどん難しい問題を解くようになっていくのではないでしょうか。ということは、「たくさん問題を解く」という単純なことを頑張るだけで、実力をどんどん向上させることができるということです。
アジア地区予選で惨敗して落ち込んでいた私でしたが、こういう話を聞いて、またやる気が出てきました。1人で1000問とけば世界大会に行けるだけの実力がつくと聞いたので、「来年は1000問とくぞ！」と、決意を新たにしました。*5
大量の問題を解いた今、改めて考えてみると、やはり「実力は解いた問題数に比例する」は正しいのではないかと思います。「線形じゃなくてlogだ」とか、「√に比例だ」とかいう人もいますが、少なくともたくさんの問題を解いた人は、「問題を解けばとくほど実力が上がる」ことを経験しています。
私の場合は、まず問題を解くことによってバグを出す回数が減りました。これは、プログラムを何度も何度も書くことによって、バグを出しやすい部分が分かり、気をつけるようになったのだと思います。
さらに問題を解くと、プログラムを書く時間が短くなってきました。これはタイピング速度が上がったということではなく、「どういうプログラムにしようかな〜」と悩む時間が減ったということです。これもやはり大量の問題を解いたことによる慣れだと思います。
さらに問題を解くと、あまりに簡単な問題では満足できなくなり、ある程度以上難しい問題しか解かないようになりました。また、知らないアルゴリズムの話を聞くと、それをwebで調べて習得するようになりました。以前解けずに諦めていた問題が解けるようになってきたのも、この頃だと思います。
このように、「問題を解けば解くほど実力が上がる」のは本当だと思います。1日に1問とくだけで、1年後には365問解いたことになります。これは国内予選を難なく突破できる問題数です。また、それを2年・3年間続けると、730問、1095問となっていきます。ここまでくれば、アジア地区予選を突破しうる実力がついているのではないか、と私は思います。*6
大学3回生の頃のまとめ
- 週に1度のチーム練習を開始。個人練習も盛んに。
- アジア地区予選で惨敗。以下のコトを学ぶ
- ペアプロミングをちゃんとする
- ライブラリは理解して使う
- 焦らない。焦っても何も良いことはない
- 「実力は解いた問題数に比例する」と聞き、やる気になった
d3sxp 成熟期 (2009年、大学4回生)
国内予選まで
「実力が解いた問題数に比例する」と聞いた私たちは、とにかく大量の問題を解くことに決めました。人によって目標に違いはありましたが、年間で一人600問〜1000問解こう、と誓いました。
目標達成度をはかるために、右図のようなグラフを用意しました。横軸は正月からの日数で、次のアジア地区予選までの約300日が対象です。縦軸は各自の目標到達率で、私の目標は1日3問、300日で900問だったので、横軸の1が900問の1%、つまり9問に対応します。
緑線がコンスタントに目標を達成するためのラインで、赤線が目標進度から5%遅れていることを示すラインです。一人ひとりの進捗を示す折れ線がこの赤線まで下がらないように、頑張って毎日問題を解いて、年間目標を達成しようね！と話し合っていました。
開始してから20日、1月20日ごろまでは非常に順調に進みました。私は1日3問を解き続け、他の人も目標どおりか、5%遅れの赤線にはぶつからず、目標達成に向かっていました。その頃、私たちの使っていたPKU(今のpoj.org)が10日ほどダウンするということもありましたが、2月の末までは目標進度通り、または5%遅れぎりぎりぐらいの進度を保つことができました。
この間、私たちの実力は素晴らしく向上しました。毎週のチーム練習で、さまざまな地域の地区予選(アジア地区予選とか、ヨーロッパ地区予選とか)の問題を解いても、それなりに解けるようになってきたのです。(60日目までの成果：右図。)
また、先ほど書いた「バグが減ってきた」「コーディングが早くなった」などの効果が見られたのもこの時期です。大量の問題を解くことで、実力が向上してきたのを感じることができました。
しかし、そのまま上手くは行きませんでした。1日3問のペースで60日以上解き続けてきた私は、疲れてしまいました。1月は授業や期末テスト、2月3月はバイトをしながら目標を目指していた私たちでしたが、なにぶん目標が高すぎました。みんな飽きたのです。
こんな理由で、私たちの1年間で1000問計画は頓挫しましたが、こんな中でも、チーム練習は続けていました。チーム練習は個人練習とはまた違った面白さがあります。また、少なくともチーム練習さえ出ていたら、毎週コンスタントに何問かは解いているわけですから、個人練習をサボっても実力の維持はできるかなぁといったような意味もありました。
国内予選
1年間で1000問解くという計画は頓挫しましたが、それでも各自が短期間に150〜250問解いたわけですから、私たちのチームはかなり好成績を収めました。結果だけみても国内4位で、東大を除くと、上には昨年世界大会に行った会津大学しかいません。
また、会津大学との差もわずか9分。最後の幾何もほとんど実装が終わっていて、誤差の処理にさえ成功すれば*7提出できる状態だったので、このままの調子で頑張れば今度こそ世界大会にいけるのではないかと再確認した国内予選でした。
この時にどういう戦略をとったのか覚えていないのですが、
以前の戦略とは違い、おそらく
- kamaeがプログラムを書いているときにkamingが後ろでチェックする。その横でmiracが次の問題を紙に実装しておく。
- 問題が解けたらmiracがコーディングに移り、その際にはkamingが後ろでチェックする。kamaeは次の問題を紙に実装しておく
という、ダブルペアプロ体制に移行したのではないかと思います。
kamingは大学からプログラミングを始めたので、この前年までは他の2人に比べて実装力が弱かったのですが、この年ぐらいからkamingもかなり強くなってきたので、このようなダブルペアプロ体制が実現しました。
ICPCではパソコンがチームに1台しか与えられませんが、この体制だとパソコンが常に有効に使えます。また、我々が大事だと感じてるペアプロもきちんと出来ているので、これ以降はずっとこの体制を基本として戦いました。
アジア地区予選まで
この年も夏合宿に呼んでいただきました。
同じような内容になるので詳細は省略...
アジア地区予選 東京大会
国内予選でも良い成績が残せたので、この年は本当に世界大会を狙っていけるのではないかと思っていました。
しかし前年、世界大会を意識しすぎて力んだり焦ったりしたという失敗があったので、「世界大会のことは意識せず、とにかく1問1問落ち着いて解こうね」と開始前に話し合ったりしました。
また、コンテスト中も「落ち着いていきましょー」とか、「ゆっくり解いたらいいよー」とか声をかけ合って、前回の失敗を繰り返さないように、みんなで平常心を保てるように、心がけていました。
また、中盤で順位表を見たとき、他の大学に負けていて、かなり焦ったことがありました。そこでも敢えて「１問１問解いていけば必ず逆転できるから落ち着いていこう」という声かけをしあった記憶があります。*8
結果的に、10問中7問を解く事ができました。
10問のうち2問は(確か)トップ２チームしか解けていなかったと思いますし、
8問目の問題もあと１０分ぐらいあれば実装が終わっていたはずなので、かなりいい勝負が出来たと思います。
順位も、東大2チーム・海外3チームに続く６位に入ることができました。
これは、
- 大量の問題を解いて、実力を高めたこと
- コンテスト中に落ち着けるように、みんなで気をつけたこと
が身を結んだのだと思います。
アジア地区予選後
海外の大学を除いた、日本の大学でのランキングでは東大に次ぐ２番目に入ったということで、世界大会にいけるかもしれない、という希望が見えてきました。他の国で開催されているアジア地区予選との兼ね合いで、全大会の終了後に決定されるのですが、最終的に世界大会への進出が決まりました。とても嬉しいかったと同時に、応援してくださった方にちょっとは恩が返せたかなぁと思ったのでした。
その後、世界大会(翌年2月に中国ハルピンで開催される)への飛行機を予約したり、大会への飛行機代の補助を頂くための手続きをしたりしました。チームのみなが4回生だったので、ちょうど卒論を書く時期ではありましたが、時間を見つけて練習をしたりしました。
d3sxp 後期 (2010年、修士1回生)
世界大会
この年の世界大会は2月に中国ハルビンにて行われました。3人とも卒業論文の締め切りが同じ時期にあったので、事前に満足いくだけの練習ができなかったのですが、せっかく参加させてもらえた世界大会なのだから、精一杯がんばろうと、3人で言っていました。
アジア地区予選に初めて参加したときもそうでしたが、世界大会に初めて参加したときも、その感動はすごいものでした。規模も大きいし、ホテルも豪華だし、イベントもたくさんありました。
(写真1枚目:雪文字彫りコンテストの成果物 2枚目:ハルビン氷祭りの風景:氷の中に蛍光灯を通しているらしい 3枚目:コンテスト会場に入る前にあった金属探知機 4枚目:コンテスト終了後の会場の様子)
世界大会には4・5日間のスケジュールが組まれていて、本番は最終日の前日にあります。
本番の日の前に数日間の余裕があるのは、遠くからきたチームのための時差調整のためだと思います。その期間には様々なイベントが計画されていて、別の国のチームと組んで雪文字を彫ったり、ハルビンの雪祭りを見に行ったり、楽しませてもらいました。
大会本番では、ウェブ中継に加えて地元TV局のカメラが乗り込んできていて、ここが大きな舞台であるということをひしひしと感じました。いつもどおり、「焦らず」「落ち着いて」とお互いに口にしてはいましたが、やはり空気にのまれて始めの1時間は焦っていたようです。
なかなか1問目が通せず、うちのチームには珍しく誤答を出してしまいました*9。それも4回は出してしまったように思います。まぁ、その犯人である、焦っていた人は他ならぬ自分なのですが...他の2人には申し訳ない。
これではいけないと誰かが気づき、声掛けが行われ、いつも通りの空気を取り戻したころから、ちょっとずつ問題が解けるようになりました。開始100分でやっと始めの1問を通し、180分、210分、230分、そしてラスト30分に1問と、計5問をとくことができました。
ただ、5問解いたチームはかなり多く、自分たちとしては満足いかない結果でした。それでも多くの方々に応援していただき、お疲れ様との声もかけていただいて、とても嬉しかったです。本当にどうもありがとうございました。
なお、このときの戦略もダブルペアプロで、kamae+kamingのペアプロと、mirac+kamingのペアプロを交互にやっていました。やはりd3sxpという１つのチームで長く戦って、最終的にたどり着いた形かなぁと思います。
その後
年齢の制限から、この年の6月に始まる国内予選から先が、僕たちにとって最後の1年となりました。前の1年間でダブルペアプロという手法が確立していましたし、d3sxpとして特に新しいことは無かったので、これ以降の1年間に関する記述は省略しようかと思います。
まとめ
ここまでずいぶん長々と、自分と、自分のチームのことを書いてきました。これだけだとほとんど役に立たない文章なので、自分たちが思っていたこと、または「今からICPCに挑戦する人はこうしたらよいのでは？」というのをまとめてみたいと思います。
教訓
- 「とにかく沢山の問題を解くべし。実力は問題数に比例する。」
- 「練習どおりに本番を迎えるべし。焦っていいことは全くない。」
大会の戦い方
- アジア地区予選でも、国内予選でも、とにかく楽しむ。
- 焦らないこと。慌てないこと。いつも通り戦うのが一番。
大会中のプログラムの書き方
練習方法
- 初期(〜100問ぐらい): 簡単な問題で良いので沢山解く。バグを減らす練習。
- 中期(〜300問ぐらい): 解けそうな問題に挑戦してみる。頻出アルゴリズムを勉強する。
- 後期(〜600問ぐらい): 各地の地区予選の問題に挑戦してみる。いっぱい解く。
- それ以降: もう自分なりの練習方法が身についているだろうから、それで頑張る。
アルゴリズムを勉強するには
おわりに
長い文章になりましたが、ご覧頂きどうもありがとうございました。
何かの役に立つか、誰かの心に少しでも残れば、嬉しく思います。
初めにも書きましたが、ICPCを同じチームで戦っていた、kaming さんも記事 (d3sxpにいた頃、意識していたこと) を書いています。自分は時系列に長々と書きましたが、kamingさんの記事ではd3sxpが気をつけていたことが短く綺麗にまとまっているので、良ければどうぞご覧ください。
宣伝
最後に１つ宣伝です。関西圏の競技プログラマーが集まって、忘年会をしませんかという企画を立てました。この記事はチーム戦ということでICPCメインの記事でしたが、ICPCをやっている学生だけでなく、ICPCに興味のある高校生、仕事をしながら競技プログラミングをされている方など、いろんな方と交流したいと思っています。
もし興味があれば、こちらをご覧いただき、登録または仮登録していただけると嬉しいです。元々は同日に東京で企画されていた会のパクリなので、東京近郊の方は元ネタの方をご覧ください。
これらの飲み会は、決して仲間内の飲み会ではなく、全ての競技プログラマーのために開催されている飲み会です。学生でも社会人でも、強くても強くなくても、実はやったことなくてちょっと興味があるだけでも、誰でも参加できます。ぜひぜひ参加して、友達を作って、楽しんでほしいと思います。
*2:大きな出費をして買ったキーボードでしたが、Happy Hacking Keyboardは結構高さがあるので、初めのうちは手首が痛かったです。数ヶ月ぐらいはアームレストを置いたりして我慢して使っていた気がします。そういえばいつからか気にならなくなりました。慣れたのかな？
*3:文章入力のためのタッチタイピングと異なり、プログラミング用のタッチタイピングでは、記号も含めたほとんどのキーを暗記する必要があります。これは本当に大変でしたが、でもそのおかげで、今不自由なくプログラムが書けているのだなぁと思います。
*4:今でこそ私もRedCoderの仲間入りをしていますが、当時はまだ青コーダーでした。(http://community.topcoder.com/tc?module=MemberProfile&cr=22691154)
*5:一応、例外があることにも触れておかなくてはいけません。頭が非常によく切れ、初めからプログラミングも得意な人の場合には、200問ほど解けば十分戦える方もいらっしゃるとのことです。しかしまぁ私はそんな人ではなかったので、問題をたくさん解くことにしたのでした。
*6:私個人のアカウントを調べてみると、PKU500問、UVA100問、live archive200問ぐらい解いているようです。 チームのアカウントでは、PKU300問、live archive300問ぐらい解いているようです。チーム練習で1/3の問題を自分が解いたとすれば、この3つのオンラインジャッジ上で1000問ぐらい解いているようですね。本当に強い方になるとPKUだけで1400問解いている先輩もいらっしゃいますし、まだまだ強くなるには練習が足りないなぁという感じです。
*7:まぁそこがこの問題の肝だったので、そう簡単ではありませんが
*8:コンテスト終了後に、自分たちの前に座っていたチームから、「後ろから時々『落ち着いていこう』とか聞こえるからびっくりした、いい雰囲気で良いなぁと思った」と声をかけてもらいました。
*9:うちのチームは完全ペアプロ主義なので、WA(Wrong Answer)を出すことはほとんどありません。WAが出ると精神的にも良くないので、気をつけているのです。詳細はid:kamingさんの記事をご覧ください
ICPCの練習方法
※ ICPC(国際大学対抗プログラミングコンテスト)に出たいけど、
強くなるには何をしたら良いのか分からない、という人向け。
自分の考えでは、ICPCの競技者は以下の４段階に分かれます。
初級者レベル：プログラミング自体を学んでいる人
中級者レベル：基本的なアルゴリズムを学んでいる人
上級者レベル：様々なアルゴリズムを学んでいる人
最上級レベル：様々なアルゴリズムを自由に応用できる人
競技者レベルが異なれば、理想的な勉強の方法が異なるので、
以下では各レベルに応じた勉強方法を簡単に紹介したいと思います。
・初級者レベル
以下のような人たちが、このレベルに該当します。
・プログラミングができない
・関数を使ったプログラムが書ける程度
このレベルの人の勉強法：
・プログラミング本を１冊買って、実装しつつ学習
・サンプルコードを書きかえて、出力を少し変えてみる
・分からないことはすぐに質問する
(身近にプログラミングできる人がいると楽)
・中級者レベル
以下のような人たちが、このレベルに該当します。
・簡単なプログラムが自由に書ける
・BFSやDFSというアルゴリズムを知っている
このレベルの人の勉強法：
・ひたすら簡単な問題を解く：目標は100問！
・基本的なアルゴリズムの本を買って、勉強してみる
(ソースコードが載っている本がおすすめ:アリ本の2章など)
・どうしても解けない問題は、ひとまず放置しておく
(身近に強い人がいれば、聞いてみると良い)
コメント：
プログラミングができる人は、とにかく問題を解きましょう。
たくさん問題を解くことでプログラミングに慣れ、
バグも出にくくなるはずです。
本で学習したアルゴリズムを使って問題が解けるようになると、
どんどん競技プログラミングが楽しくなってくると思います。
・上級者レベル
以下のような人たちが、このレベルに該当します。
・Union-FindやFenwick木を何も見ずに実装できる
・最大流問題や幾何問題を解くプログラムが書ける
このレベルの人の学習法：
・ひたすら大量の問題を解く：目標は1000問！
・アルゴリズムが思い浮かばない問題も考え続ける
(身近に強い人がいれば、互いに相談してみる)
・どうしても分からないときは解答を見て勉強し、
次に類題が出た時には必ず解けるようにする
コメント：
このレベルになると、書店の簡単なアルゴリズム本では
満足できなくなってくると思います。
BBSやアルゴリズム紹介ページを利用して、
様々なアルゴリズムを身につけていきましょう。
・最上級レベル
以下のような人たちが、このレベルに該当します。
・各種アルゴリズムを組み合わせて問題が解ける
・むしろ自分でアルゴリズムが提案できる
私より上のレベルの人に言えることはありません…。
ちなみに自分はこんな感じで勉強しました。
(初級者レベルだったころ)
・C言語を勉強する
・時間をかけて簡単な問題を解く
・C++言語のSTL(vectorとか)を勉強する
・ひたすら簡単な問題を解く
(このあたりから中級者レベル)
・BFSやDFSの基本的な書き方を勉強する
・ひたすら簡単な問題を解く
・ひたすら問題を解く
(このあたりから上級者レベル)
・分からない問題の解法を調べ、アルゴリズムを学ぶ
・ひたすら問題を解く
・ひたすら問題を解く
・ひたすら問題を解く
(未だに最上級レベルには達してないですが...ｗ)
色々書きましたが、
中級者レベル以降の競技者にとって重要なことは、
"問題をとにかくたくさん解く"ということです。
初めのうちは信じられないかもしれませんが、
"解いた問題数と実力は比例する"という人もいます。
1日1問、もしくは2問解くことを毎日続けていけば、
半年後には自分でも驚くほどの実力がついていると思いますよ。
継続は力なり、、頑張ってください。
ACM/ICPC アジア地区予選 2010 韓国(デジョン)大会 参加メモ
先週末、miracを含むチームd3sxpは、
ACM/ICPC Asia Regional Contest 2010 Korea(Daejeon) Site
に参加してきました。
韓国大会に関する情報はあまり多くないので、
将来参加される方のためにも、少し情報を残しておこうと思います。
ほぼ箇条書きなので面白くないかもしれませんが...
自分の感想などは別のポストで。
注意:
当然のことですが、ここに書いてある情報が最新であるとは限りません。
実際に大会に参加される場合には、各自よくご確認をお願いします。
全般:
公式ページ: http://acm.kaist.ac.kr/phpBB3/ (ウィキ形式)
大会の1-2週間前に、情報が一気に追加される。
参加する場合には過去数年の情報を確認しておくと良い。
参加チーム数: 80チーム (うち国外から4チーム？)
費用:
総費用: 60,000円(一人当たり)
(大雑把な内訳)
航空券代: 35,000円
ホテル代: 10,000円
交通費: 5,000円
飲食費: 5,000円
その他: 5,000円
参加登録:
国内予選に登録するのと同じようにコーチに登録してもらう。
(cm.baylor.eduのページから、"Regional Finder"をクリックして進む)
国外チームは1大学から1チームしか受け付けていないようなので注意。
式典/コンテスト中:
式典: 韓国の国内プログラミングコンテストを兼ねているらしく、
開会式や閉会式は韓国語で行われる。
最後の公式な順位発表は英語で行われた。
プラクティス時: アナウンスは韓国語と英語で行われた。
コンテスト中: 放送によるアナウンスは(おそらく)行われなかった。
バルーン: 本番中は色と問題の対応関係が公開されない。
(順位表もチーム名と正解問題数が書かれているのみで、
どの問題が解かれているか分からないようになっている。)
コンピュータ環境:
OS: Windows 7
キーボード: 韓国用キーボード (ほとんど英字配列と同じ)
持ち込みも可能 (問題が生じた場合には自己責任、とのこと)
その他: 我がチームはコマンドプロンプト, g++, gvim で頑張りました。
Visual Studio 等が使えるようです。詳しくは公式ページを。
問題:
数値の下限・上限などの制約も、不足なく書かれている。
過去問は公式ページにて参照可能。
公式入出力・想定解法などは公開されず。
(live archiveで2001年と2007年の問題のみジャッジ可能)
ライブラリ:
片面30ページ(または両面15ページ)で、複数部持ち込み可
前日のチーム登録時に預け、大会の開始直前に返却される。
(前日のプラクティスの際に配られた資料に「ライブラリは片面25ページ」
と書いてあって焦りましたが、どうやらミスプリントだった模様。)
その他:
宿泊: ホテルの紹介はあるが、各自予約・支払いをする。
交通費: おそらく補助なし
エクスカーション: なし
本番前日(1日目): 15:00ごろ集合して登録/プラクティス。18:00ごろ解散。
本番当日(2日目): 9:00ごろ集合して本番。夕食に満足した人から帰宅。
おまけ:
・韓国への入国方法は、
1. インチョン空港へ (ソウルまでバスで1時間ほど)
2. ギンポ空港へ (ソウルまでバスで40分ほど?)
3. プサン空港へ
4. どこかの港へ
の4通りぐらいだと思います。
・国内主要都市は大体、最高時速300kmの電車KTXで結ばれています。
・タクシーの運転手さんはほとんど英語が喋れないので、
印刷した地図を(できれば韓国語表記のものを)持っていきましょう。
謝辞:
初めて海外のアジア地区予選に参加するにあたり、
@WtbHさん・@iwiwiさんには様々な情報を頂きました。
また、現地では@xoancerさん・@neoevokeさんの協力をいただきました。
チームメイトやコーチ、上記の方々をはじめ、
助言や応援を下さった多くの方々に感謝したいと思います。
開設
してみました。
