カレーちゃんブログ

Kaggleや競技プログラミングなどのこと

AtCoder緑色になりました

AtCoder緑色になったので、ここまでやったことと、どうやって始めたか、これから何をやるかなど書いてみます。
Atcoderの世界では、色変記事というらしい。

これからはじめる人の少しでも参考になってくれたら嬉しいですし、自分のモチベーションのアップになることも期待して書いています。

緑になるためにやったこと

Pythonで競技プログラミングをはじめることにして、「鹿本」、「鉄則本」という今年に入って発売された、次の2冊の本をやりました。
この2冊の本により、競技プログラミングに入門し一通りの知識を得ることができました。
とてもわかりやすい本で、もう神の本です。競技プログラミングを始める人にはとてもおすすめしたい。

アルゴリズム的思考力が身につく! プログラミングコンテストAtCoder入門

アルゴリズム的思考力が身につく! プログラミングコンテストAtCoder入門

Amazon

競技プログラミングの鉄則 (Compass Booksシリーズ)

競技プログラミングの鉄則 (Compass Booksシリーズ)

Amazon

この２冊をどこまで読み進めたかというと、１冊目の鹿本は、ほぼ全て読了。２冊目の鉄則本は半分程度読了しました。

どちらも、C++とPythonに対応で(鉄則本はJavaにも対応）、多くの人におすすめできます。 鹿本のほうが初級者向けだと思うので鹿本→鉄則本の順に読み進めるのが良いかなと思いました。（ある程度アルゴリズムができる人は鉄則本からでも良いのかもとも思いました）
練習問題がとても多いので、全部解きながら進めるとかなりの時間がかかります。
本については説明が長くなるので、細かい紹介は、今後公開するYoutubeでもう少し詳しく説明したいと思います。

これらの本がどこまで対応しているかは、鉄則本著者のE869120さんがまとめられていました。

競技プログラミングをはじめるにあたり役立ったこと

AtCoderを続けるにあたり使っているルールや環境です。これからはじめる人の役に立ってもらえると良いなというところ。

環境構築

Dockerで環境構築しました。PCが変わっても同じ環境で取り組めるので便利です。 適当にPython環境を作ってしまったので、これが最善かはわかりませんが特に不具合はおこっていません。 環境を作ったDockerfileなど一式を公開しておきます。（参考にした記事があったのですが、どれだっただろう...あとで探します）

この環境には、AtCoderからのテストケースなどのファイルのダウンロードや、提出ができるatcoder-cliと、online-judge-toolsといツールを入れています。これについて説明します。

atcoder-cli

コマンドラインツールatcoder-cliを公開しましたを見てもらうのがわかりやすいと思います。 私が使っているコマンドはコンテスト用ディレクトリ作成と提出機能。

例えば、abc(AtCoder Begiiner Contest)279のディレクトリを作成するときは
$ acc new abc279 とします。すると次のようにディレクトリが作成され、サンプルケースもダウンロードされる。

そこで私は、各問題毎にmain.pyというファイルを作って、問題を解いています。

AtCoderへの提出の時には、
$ acc submit main.py とします。PyPy3の時は、
$ acc submit main.py -- --guess-python-interpreter pypy
で提出。

online-judge-tools

提出する前は、テストケースで全てACするか試しておいたほうが良いので、その場合に使うのがonline-judge-toolsです。

main.pyにコードが書き終わったら $ oj t -c " python3 ./main.py" -d ./tests/
でテスト。次のようにテストケースがACするかテストできます。テストケースに通らないコードを提出してしまうのは、ペナルティがついてしまい損なので、このようなテストケースのACを確認できるツールは初心者には必須です。

AtCoder Problems

AtCoder Problemsというとても便利なサイトです。とても機能が多いのですが特に便利な点を3つ紹介します。

過去の問題の難易度を確認できる

まず便利なのが、過去の問題の難易度を見ることができるところ。（次の画像参照）ABCコンテストだと緑の人は大体Dぐらいまで解いているんだなーとか、この問題は茶色の人は大体解けるんだなーということがわかります。

易・適・難の３つで問題をレコメンドしてくれる

UserのRecommendationの箇所には、自分のランクに応じて、Easy、Moderate、Difficultの3つに分けて解くべき問題をレコメンドしてくれます。（詳しくはUser Guideのレコメンド参照） 私のランクだと、EasyだとDifficulty574~558、Moderateだと884~864、Difficultだと1193から1177の問題がレコメンドされました。（次の画像はDifficultのレコメンド）

簡単すぎる問題や、難しすぎる問題を解いても実力の向上にはつながらないので、ちょうど良い難易度の問題をレコメンドしてくれる機能は便利です。

Virtual Contests

AtCoder Problems上でAtCoderの過去の問題と時間を決めて、コンテスト形式で問題を解いて行くことができます。
他の人を誘って複数人でコンテスト形式で問題を解くこともできるし、1人でもコンテスト形式にすることで集中して解けるので重宝しています。
パフォーマンスの推定値も出るのて、単純に解いていても楽しいです。

提出されたコードの並び替え

AtCoderの過去問を解いて、他の人のコードを参考にする場合に、問題、言語、結果を入れて検索をするのはよくやると思います。
ただこれだけだと、とても数が多いので、ここから更に絞り込むための方法です。

問題、言語、結果で絞り上の画像のようになった画面で、提出日時、コード長、実行時間をクリックすることで、それぞれ提出日時の早い順、コード長の短い順、実行時間の短い順に並び変えることができます。 多くの場合は、強い人のコードを見ると参考になることが多いので、提出日時が一番早い順に並び替えて上から見ると参考になることが多かったです。
その他、コード長の短い順と実行時間の短い順も参考になることがありました。

AtCoderのお気に入り機能

AtCoderのサイト上で、参加者をお気に入りに追加することができます。
知り合いをお気に入りにしておき、コンテスト中はお気に入りが表示される順位表にしておくと、知り合いと勝負している感じになり、コンテスト中も楽しいです。

これから水色になるためにやること

競技プログラミングは楽しいですし勉強になるので、少なくても黄色になるぐらいまでは続けたいと思っています。
次の目標は水色になることです。 水色になるためにですが、
まだ鉄則本を半分までしか読めていないので、鉄則本を12月中くらいで読み切り、読み切った後は、鹿本と鉄則本の理解が不十分なところを復習したいと思っています。
おそらくそれで水色ぐらいには行くのではないでしょうか。 終わったら次のことも進めたい。

水色になった後に何をやるかは、水色になった記事でまた考えたいと思います。

その他参考にした資料など

終わりに

アウトライン書いてから時間がかかったけれど、緑になって次のコンテストに出る前に書けてよかった。茶色に落ちてしまったら書きづらいし笑
後ほど、Youtubeの動画も作ります。