sataniC++

C++、競プロ、数学などについて色々考えたりします。

競技プログラミングを始めて1年が経ちました

2015/11/22に競技プログラミングを始めてから丁度1年が経ったので、競技プログラミングをやるにあたって、何をしていたか等を記事としてまとめておきます。
(ためになる話は多分そこまでないです)


この記事の流れ

この記事は次のような構成になっております。

  • 始まり
  • 競プロを始めて変わったこと
  • この一年での競プロにおける変化
  • (以下「続きを読む」部分、競プロでの様々なこと)
  • 言語
  • 競プロ環境
  • 練習・勉強方法
  • 成績
  • 最後に

始まり

twitter.com
私が"競技プログラミング"というものに触れたのはyukicoderが一番最初でした。
何故yukicoderかはわかりませんが、yukicoder の"ゆるふわ"推しにつられたのでしょう(?)。
このときは、AtCoderTopCoderICPCなどは全く知りませんでした。


競プロを始めて変わったこと

twitter.com
簡単に言うと、競プロ依存になりました

競プロは、何かキッカケをもって始めた訳ではないため、
「まぁコーディングの練習として適当にやってみよう」
位の感じでした。


しかし、問題を解き、コンテストにも参加するようになると、だんだん次のようなところに惹かれていきました。

  • 問題を見たときに、「どのアルゴリズムを使うのがいいか?」と考えるのが楽しい
  • 実生活でありうるような、複雑な要素が絡み合う問題をプログラムに解かせることが出来るのが面白い
  • 単純に問題を解くのが楽しい
  • Twitterを通して他の人と競プロの話題で盛り上がることが出来るのが楽しい

などなどです。

こうして、競プロを主軸とした生活が始まるのでした…。



twitter.com
また、Twitterの利用法も大きく変わりました。
このツイートは競プロを始めて1週間くらいの時のものですが、当時まだフォロー/フォロワー数が100人前後しかいませんでした。
f:id:satanic0258:20161123215514p:plain
(競プロを始める前は何故かこんなアイコンだったんですが、覚えている人はいるんでしょうか)



twitter.com
f:id:satanic0258:20161123220040p:plain
ところが、競プロを始めて、競プロ/プログラミングをやっている人をフォローしていたら、気づくとフォロー/フォロワー数が400人前後まで増えていました。

Twitterで話す内容も、半分以上が競プロの内容ばかりとなっています。



twitter.com
また、いつの間にかプログラム実装力がついていました。

プログラミングのコンテストでは、問題を見てからそれをすぐにコードに起こすことが重要となってきます。
そのため、コンテストで経験を積んでいった結果、競技とは関係のないところで簡単なプログラムを作成する際に、素早く目標のプログラムを作成することが出来るようになっていました。
(このおかげで試験も難なくこなせたので、まさに競プロありがとう、と言った感じでした)


この一年での競プロにおける変化

ここでは、各コンテストサイトでのレートの変遷を見ていきます。

AtCoder

f:id:satanic0258:20161123225317p:plain
AtCoderのページが新しくなってからのレートはこのようになっています。
未だ何とか単調増加を続けてはいますが、正直結構厳しいですね…。
なるべく増加を続けられるように頑張りたいと思います。


Codeforces

f:id:satanic0258:20161123225558p:plain
Codeforcesのレートはこのようになっています。
正直こどふぉは問題文がの読解が難しい回が何回かあり、それ故のミスもよくしています…。
(最近Google翻訳の性能が向上したこともあってか、レートも少し上がっています)

また、こどふぉではちゃんとコーナーケースを処理しなければ落ちてしまうことも多々あるため、うっかりそれを忘れてレートが下がったりもしています。
素早く、かつ正しく問題を理解することが大切ですね…。


TopCoder SRM

f:id:satanic0258:20161123230126p:plain
SRMのレートはこのようになっています。
SRMは結構レート変動が激しく、参加した回の半分も色が変わってしまっています(苦笑)。

一応青から黄色になったりしてはいますが、まだdiv1の問題を時間内に解いたことがないため、それが今後の課題となっています。
何とか競プロ2周年までには、div1easyを安定して解けるようになりたいですね。


  • (以下「続きを読む」部分、競プロでの様々なこと)

この先は、過去1年分のツイートを適当に抜粋して、あったことなどのコメントを加えただけのものなので、時間に余裕のあるときどうぞ。

(Twitterのツイートを大量に貼り付けているため、記事のロードに時間がかかる可能性があります)

言語

twitter.com
一番初め、本当に最初の頃はC言語で問題を解いていました。

しかし、機能面において色々つらい面がいくつか出てきたため、すぐにC++へと転身しました。
何故C++かというと、プログラミング言語C言語C++しか使えなかったためです。
(これは今も大して変わっていない)

多倍長の整数型が扱える言語もぼちぼち勉強すると色々楽そうですね(現状、C++でint型配列を使う方法を取っています)。


競プロ環境

twitter.com
4月頃、競プロの問題を解くのに何故か(?)Wandbox をよく使っていました。
PCはWindowsだったのですが、手頃に「コンパイル→サンプルを確認する」ということが出来る環境をまだ作っていなかったためだと思われます。


twitter.com
しかし、Wandbox では色々つらい部分も出てきたため、競プロを始める前から触っていたVisual Studioに戻ることにしました。

twitter.com
特にデバッグ機能や(これは長さ3の配列の5番目の要素を参照しようとしたときのエラーを検出している)、

twitter.com
スニペット登録が便利で重宝しています。


twitter.com
そして現在は、このように画面右に問題文、画面左にエディタ&コンソールという画面構成で競プロをしています。


練習・勉強方法

twitter.com
twitter.com
プログラミングには割と馴染みがあったので、初め競技プログラミングをやるにあたって「まずはアルゴリズムを学ぶところから始めよう!」と意気込んで、yukicoder の簡単な問題を解きながらアルゴリズムを勉強していました。


twitter.com
元々、問題を解いたりするのが全然苦ではなかったため、ゲームをするような感覚で問題を解き進め、最初の1週間はyukicoderで問題を46問解いていたみたいです。


twitter.com
そして、3週間弱でyukicoderの★1の問題を全て解き終わっていました。
よほど暇だったんだと思います(小声)。



twitter.com
競プロを始めて約3ヵ月、Twitterを眺めていると、「AtCoderコンテストがあるよ!」というツイートが見られたため、ものは試しとABC034に参加してみることにしました。
これが初めてのコンテスト参加です。
(結果等は後述します)

twitter.com
初め、
>>コンテスト<<
…と聞くと、何処か怖気づいてしまう部分がありました。しかし実際は、今まで問題を解いていたところに時間制限が付いたり、その早さによって順位が決まったりする、というだけで、何かプレッシャーを感じたり、失敗したからといって大きく損したりするようなものでもない、ということに気が付きました。

そこから、コンテストに参加するのも練習のひとつとして取り入れていくことにしました。

twitter.com
twitter.com
さらに、コンテストへのイメージが変わってからは、他のコンテストにもどんどん参加するようになりました。

twitter.com
英語(特にこどふぉ)に躓く部分もありますが、英語は英語でまた必要なスキルの一つであるため、日本/海外問わずコンテストには参加しています。



twitter.com
また、コンテストが終わった後はほぼ毎回Twitterで自分の解法を言うようにしました(このツイートはCodeFestival予選Bに対するものです)。

これには良い点がいくつかあります。
理解していることに対して解説を行うと、自分がどれくらい理解しているのかがわかります(解説というほどのものでもありませんが)。
さらに、それをアウトプットすることで他の人の助けとなったり、意見を共有・交換することが出来ます。

このことから、積極的に解説をしていこうと思いました。
(この「解説勉強法」は、試験対策や大学受験にも役立った記憶があります)



twitter.com
また、時には「自分が使えるアルゴリズムは何か/使えないアルゴリズムは何か/何故使えないか」をリストにまとめてみたりもしました。



twitter.com
競プロを始めてから4か月経って、競プロerは全員知っているであろう「蟻本」を手に入れました。

twitter.com
蟻本を買ったことで、「知らない技が出てきた→蟻本で確認!」の流れが出来たため、勉強の効率が良くなった気がしました。
(この頃から、「競プロのプロになりたい」という思いが強くなり始めたんだと思います)



twitter.com
それから、「自分は何が苦手か」ということを徐々に意識し出してきました。

twitter.com
そこで、苦手克服のためにまずはDPを完璧にしよう!と意気込んでTDPCの問題を解き始めました。
(しかしTDPCは難しく、まだ全部は解けていません)



twitter.com
twitter.com
また、たまにTwitterで競プロのプロから問題サジェストが飛んできたりして、とてもいい刺激になっていました。
(ありがとうございます)



成績

twitter.com
初めてのコンテスト、結果はAB+C部分点の2.5完でした。
ABC034の順位表
分からなかったのはC問題でコンビネーションを求める部分で、解説を見て
「逆元を求めよう!これはフェルマーの小定理を使ってできるよ!」
といった内容の文を見て、
「へぇ、そうなんだ…(無知)」
みたいな感じでした(ぶっちゃけそんなん知らんわ!と呆れたところもあったと思います)。



twitter.com
競プロを始めて5か月で、ようやくABCを時間内に全完することが出来ました。
これが早いのか遅いのかわかりませんが、成長を感じられて嬉しかったです。


twitter.com
また、Codeforcesは競プロを始めて11ヵ月で初めて4完することが出来ました。



twitter.com
そして今現在、どのコンテストサイトでも青コーダーとなっています。


twitter.com
さらに、CodeFestival2016への出場権もゲットすることが出来ました。

東京に行くには片道数時間数万円かかるため、中々オンサイトイベントには手を出せずにいましたが、「交通費・宿泊費無料!」という文に誘われ、参加を確定しました。
無事に行って帰って来ることが出来たら、CodeFestival2016の参加記を書きたいと思います。
(まだ一人で飛行機に乗ったり東京に行ったりしたことがないため不安がいっぱい)

[2017-02-22 追記]
無事生きて帰ってこれたので参加記を書きました。
satanic0258.hatenablog.com
[2017-02-22 追記ここまで]

最後に

twitter.com
twitter.com


ありがとうございました。