この記事は Competitive Programming Advent Calendar の18日目の記事です。

はじめに

アルゴリズムやその他の何らかのダイレクトに役に立つコンテンツは、 おそらく他の多くの方によって充実していることであろうかと思いますので、 私は大して役に立たないことを取り留めもなく書き綴ることにします。

なぜ私のような普通のプログラマが、 当時競技プログラミングの世界のトップに立つことになったのか。

競技プログラミングを考える

「競技プログラミング」という単語がにわかにWeb界隈を賑わせはじめたのは 私が知るかぎりではそんなに歴史のあるものではないと思います。 おそらく「競技プログラマ」という単語及びそれが指し示す人たちの出現と同時期に 適切な語を探す形で生まれたのでしょう。

しかし、プログラミングの技能を競うという試みは新しいものではありません。 それはICPCが30年以上の歴史を誇るということ、 そして7年ほど前に私もそこに名を連ねているということが示しています。 いわゆるProblem Solving以外にも、 プログラマたちはプログラミング技能というものを様々な尺度で 競い合ってきたのです。

  • ICPC / TopCoder / CodeJam / Codeforces - コーディングの速さと正確さ
  • Sort Benchmark - コードの速さ
  • CodeGolf - コードの短さ
  • ICCC - コードの読みにくさ
  • ICFP Contest - プログラミング言語の優位性・プログラマのアレゲさ

しかし近年で日本語の単語としての「競技プログラミング」では、 狭義的には一つ目だけを指すことが多いようです。 さしずめ狭義競技プログラミングとでもいいましょうか。 これに関して、日本ではここ数年である潮流がありました。 その出現はTopCoderに遡るかと思います。 まずはインターネットの普及、 それからTopCoderによるインターネット上での定期的コンペが 開始されたのがTopCoderの始まった2005年頃。 この頃に中学生以下だった人たちが事実上の英才教育を受ける形で、 これに関する技能を底上げしていきました。 このあたりは最近の事情に詳しい人なら説明は不要かと思います。

さて、「競技プログラマ」と呼ばれる人たちは幾つかの世代に分けられるかと思います。 日本の(狭義)競技プログラミングの源流は1990年後半にさかのぼります。 もともとプログラミングスキルの高い人達が、 その能力をたまたまICPCという形式で世界に問うていたのが 最初の世代の人達でしょうか。 コンテストの知名度の向上、それに伴い 世界への切符を争うようになった第2世代。 OBの人達によりOB会が結成され、 合宿などが開催されるようになり、 そのあたりの訓練を受けるようになった第3世代。 私はこのあたりに入るかと思います。 そして、TopCoder後の新世代。 彼らはまだ現役世代でしょうか。

いずれにせよ、いわゆる競技プログラマとしての スキルは今のところ年代を経るごとに 単調増加しているように見えます。

私とプログラミング

私がプログラミングを始めたのは、 遊び道具としてのコンピュータを作るためでした。 ゲームが好きだけど、お金が無いのでゲームは買えない。 コンピュータ(当時はマイコンと言った)を貰ったはいいが、 BASICでプログラムを書かなければ何も出来ない。 そうなると選択肢はひとつ、ゲームプログラマになるしかありません。

小学生の時からゲームプログラミングを始めて、 中学生の時は毎月1本ぐらいのペースで しょうもないゲームを量産していました。

高校に入ると、Windowsマシンを手に入れてC++を始めて、 市販ゲームと同等のゲームが作れるようになって、 それと同時にプログラムの複雑さと戦う必要に迫られるようになり、 それから興味がプログラムに関するプログラムに 傾倒してゆくのですが、それはまた別の機会に。

私と競技プログラミング

初めて私が競技プログラミングに出会ったのはSuperCon’99でした。 部の先輩がチラシを持ってきたのが知ったきっかけだと思います。 当時、競技プログラミングなんて言葉はおろか、 インターネット回線すらありませんでしたから、 図書館に通いつめてなんとか解法を考えて、 フロッピーにソースコードを詰め込んで封筒に突っ込んで郵送をした記憶があります。 それはともかく、私は当時高校2年生でしたがまさに井の中の蛙で、 プログラミングの腕に関しては高校生最強を吹聴して回っておりましたので、 まあ通らないわけがないだろうとタカをくくっていたのですが、 SuperConからは待てど暮らせど返事は来ず、 それが結局私の最初の競技プログラミングへの参加ということになりました。

それでそのまま翌年になりますが、再度のSuperConです。 私は高3になり能力も前年からかなり向上し、 念願のインターネット回線も手に入れ、 万全の体制でオンライン申込みをしました。 はたしてその甲斐はあり無事予選通過、 さらに本戦優勝という結果を残すことが出来ました。 これが私のプログラミングコンテスト最初の勝利であり、 勘違いの始まりでもありました。

ICPCとの出会い

さて、私は大学に入りました。 それで夏前に、ICPCのチラシが授業で配られたのですが、 その年は華麗にスルーしていました。 3人1組というのになにか引っかかるものを感じたといえば聞こえが良いです。 自分は強いけど、3人1組だと勝てないかもしれない。 でも本当のところは、一緒に出る人がいないでござる状態というわけで。

それで大学1年生の時は、フリーウェアの開発に精を出したり、 某商用ゲームの開発に携わったりしておりまして、 そんなことはすっかり忘れていたのです。

大学2年生になり、高校の後輩が同じ大学に入ってきて、 私は当時から目をつけていた彼をICPC誘うことにします。 それが今も交流の深い [@nushio](https://twitter.com/nushio) さんなのですが、 彼と、後もう一人同じ学科の人に出てもらって参加したわけです。 しかし、結果は残念ながら予選敗退。 大学内順位が3位だった気がします。 その時は酷く落ち込みました。 終わったあとに3人で食べた牛丼が未だに忘れられません。 それなりに自信もあったわけで。

敗因としては、

  • 予選環境がLinuxなのに、Linuxをほとんど触ったことがなかった
  • エディタがEmacsだったのに、Emacsをほとんど触ったことがなかった
  • 予選環境が英語キーボードなのに、英語キーボードを触ったことがなかった
  • STLを使っていなかった

問題自体は大して難しくはなかったと記憶しています。 それなのに5問中2問しか解けなくてもどかしくて悔しかった。 その記憶をかき消すために、Linuxを入れ、Emacsを使い、英語キーボードを買い、 練習サイトで練習するようになりました。

そして次の年、新たに入学してきた後輩を誘い、 盤石の態勢で予選を突破します。 しかしアジア地区予選でこっぴどく敗北します。 最初の1時間30分で3問を解いて、 残りの時間ほとんど何も出来ずに終ってしまい、 何か壁のようなものを感じました。

考えたらわかるもの。

自明な問題。

考えてもわからないもの。

有名な問題。

考えなければならないもの。

有名問題の応用。

ICPCに限らず、短時間のコンペで出題される問題には傾向があります。 C/C++、Java(、Pascal)の標準ライブラリのみを用いて、 1時間もかからずに1から記述できなければいけないという制限がある為です。 自ずから利用できるアルゴリズムには制約がかかり、 TopCoderでは、使いやすさからDPが非常に好んで採用されているように思います。

オンラインジャッジサイトでの解答数を50→200まで上積みし、 翌年の国内予選は5位で通過します。 それでも当時のトップチームとの実力差は歴然としたものを感じていました。

合宿への参加

その頃日本チームの成績の底上げを目的として、 予選上位通過者を対象に強化合宿が行われるようになりました。 たしか私が大学4年の時に第一回が行われたと記憶しています。 それまではチーム名と、その恐ろしい実力しか知らなかった人達と実際に 顔を付き合わせて3日3晩戦い続けたのです。 衝撃でした。 これが私の人生に与えた影響は計り知れません。 当時の最強チームGokuriの面々は今でも最も尊敬する人達ですし、 この時出会って、その後2年間にわたりライバルであったGNCの西川さんとは 会社を立ち上げることにもなりました。

合宿自体は特に振るったわけでもなかったのですが、 上位のチームの人達が当然やっていることを 自分たちが全くやっていなかったことに気付かされました。

アルゴリズムの網羅的勉強を一回もしたことがなかった!

私は当時お金が無かったので、本もほとんど買わず、 知識は作るプログラムに応じてオンデマンドで勉強してきたものでした。 投機的に学習するという発想がそもそもなかったのでしょうか。

でも強くなりたかった私は、 ロバートセジウィックの「アルゴリズムC++」 を泣く泣く大枚をはたいて購入し、通して読んで勉強しました。

その甲斐もあって、その年のアジア地区予選で上海交通大学に次ぐ2位になります。 それから世界大会に出場して、挫折を経験し、 再度の世界への挑戦、そして挫折。

と続いてゆくのですが、 転機は合宿への参加だと思います。 実際に会って相まみえると、 負けて悔しいという感情が恐ろしいほどに増幅されます。 もともと負けず嫌いというのもあって、 とてもよい方向の刺激を受けることができました。

競技プログラミングをやって得られたもの

思い出話はこのあたりにして、 競技プログラミングが私にもたらしたものでも語りましょうか。

  • 正確なコーディング

自分で言うのも何ですが、普通の人より正確にコードが書けると思います。 というのも、ICPCではコードの正確さがスコアに直結するからです。 正確なコードを速く書くために、正確に書きやすいコーディングスタイルを自然に追い求めるようになります。 同時期にHaskellを勉強していたこともあり、 どうプログラムを書けばバグが出にくいかということにとても敏感になりました。 加えて、コーナーケースにも敏感になります。 コーナーケースで間違えるという経験を何度もすることになるので、 コードを書くときに自然と頭の片隅に常にコーナーケースが意識されるようになります。

  • 思ったことをすぐにコードに落とせるようになる

やりたいことを思い描けば、 次の瞬間には、ほぼオプティマルな形でコードが完成しています。 慣れてない人は割りとそれができない印象です。

  • 計算量のオーダが瞬時に見積もれるようになる・どれぐらいまで現実的な時間で動作するかなど

アルゴリズムやコードがどれぐらいの時間で動作するのか だいたい分かるようになりました。 その直感に反するほど遅いケースなど、 ボトルネックの存在が見抜けるように。

  • それ、○○でできるよ!というのが見抜けるように

解くべき問題が与えられたときに、それがどれぐらい難しいのか分かるようになりました。 それには既知の問題を広範囲にわたって知る必要があって、 問題集としてICPCなどは優秀かと。

競技プログラミングへ思うところ

競技プログラミングが云々という話は、いろいろな所でされていますが、

  • 競技プログラミングをしていた人のコードは汚い

人それぞれでしょう。私は自分のコードは綺麗だと思います。 競技プログラミングをしていた人は、同じアルゴリズムを何度も実装しているので、 経験がない人よりも一発で簡潔なコードを書けるという良い傾向はあると思います。

競技プログラミングの後遺症として変なマクロを使い出す人もいたりしますが、 これは言語の表現力を補うためのものですし、手の運動をしているだけで お金がもらえるというのは社会人にとっては願ったり叶ったりなので、 それがわかれば矯正すればすぐに治るでしょう。

  • 大きなプログラムが書けない

人それぞれでしょう。私はICPCやっている時もそれなりに規模の大きなプログラムを書いていましたし、 もともとプログラムが得意な人がそれを生かして競技プログラミングに出ているケースが多いと思います。 最近は競技プログラミングからプログラミングに入った人も多そうですけど、 それは少し危惧しています。 あるいは、そもそもプログラミングをプログラムを作る手段としては 興味が持てない人が出てくるんじゃないかとか。

  • こんなのができてもなんにもならない・できないけどすごい人はいくらでもいる

迷路の探索とかが意外と書ける人が少なくて、その反論で言われているのを見ましたが、 「掛け算ができないけどすごい数学者なんだ」のようにしか見えません。 できてもなんにもならないけども、できないと言うことは プログラマとして何か劣っているということです。

おわりに

思った通り取り留めのない話になってしまいました。 旧世代の競技プログラマの戯言だと思ってもらえば。

まあ、なによりプログラミングの能力を他人と競いあうのはとても楽しい! お金もかからないし、勉強にもなるし一石二鳥じゃないか。

何事も頂点を極めるのは大変です。 僕以外の歴代覇者はみんな化物揃いだと思います。 勝てなくても、そういう人のコーディングを間近で見れるだけでも それは貴重な機会だったりします。

最後になりますが、 競技プログラミング、特に私としては、ICPCに参加して 本当に良かったと思っています。 人脈にしても、スキルにしても。青春を賭するのに十分値するものだと思います。 私もまだ引退したわけではないので、 TopCoderなどにリハビリとして定期的に参加したいものです。

告知!

宣伝で恐縮ですが、来るコミックマーケットC81にて、

簡約!? λカ娘(二期)

という本が頒布されます。 私も幾つか寄稿しております。 Haskellの話+ ICPC的な話も書きまして、 これは純娯楽小説みたいな形になっておりますので、 お気軽に楽しめるかと思います。 お立ち寄りの際はぜひ手にお取りください。