Hatena::Grouptopcoder

skyaozoraの日記

 | 

2016-12-08

競技プログラミングを始めての10年間を振り返る(前編)

23:05

競技プログラミングアドベントカレンダー2016の8日目の記事です。私が競技プログラミングと呼べるものを始めたのは2006年の10月か11月くらい、なので今年でもう競プロ暦が丸10年になります。という訳で、それを記念(?)して2006年から2016年まで1年ごとに競プロに関してどんな1年だったかを、レーティングの変化等も交えつつまずは最初の5年に関して振り返ってみようかなと思います。単なる自分語りではなく当時の競プロ界とかもちらっと触れられるようにしようかと思いましたが結局単なる熱い自分語りになってしまいそうなwそんな内容ですがよろしければ見ていって下さい。

2006年(中3)

全ての始まりはこの年の9月末ぐらいかな?に科学部で同級生が「そろそろ情報オリンピックに向けての対策を始めないとなぁ」と呟いたことでした。別に私に対して誘うとかそういった感じのニュアンスでは全く無かったのですが、それを聞いて何かふと「自分も参加してみようかな」と思いました。

で、帰って情報オリンピックの公式ページから過去問を見てみました。確かに、最初の問題ならどういう風な処理をすれば答えが求まるかは何となく分かるような…。ただこの当時自分はプログラミングといえば、VisualBasicでフォームにボタンやらテキストボックスやらを配置してゲーム(とはとても呼べないものでしたが)を作るといった経験しかなく、いわゆる競プロで求められるコンソールプログラム的なものは全くピンと来ませんでした。

そこで書店でC言語の入門書を購入し、if文やfor文、配列や関数の使い方、ファイルからの入出力などを適宜自分で書きながら覚えていきました(ちなみにこの時買った入門書でサクラエディタが紹介されてたのでそれから10年以上たった今でも使っていますw)。練習として、当時生物の授業でランダムウォークで生命の子孫が収束していく実験をおはじきを使ってやったのでそれをシュミレートするプログラムを書いたり、数学の授業でランダムに配った時ポーカーのそれぞれの役が出る確率の話をしてたので役判定のプログラムを書いて実験したりしてました。

そうしてある程度プログラムを書くことに慣れたところで公式ページから過去問に挑戦してみました。正しくプログラムが書けると、100万回や1000万回の処理であっても、プログラムに入力を与えると一瞬で出力を返し、かつそれが公式ページに正しい答えと一致するというところに感動しました。競プロを始めて最初の感動は、アルゴリズムを工夫してどうこうではなく手数が大量にかかることでもプログラムが一瞬で答えを返してくれるというところでしたね(同意して下さる方はどれだけいるでしょうか)。

そして迎えた情オリ予選本番は、当時はまだ復活して2回目ということで予選通過のレベルはそこまで高くなく(代表になる方々は今と遜色無いレベルでしたが)、落ち着いて取り組めたこともあり初参加で予選通過を果たすことができました。こうして競プロに初めて触れた1年はかなり満足のいく形で終えることができました。

2007年(中3→高1)

TopcoderRating:初参加→883(年5回参加/計5回参加)

そうして迎えた初の情オリ本選でしたが、流石にこちらは通過することができませんでした。その後はこういった形式の問題を練習する方法がよく分からず(情オリの公式ページにある過去問も少なかったですし)、どうしたものかと思っていたのですが、私が競プロを始めるきっかけとなった科学部の同級生の言葉が再び転機となります。

高1の夏休み、科学部の部室で彼がTopcoderというサイトを紹介してくれました。定期的にコンテストが行われていて、こんな感じでArenaにプログラムを打ち込むと自動で正誤判定が行われるよって感じのことを科学部においてあったパソコンで実演してくれました。ちなみにこの年は最初に日本人にTopcoderが広まり始めた年(もちろんその前から始めていた日本人の方もいる)なのですが、恐らくchokudaiさんが見つけて色々な方に布教していたのではないかと思われます。彼もどうやらSuperconでchokudaiさんから布教されたものと思われます。

早速これだ!と思って始めようとしたのですが、登録の大変さに挫折…。その後すぐに2学期が始まってしまい中々始められずにいたのですが、9月末の体育祭の代休に1日使って何とか登録したのを覚えています。そして初参加のSRMがいきなりUnrated回になったりしつつ、Rateがつき始めたらあっという間に灰色に…。最初のころは電子辞書を使って知らない単語をひとつずつがんばって訳そうとしていたので文章把握に大量に時間を消費し(流石にすぐ諦めて翻訳サイトを使うようになりましたが)、さらに言語自体にも慣れてなかったのでコンパイルエラーが出ると全く原因が分からなかったりしました(コンパイルエラーのメッセージも英語で出力されますしね。まぁ慣れてないと日本語でもどこが悪いのか分からなかったりしますが)。

ちなみにこれは参加3回目のSRMの本番中に書いたコードです。やることは分かってコードは書けたのですが何故かコンパイルが全然通らず、原因が全く分からないままコンテスト終了。そのときのコードがこれです。原因分かりますか?そう、配列なのにもかかわらず添え字を入れてないんですwあまりに初歩的なミスですが当時の自分では最後まで見つけることができませんでした。本当にひどすぎますよね…

そうこうしているうちに2度目の情報オリンピック予選。Topcoderをしばらくやっていた所為で出力をprintfではなくreturnで返そうとしてしまうというのがあったけど流石にある程度慣れたお陰か前の年よりは危なげなく通過することができました。この年の間はまだ全然でしたが、Topcoderという間違いなく自分の競プロ人生において最も重要なものとの出会いを果たした1年でした。

2008年(高1→高2)

TopcoderRating:883->1340(年20回参加/計25回参加)

迎えた2度目の情報オリンピック本選は、プログラムはある程度書けるようにはなってはいたものの、計算量の概念とかアルゴリズムを改善するとかを全然知らなかったので結局解けたと思った問題でも部分点しか取ることができず2年連続で落選。さらにTopcoderでも毎回全然思うように問題を解くことができず灰色から抜け出せる気配も無く、かなり競プロへのモチベが下がって、引退というほどではないですがもうSRMに参加するのはしばらくやめておこうという気分になりました。

そういう訳で数ヶ月ほど離れていたのですが、ある時ふと「またちょっとやってみようかな」という気分になって久しぶりにSRMに参加してみたりしました。するとその回ではそこそこの結果を残すことができ、そこから競プロへのモチベが回復していきました(実は自分の競プロ歴の中でもかなり重要なポイントだったと思います。もう1回やってみようと思わなかったり、或いは思ってもここで惨敗してまた叩きのめされたらどうなっていたんでしょう?)。

その後はまた上手くいかない回があったりしてちょっと上がったレートもすぐに元に戻ってしまったのですが、それでも本番中に解けなかった問題を後で復習したりするようになりました。そうこうしてるうちにやっと力がつき始めたのか、SRM409にて漸く半年以上ぶりにグリーンコーダーに復帰できました(同じコンテストでrng_58氏が日本人の高校生として初めてレッドコーダーになってました。ぱない)。その後は参加したコンテストの復習に加えてSRMの過去問も解いたりするように。この頃はよくchokudaiさんにSkypeで問題に関する質問をしてましたね(これは相当ためになったと思いますし、いつも答えて下さって本当にありがとうございました)。そうしてくると当然目標はDiv1、ブルーコーダーとなるのですが、結構レートのアップダウンが続いて中々届かずやきもきしてました。この頃は毎回コンテストが始まる直前はPCの前で緊張で体がガクガク震えてましたねwそんな中SRM422で遂に念願のDiv1昇格。一度落ちますがすぐ次のSRMで復帰して、以降はずっとDiv1ですね。

そんな訳でDiv1の過去問にも挑戦するようになりました。この時代のSRMのDiv1Medは今から見ると「典型DP」と呼べるようなタイプの問題が非常に多く、SRMの過去問埋めを通してかなりDPの基礎的な力は身についたと思います。3度目の挑戦となった情報オリンピックの予選はちょっとミスってひやっとするも何とか通過。それまではまともにしてなかった「競プロの練習」というものをするようになったという意味で、この1年の特に後半はターニングポイントになりましたね。

自分のTopcoderへの熱が徐々に高まっていくと同時に、それまでは全然気にしてなかったレーティング上位勢のハンドルとかも見るようになりました。この頃のTopcoderは完全にPetr,ACRush,tomekの3強でしたね。国内ランキングではnyaさんやLaycurseさんといった辺りが1位争いをしていました。1ページにつき50人ずつ表示されるので、開いた瞬間に表示される国内上位50人に入るのが目標でした。またどの国の参加者のレーティングが高いかというランキングもあって、日本の順位の変動に一喜一憂したりもしてました。*1

さらにこの頃からTopcoderSRMで検索して色々な方の参加記や記事を読むようになりましたね。特にgentooさん(恐らく日本で最初にTopcoderが紹介されたであろう記事に載っていた夷藤勇人さんです)の日記は何度も読み返しましたね。過去問を埋めていく過程でこの日記で触れているところまで遡ったら「確かに日記でこう書いてあったなぁ」と感慨に浸ったり。またTopcoder部というのが一番最初にできた頃だったと思うのですが、そこの一員であったtomerunさんやnaoya_tさんを一方的にライバル視してたり、cafelierさんがあっという間にRedcoderまで駆け上がったのを見て驚いたりしてましたw

2009年(高2→高3)

TopcoderRating:1340->1890(年11回参加/計36回参加)

年が明けてからも相変わらずコンスタントにSRMの過去問を解いていました。2月頭くらいに5日くらい連続で何人かの競技プログラマーがTopcoderのArena上に集まって過去問を解くという練習会的なイベントがあったのですが、そこで一緒になったAyokura氏とwrong氏のプロフィールを見てみるとそれぞれ高校生・中学生とのこと。これはもしかして情報オリンピックの本選に2人とも来るのでは?と思ってたら案の定本選の懇親会でこの2人を見つけることができ、「あの練習会で一緒だったよね」と話すことができました。最初にコンテストサイトで名前(HN)を知った人とリアルで会う、というのはこれが恐らく初めてで感動しました。

その情報オリンピック本選のコンテストに関しては、練習をつんでいたお陰かかなり危なげなく通過。最後の年にして初めて合宿に進むことができました。しかし合宿では上位4人に入ることができず代表落ちとなりました。これで情オリの代表になるチャンスは完全に失われてしまったので、流石にショックでしたね…。

しかしある程度競プロにはまってきてたからか、その後もモチベーションが落ちることはありませんでした。むしろ情オリの資格を完全に失った高3の時が多分一番高校の間では競プロの練習をしてたんじゃないのかというw(この辺我ながらかみ合わないなーとも思うけど)。この頃に色々なアルゴリズムだったり、またDPの色々なパターンを身に付けられたと思います。この年は基本SRMが月2回しかなかったので参加回数としてはあまり多くはありませんでしたが、初めてイエローコーダーに昇格し、また初めて本番中にDiv1のMedium問題を通すことができました。

またこの年は初めてマラソンマッチにも参戦してみました。思いついた改善をしてみたらスコアが上がる、その様子がビジュアライザーで見ることができる、っていうのは面白いなぁとは思いましたが…。何か上位陣とはやっていることが全然違うというか、今のやり方では明らかに越えられない壁があるというか…。その後もマラソンマッチには何回か参加はしましたがどうにもちゃんとできてる感じがしなくて結局最近は全然参加してないですね。

ちなみに、この年には「天下一プログラマーコンテスト」の予選にも参加しました。え?と思った方もいるかもしれませんが、そう、Klab社主催のあの「天プロ」です。天プロは今のような形で開催されているのは2012年からですが、実はこの年にもちょっと形式は違うものの開催されていました。この年はチーム戦参加可能かつ予選はマラソンマッチっぽい形式(要するにSupercon予選みたいなやつ)でした。私は高校の後輩と予選に参加したのですが残念ながら通過できず。本選は数日間にわたって開催され、予選と決勝が存在したらしいです(今年のコドフェスみたいな感じ?)、楽しそう。チーム参加可能だったにもかかわらず優勝は個人で参加したwataさんだったらしいですね。流石だ…。またwataさんといえば、この年に行われたSRM443において日本人として初めてのTarget(レート3000)になっていましたね。日本人Targetはこれまで6人しかいません。

最後に、この年にはchokudaiさんによる最強最速アルゴリズマー養成講座の連載も始まりました。個人記事以外でこういうまとまったTopcoderに関する記事が出るのはこれが多分初めてじゃないでしょうか?これによってまたTopcoderに参加する日本人の層も広がった気がします(しかし、前半の説明は結構いいと思うんですが、後半に載ってる例題が難しすぎて、せっかく興味持ってくれた人も心折れちゃうんじゃないかと個人的には思ってましたね…まぁchokudaiさんも当時はまだ若かったですし、この辺の試行錯誤がきっと今のAtcoder運営にも生きてるんじゃないかということで)。

2010年(高3→B1)

TopcoderRating:1890->2288(年31回参加/計67回参加)

CodeforcesRating:初参加->1996(年10回参加/計10回参加)*2

この年の最初の方は大学受験があったので流石にSRMには参加せず。とはいえ全く競プロから離れて受験に集中ということもできなかったので、SRMの結果をチラッと見たり問題を考えたりはしていました。センター試験終了直後のSRMは流石に出てもいいかなと思って出ようとしたのですが、早寝早起きの生活をしていたので深夜まで起きてられず寝落ち…。結局SRMへの復帰は受験終了後まで待つこととなりました(しかし同級生のrng_58氏やlyrically氏はそんな受験直前でありながらSRMに参加し続けて何と高校生Targetになっていました。やば過ぎる…)

そして大学受験も終了し、SRMに復帰…の前にTopcoderで参加したのはTCHSというコンテストでした。TCHSはSRMと同じ形式のコンテストですが高校生のみが参加可能です。2008年ごろまではSRMと同じタイミングで定期的に開催されていました。自分がこの時参加したのはトーナメントでしたがそれもどうやらこの年が最後だったようですね(自分も高校卒業直前にギリギリ参加できてよかった)。TCHSではtouristとneal_wuが圧倒的な2強だったと覚えています。

また、この年からCodeforcesという新たなコンテストサイトも生まれました。日本人で元々Topcoderに参加していた人たちの間では始まってかなり早い段階から名前が広まった気がします。自分も初めて参加したのはContest#4とかでした。ただこの回は確かキューが混みまくっていて、コンテスト半ばで出した提出の結果がコンテスト終了直前になってやっと分かるというレベルでしたw

もちろんTopcoderも。この年からSRMは月3回にまた増えましたし、さらにこの年からTCOへの参加資格も得たのでかなりの回数参加できましたね。レートが2000に乗ってからはまたアップダウンが続いて(Div1を目指していた頃と同じように)やきもきしていましたが、SRM478で遂に念願のRedcoderに!Topcoderを初めて3年弱、始めた頃はどんなレベルか想像もできませんでしたが、その憧れの境地に自分が到達することができました。流石に嬉しかったですね。

前述の様にこの年からTCO,GCJへの参加資格を得て、初めてのトーナメント形式のコンテストへの参加となりました*3GCJは500人通過のR2を予想に反して通過できてR3まで進めました。もっと神がかっていたのはTCOで、毎回「次のRoundでこの順位を取ったら通過できない」というギリギリの順位で通過し続け、何と60人参加24人通過のオンライン最終ラウンドまでたどり着きます。その最終ラウンドも1問通して27位。毎年数名辞退者は出ると聞いていたので期待していたのですが、結局辞退者は2人で次点という何とも悲しい結果に。もちろん自分の実力からしたらここまでこれた地点で相当幸運なのですが、それでも何で最後の最後でちょっと足りなかったのかなーと嘆きましたね。

コンテスト参加以外でこの年の競プロに関する(自分の中での)大きな出来事は、まずは何といってもTwitterを始めたことですね。競プロ勢の人たちをフォローして、コンテスト終了直後には色んな感想が流れてきたり問題に関する議論が起こったりするのを見たり参加したりするのが楽しかったです。

次に、色んな競プロ勢の方々とリアルに会う機会ができ始めたってことですかね。ICPCへの参加(練習含む)を通してwataさんやkitamasaさん、shimejitanさんやkohyatohさんといったコンテストサイト上で名前を知っていた方々とリアルでお会いできました。またいわゆるオフ会的な集まりにも参加するようになって、この年のUTPCの懇親会ではkinabaさん(cafelierさん)やtomerunさんといった参加記をよく読んでた方々に会うことができて嬉しかったです。

最後に、(放送自体は既に前年からあったと思うのですが)診断人さんのニコニコ生放送を見るようになったということですね。この年はほぼ毎回SRMの後に放送されていた気がします。自分もほぼ毎回見てましたね、とても楽しかったです。特にBGMとしてよく流れていたPinkRoseは完全にこのニコ生の音楽として自分の中では定着しましたw

まとめ?

とりあえずこれで前半の5年は終了です(前半といっても半分よりは短いですけど)。いやー自分でも振り返ってみて懐かしいというか、もう10年もたつんだなーというか。しかし、この地点で既にRedcoderになれてたのにそのあとの5年はどうだったんだろう、この頃には始めてもいなかったけどいま自分より強い人とか普通にいるよな…とか考えると悲しくなるのでやめておきましょうw

後編もこのアドベントカレンダーの記事として24日に上げる予定です(間に合えば、ですが・・・)しかし、最初の5年は始めたばかりということで色々書くことがありましたが、後半は変化が無くて何を書けばいいのやら・・・。

*1:サイトのデザイン変更で恐らくこのあたりはもう見られないんですよね。悲しい…

*2Codeforcesは当時の色分けで書いています。間違ってるかもしれないけど

*3:本文の流れ上こういう書き方にしましたが実はGCJは2009年の地点ですでに18歳だったので参加してQual及びR1は通過してたりします

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/skyaozora/20161208
 |