競技プログラミングを始めて1年が経ちました
2015/11/22に競技プログラミングを始めてから丁度1年が経ったので、競技プログラミングをやるにあたって、何をしていたか等を記事としてまとめておきます。
(ためになる話は多分そこまでないです)
この記事の流れ
この記事は次のような構成になっております。
- 始まり
- 競プロを始めて変わったこと
- この一年での競プロにおける変化
- (以下「続きを読む」部分、競プロでの様々なこと)
- 言語
- 競プロ環境
- 練習・勉強方法
- 成績
- 最後に
始まり
twitter.comよーしyukicoderや!
— satanic@ABC-D32/43 (@satanic0258) 2015年11月22日
私が"競技プログラミング"というものに触れたのはyukicoderが一番最初でした。
何故yukicoderかはわかりませんが、yukicoder の"ゆるふわ"推しにつられたのでしょう(?)。
このときは、AtCoderやTopCoder、ICPCなどは全く知りませんでした。
競プロを始めて変わったこと
twitter.com競プロ依存症わかる…
— satanic@ABC-D32/43 (@satanic0258) 2016年8月2日
簡単に言うと、競プロ依存になりました。
競プロは、何かキッカケをもって始めた訳ではないため、
「まぁコーディングの練習として適当にやってみよう」
位の感じでした。
しかし、問題を解き、コンテストにも参加するようになると、だんだん次のようなところに惹かれていきました。
- 問題を見たときに、「どのアルゴリズムを使うのがいいか?」と考えるのが楽しい
- 実生活でありうるような、複雑な要素が絡み合う問題をプログラムに解かせることが出来るのが面白い
- 単純に問題を解くのが楽しい
- Twitterを通して他の人と競プロの話題で盛り上がることが出来るのが楽しい
などなどです。
こうして、競プロを主軸とした生活が始まるのでした…。
twitter.comおっフォロー数がpow(2, 7)
— satanic@ABC-D32/43 (@satanic0258) 2015年11月30日
また、Twitterの利用法も大きく変わりました。
このツイートは競プロを始めて1週間くらいの時のものですが、当時まだフォロー/フォロワー数が100人前後しかいませんでした。
(競プロを始める前は何故かこんなアイコンだったんですが、覚えている人はいるんでしょうか)
twitter.comそういや今のフォロワーさんの大半がここ1年以内にフォローした人だ
— satanic@ABC-D32/43 (@satanic0258) 2016年7月24日
ところが、競プロを始めて、競プロ/プログラミングをやっている人をフォローしていたら、気づくとフォロー/フォロワー数が400人前後まで増えていました。
Twitterで話す内容も、半分以上が競プロの内容ばかりとなっています。
twitter.com勉強用のプログラム作ろうと試験直前に思い立って一気に書き上げたら1時間も掛からなかったし、競プロが実生活に役立っている
— satanic@ABC-D32/43 (@satanic0258) 2016年8月2日
また、いつの間にかプログラム実装力がついていました。
プログラミングのコンテストでは、問題を見てからそれをすぐにコードに起こすことが重要となってきます。
そのため、コンテストで経験を積んでいった結果、競技とは関係のないところで簡単なプログラムを作成する際に、素早く目標のプログラムを作成することが出来るようになっていました。
(このおかげで試験も難なくこなせたので、まさに競プロありがとう、と言った感じでした)
この一年での競プロにおける変化
ここでは、各コンテストサイトでのレートの変遷を見ていきます。
AtCoder
AtCoderのページが新しくなってからのレートはこのようになっています。
未だ何とか単調増加を続けてはいますが、正直結構厳しいですね…。
なるべく増加を続けられるように頑張りたいと思います。
Codeforces
Codeforcesのレートはこのようになっています。
正直こどふぉは問題文がの読解が難しい回が何回かあり、それ故のミスもよくしています…。
(最近Google翻訳の性能が向上したこともあってか、レートも少し上がっています)
また、こどふぉではちゃんとコーナーケースを処理しなければ落ちてしまうことも多々あるため、うっかりそれを忘れてレートが下がったりもしています。
素早く、かつ正しく問題を理解することが大切ですね…。
TopCoder SRM
SRMのレートはこのようになっています。
SRMは結構レート変動が激しく、参加した回の半分も色が変わってしまっています(苦笑)。
一応青から黄色になったりしてはいますが、まだdiv1の問題を時間内に解いたことがないため、それが今後の課題となっています。
何とか競プロ2周年までには、div1easyを安定して解けるようになりたいですね。
- (以下「続きを読む」部分、競プロでの様々なこと)
この先は、過去1年分のツイートを適当に抜粋して、あったことなどのコメントを加えただけのものなので、時間に余裕のあるときどうぞ。
(Twitterのツイートを大量に貼り付けているため、記事のロードに時間がかかる可能性があります)
言語
twitter.comキュー使うって分かっててCで泥臭くやってんの意味ない気がしてきた…
— satanic@ABC-D32/43 (@satanic0258) 2015年11月25日
一番初め、本当に最初の頃はC言語で問題を解いていました。
しかし、機能面において色々つらい面がいくつか出てきたため、すぐにC++へと転身しました。
何故C++かというと、プログラミング言語はC言語とC++しか使えなかったためです。
(これは今も大して変わっていない)
多倍長の整数型が扱える言語もぼちぼち勉強すると色々楽そうですね(現状、C++でint型配列を使う方法を取っています)。
競プロ環境
twitter.com最近Wandboxの方が使い勝手いいと思ってるのなんでだろう
— satanic@ABC-D32/43 (@satanic0258) 2016年4月2日
4月頃、競プロの問題を解くのに何故か(?)Wandbox をよく使っていました。
PCはWindowsだったのですが、手頃に「コンパイル→サンプルを確認する」ということが出来る環境をまだ作っていなかったためだと思われます。
twitter.com最近は競プロでMSVSをエディタとして使ってます(実行確認はターミナル上)
— satanic@ABC-D32/43 (@satanic0258) 2016年7月10日
しかし、Wandbox では色々つらい部分も出てきたため、競プロを始める前から触っていたVisual Studioに戻ることにしました。
twitter.com@yumechi0525 です! 「ここでエラー出たよ~」とか教えてくれます pic.twitter.com/SwYGKnYvL7
— satanic@ABC-D32/43 (@satanic0258) 2016年9月11日
特にデバッグ機能や(これは長さ3の配列の5番目の要素を参照しようとしたときのエラーを検出している)、
twitter.comVC++にコードスニペットを登録してみた pic.twitter.com/s7ePNGmQsk
— satanic@ABC-D32/43 (@satanic0258) 2016年9月16日
スニペット登録が便利で重宝しています。
twitter.comいつも競プロはこんな感じです(二回目) pic.twitter.com/MoDKlKzgTv
— satanic@ABC-D32/43 (@satanic0258) 2016年9月16日
そして現在は、このように画面右に問題文、画面左にエディタ&コンソールという画面構成で競プロをしています。
練習・勉強方法
twitter.com文法わかるけどアルゴリズムそんなに知らないマンだから勉強するはアルゴリズムですね
— satanic@ABC-D32/43 (@satanic0258) 2015年11月23日
twitter.comツリー構造とか巧みに使いこなしたい()
— satanic@ABC-D32/43 (@satanic0258) 2015年11月23日
プログラミングには割と馴染みがあったので、初め競技プログラミングをやるにあたって「まずはアルゴリズムを学ぶところから始めよう!」と意気込んで、yukicoder の簡単な問題を解きながらアルゴリズムを勉強していました。
— satanic@ABC-D32/43 (@satanic0258) 2015年11月30日twitter.com
元々、問題を解いたりするのが全然苦ではなかったため、ゲームをするような感覚で問題を解き進め、最初の1週間はyukicoderで問題を46問解いていたみたいです。
twitter.comyukicoder★1暫定全部解き終わりました♨
— satanic@ABC-D32/43 (@satanic0258) 2015年12月10日
そして、3週間弱でyukicoderの★1の問題を全て解き終わっていました。
よほど暇だったんだと思います(小声)。
twitter.comAtCoderコンテストがあるらしいのでこの機会に会員登録
— satanic@ABC-D32/43 (@satanic0258) 2016年3月12日
競プロを始めて約3ヵ月、Twitterを眺めていると、「AtCoderコンテストがあるよ!」というツイートが見られたため、ものは試しとABC034に参加してみることにしました。
これが初めてのコンテスト参加です。
(結果等は後述します)
twitter.comABC参加→解説放送見る→なるほどなぁ
— satanic@ABC-D32/43 (@satanic0258) 2016年3月12日
を習慣づけていこう
初め、
>>コンテスト<<
…と聞くと、何処か怖気づいてしまう部分がありました。しかし実際は、今まで問題を解いていたところに時間制限が付いたり、その早さによって順位が決まったりする、というだけで、何かプレッシャーを感じたり、失敗したからといって大きく損したりするようなものでもない、ということに気が付きました。
そこから、コンテストに参加するのも練習のひとつとして取り入れていくことにしました。
twitter.comはじめてのSRM
— satanic@ABC-D32/43 (@satanic0258) 2016年4月15日
twitter.comAOJとCodeforcesにも登録しておこうかな
— satanic@ABC-D32/43 (@satanic0258) 2016年5月7日
さらに、コンテストへのイメージが変わってからは、他のコンテストにもどんどん参加するようになりました。
twitter.com英語が読めないので問題を正確に読解できるかによってる部分がある(つらい)
— satanic@ABC-D32/43 (@satanic0258) 2016年8月7日
英語(特にこどふぉ)に躓く部分もありますが、英語は英語でまた必要なスキルの一つであるため、日本/海外問わずコンテストには参加しています。
twitter.comA:"CODEFESTIVAL2016"との相違回数をチェック
— satanic@ABC-D32/43 (@satanic0258) 2016年10月10日
B:'a'⇒a+b>0ならYes、'b'⇒b>0ならYes
C:昇順priority_queueに縦横が分かるように突っ込んで、取り出したものが横だったら(縦+1)×その値をansに加え、横をデクリメント(縦も同様)
また、コンテストが終わった後はほぼ毎回Twitterで自分の解法を言うようにしました(このツイートはCodeFestival予選Bに対するものです)。
これには良い点がいくつかあります。
理解していることに対して解説を行うと、自分がどれくらい理解しているのかがわかります(解説というほどのものでもありませんが)。
さらに、それをアウトプットすることで他の人の助けとなったり、意見を共有・交換することが出来ます。
このことから、積極的に解説をしていこうと思いました。
(この「解説勉強法」は、試験対策や大学受験にも役立った記憶があります)
twitter.com今日は競プロでよく使うアルゴリズムをリストアップして概要書いたり実装・使用できる/できないを軽くまとめましょう
— satanic@ABC-D32/43 (@satanic0258) 2016年4月1日
また、時には「自分が使えるアルゴリズムは何か/使えないアルゴリズムは何か/何故使えないか」をリストにまとめてみたりもしました。
twitter.com加えて名著2冊も購入しました♨︎ pic.twitter.com/hziGFigcdW
— satanic@ABC-D32/43 (@satanic0258) 2016年4月10日
競プロを始めてから4か月経って、競プロerは全員知っているであろう「蟻本」を手に入れました。
twitter.comGrundy数なるものを知らなかったので早速蟻本を見てみる
— satanic@ABC-D32/43 (@satanic0258) 2016年4月17日
蟻本を買ったことで、「知らない技が出てきた→蟻本で確認!」の流れが出来たため、勉強の効率が良くなった気がしました。
(この頃から、「競プロのプロになりたい」という思いが強くなり始めたんだと思います)
twitter.com蟻本見てたら自分がDPとグラフ理論系があまり得意ではないことが分かった(´-`)
— satanic@ABC-D32/43 (@satanic0258) 2016年5月11日
それから、「自分は何が苦手か」ということを徐々に意識し出してきました。
twitter.comやっぱDP強化月間に入ると良さそうだな…
— satanic@ABC-D32/43 (@satanic0258) 2016年6月3日
そこで、苦手克服のためにまずはDPを完璧にしよう!と意気込んでTDPCの問題を解き始めました。
(しかしTDPCは難しく、まだ全部は解けていません)
twitter.com何かいい問題ありますか!
— satanic@ABC-D32/43 (@satanic0258) 2016年8月11日
twitter.com★4の問題が飛んできた
— satanic@ABC-D32/43 (@satanic0258) 2016年8月11日
また、たまにTwitterで競プロのプロから問題サジェストが飛んできたりして、とてもいい刺激になっていました。
(ありがとうございます)
成績
twitter.comAとBだけやって詰まってしまった…
— satanic@ABC-D32/43 (@satanic0258) 2016年3月12日
初めてのコンテスト、結果はAB+C部分点の2.5完でした。
(ABC034の順位表)
分からなかったのはC問題でコンビネーションを求める部分で、解説を見て
「逆元を求めよう!これはフェルマーの小定理を使ってできるよ!」
といった内容の文を見て、
「へぇ、そうなんだ…(無知)」
みたいな感じでした(ぶっちゃけそんなん知らんわ!と呆れたところもあったと思います)。
twitter.comABC全完キタコレ!
— satanic@ABC-D32/43 (@satanic0258) 2016年5月7日
競プロを始めて5か月で、ようやくABCを時間内に全完することが出来ました。
これが早いのか遅いのかわかりませんが、成長を感じられて嬉しかったです。
twitter.comこどふぉでついに初4完した
— satanic@ABC-D32/43 (@satanic0258) 2016年10月22日
また、Codeforcesは競プロを始めて11ヵ月で初めて4完することが出来ました。
twitter.com今AtCoderでもCodeforcesでもTopCoderでも青の真っ青コーダーになってる
— satanic@ABC-D32/43 (@satanic0258) 2016年9月13日
そして今現在、どのコンテストサイトでも青コーダーとなっています。
twitter.comまだ競プロ初めてから1年経ってないけど通過できたのでうれしい
— satanic@ABC-D32/43 (@satanic0258) 2016年10月24日
さらに、CodeFestival2016への出場権もゲットすることが出来ました。
東京に行くには片道数時間数万円かかるため、中々オンサイトイベントには手を出せずにいましたが、「交通費・宿泊費無料!」という文に誘われ、参加を確定しました。
無事に行って帰って来ることが出来たら、CodeFestival2016の参加記を書きたいと思います。
(まだ一人で飛行機に乗ったり東京に行ったりしたことがないため不安がいっぱい)
[2017-02-22 追記]
無事生きて帰ってこれたので参加記を書きました。
satanic0258.hatenablog.com
[2017-02-22 追記ここまで]
最後に
twitter.com競プロはいいぞ
— satanic@ABC-D32/43 (@satanic0258) 2016年4月23日
twitter.com競プロはいいぞ
— satanic@ABC-D32/43 (@satanic0258) 2016年5月11日
ありがとうございました。