hogecoder

tsutaj 競技プログラミングの記録

競プロをやりはじめてから半年が経ちました

競技プログラミングを初めて、今日でちょうど半年です。(私が初めて使用したオンラインジャッジであるAtCoderの初AC日を、競プロ初日としています)

競技プログラミングはじめたいけど、なにからやればいいのかな・・・」とか、「この大会の準備期間短いけど今から頑張ったら間に合うかな・・・」とか、その辺の疑問にお答えできたらいいなあと思い記事を書くことにしました!特に初心者のかたは参考にしてください(プロはこわいから見なくてもいいですよ ><)

競プロ初心者がやるべきこと

入出力やSTL・簡単なアルゴリズムを勉強する

まず、プログラムが書ける状態までもっていかないと何も始まりません。まずは、図書館等で基本的なプログラミングの知識をつけましょう。標準入出力、for、while、if等使えるようになれば十分です。ポインタとかクラスとかは競技プログラミングではそんなに意識しなくてよいです(でもライブラリ作るときに必要になるかもしれないので勉強するに越したことはないです)

自分はそのへんどうだったかというと、競プロ始める前はCしか知らなかったためC++の記法を勉強するときはちょっと大変でした。とはいえ、毎日のようにプログラム書いてたらそのうち覚えるので頑張りましょう。ネットで検索したら初心者向けのスライドが転がってるので、そういうのも参考になりますよ。

アルゴリズムに関しては「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」(通称: TLE本)や「プログラミングコンテストチャレンジブック」(通称: 蟻本)が非常に参考になります。最初に読むならTLE本ですかね、蟻本は初級編からけっこう難しいので・・・。TLE本がわかってきたら蟻本を読む、という流れが良いと思います。

オンラインジャッジで修行

初めのうちはコンテストに出るよりも、出題形式や提出方法に慣れるために、またアルゴリズムを学ぶために、問題を解きまくるのが良いです。例えばAtCoderの場合なら、AtCoder Beginner ContestのA・B問題が簡単なのでまずはそこから埋めていきましょう。で、だんだん慣れてきたらCとかDとかに挑戦して・・・という感じですかね。自分のレベルに応じて問題を選んでいってくださいね。

出題形式はコンテスト出る前に把握したほうが良いです。特にTopCoderがちょっと特殊で、main関数に処理を書くのではなくクラスのメンバ関数に処理を書くことになります。一度やっておかないとコンパイルエラー頻発でコンテスト中悲しい思いをするので、事前にやっておくことをおすすめします。

コンテストに参加する

ある程度経験を積んだらコンテストに参加してみましょう。私はコンテスト出たいマンなのでやたら参加してますが(5/19に初めて5/28にはもうコンテスト出てました。せっかちすぎる)、自分のペースで参加しましょう。というのも、コンテスト終了後に復習しないと出た意味がほとんどなくなるので、復習が可能なレベルで出る必要があります。

コンテストはTopCoderCodeforcesAtCoder等で行われています。AtCoderは日本語で行ってくれますが、ほかは英語ですね。最近Google翻訳が強くなったらしいので、英語に抵抗のある方も是非参加してみては・・・?

ライブラリを作る

上位を狙うなら必須です。上位行ったことない私が言うのもなんですが・・・。

ライブラリとは、「このアルゴリズム使いたいぞ!」となったときにすぐに使えるように、予め用意しておくものです。グラフ理論とか幾何でよく使いますね。

で、これを作ることによって解答速度が速くなって良いのは当たり前なんですが、それ以上に「そのアルゴリズムを自分の中で咀嚼できる」のが大きいと自分は思っています。意味を理解しつつライブラリを作っていくと、自分の中で考えが整理できてとても良いので、ちゃんと理解するという意味でもライブラリ作ったほうが良いです。

自分の話

いろいろ書きましたが、実際お前はどんな感じでやってきたねん、ということで振り返ってみます。

大学の競技プログラミングサークルに初めて見学に行った(5/19)。この日から競プロはじめました。AtCoderの問題を使ってバーチャルコンテストをしていたので、AtCoderはじめました。当時Cしか書けず文字列の問題で詰みまくっていたのでC++を勉強するとぞと心に誓う。その時はICPC出ないでおこうかなと思ってたけどなんだかんだで出ることにした。

ICPC国内予選に参加した(6/24)。競プロ歴まだ1ヶ月くらい。自分のチームは、他のメンバーも同じくらいの経験値だったけど3完した。正直これは運が良すぎただけ。だってまだC++に慣れてなさすぎて、setにある要素が入っているかどうかってなんの関数使えば分かるっけ?みたいなレベルだったので・・・。グラフや幾何、DPは全く歯が立たなかったので、これから頑張っていこうと思った。

ICPC後はTopCoderとかCodeforcesとか、やたらいろんなものに手を出した。Twitterのフォロワーが頑張ってるのを見ると触発されて自分も出ちゃうんだよねー。Twitterにいるプロがモチベーションの源でした。

夏休みからライブラリを整備し始めた。AOJにはverify時に大変お世話になりました。特に幾何のライブラリが潤って、ライブラリ使うだけ問題は対処できるようになった。しかし経験が足りない。

あとは、夏休み中に蟻本の初級中級はだいたい読んだ。でもまだフローがわからない、むずい。上級は未だに読めてないなあ、あかん。

9月10月、こどふぇすワンチャンあるかなと思って予選参加するも通らず。まあ、当たり前ですね。来年に向けて1年間精進するぞと思った。

11月、全く狙ってなかったけど DISCO presents ディスカバリーチャンネル コードコンテスト 2016 予選突破してしまった。正直行ってB3補正のおかげで通ったようなもんだけど、オンサイトのコンテストに行けるというのはやっぱり嬉しいですね。本戦が楽しみです・・・。

本戦とかがかかったコンテストで勝つには、最低でも半年は必要な気がしますね。相当センスある人だったらもう少し短くても行けるかもしれないけど、経験が物を言うところがやっぱり大きいですからね・・・。

というわけで、ざっくり言うとこんな感じで取り組んでました。もっといろんなコンテストで結果出せるようになりたいですね。

目標とか

さて、競プロ歴1年を迎える前に達成しておきたいことをまとめておきますかねー。

  • レートあげたい

AtCoderCodeforcesTopCoder全部そうなんだけど、青色になりたい。もう少しがんばれば到達しそうな雰囲気はあるから、このまま頑張っていきたい。

  • ライブラリ充実させたい

ジャンルによってライブラリの充実度が違いすぎるので、どの分野も充実させたい。あとライブラリのバグ発見したい。

  • 蟻本読み進めたい

もう難しいところしか残ってないし、なかなか読み進めるのが大変だけど、なんとか乗り越えたい。

こんなところですかね。次の半年間も実りあるものにしたいですね。精進します。