ぶちのブログ

競プロとCTFが趣味なWebエンジニアのアウトプットの場

AtCoder水色から青色になるまでにやったこと

はじめに

今年の1月から本格的に競技プログラミングに取り組み始めて、先日のAtCoderのコンテストで青色の仲間入りを果たしました
1月時点での頃の目標が1年半以内に青色だったので、かなり早く達成することができて、とても嬉しいです。

f:id:betit0919:20190812232450p:plain

参考になるのかはわかりませんが、自分の勉強した内容や取り組みを紹介します。
なお、水色になるまでの記事はこちらです。(こちらは具体的なアルゴリズムについては書いていません)

精進

f:id:betit0919:20190812232940p:plain

水色から青色になるのに約4ヶ月かかりました。
その間の努力目標は、「毎日ABC-D(400点-500点のもの)を解く」で、どうしても時間がないときだけABC−Cを早解きしました。 また、解いた問題は必ず解説をちゃんと読んでいました。

f:id:betit0919:20190813001404p:plain

仕事との兼ね合いもあり、モチベーションを切らさないことを第一に考えると、1日30分程度の精進が限界だったため、効果を最大化するようにしていました。
具体的には、自分の実力に合わせた問題を、自分の実力で適切な時間内に解くように心がけていました。

難易度と自分の実力を見積もるという行為自体が、コンテストでの安定したパフォーマンスにもつながっていたと思います。

コンテスト

とにかくコンテストの出場数は重要だと考えています。ほとんどのRatedコンテストに出ていました。
毎週のように、「今週300点問題解いた日が多くて冷えそうだから出たくないな」と思いながら出ました。これは我ながら誇れると思います。

また、コンテストの当日は、新たなアルゴリズムや概念を一つ理解することを目標に、慌てて勉強していました。

コンテストでは、落ち着いて実力を出すことだけ考えていました。
令和ABCの結果をまとめたのがこちらです。

f:id:betit0919:20190813000736p:plain

全体的にかなり安定していたと思います。普段から問題の難易度を順位表と感覚から見積もっていたおかげで、
「400をこの時点で通せれば、レートが極端に下がることはない」
「500を通しさえすれば、レートは上がる」
といった感じに、かなり落ち着けていたと思います。

自分の場合は、500をそこそこの勝率で通せれば青色になるには十分だと判断していたので、600は精進の対象外でした。

読書

螺旋本とチーター本を流し読みで一周しました。また、蟻本は3-4(フローの前)くらいまで必要に応じて何度も読んでいました。
読んだ際には手を動かすことはせず、概念や考え方などの抽象を把握することに心がけていました。

また、友人からアルゴリズムイントロダクションを借り、8章くらいまで流し読みしました。
加えて、競プロのためだけではありませんが、離散数学の教科書と圏論の基礎の教科書を少しだけ読んでいました。

具体的にできるようになったこと

グラフは400-500の勝負どころに頻出なので、重要でした。

  • 基本から少し応用程度のDP

方針さえ立てばちゃんとバグらせずに実装できるようになっていました。

実際には殆ど使ってませんが、基本的な問題ならば解ける自信はあります。

  • priority_queueやsetなどの基本的なデータ構造への理解
  • 計算量についての理解

これらは、実感はしにくいのですが、基礎としてかなり重要だと考えています。
それぞれのデータ構造がどういうものか、内部実装もふんわりと理解しながら、適切に使い分けることができるようになっていました。
アルゴリズムイントロダクションを流し読みしたのが大きかったかもしれません。

特に、情報系の学部を出ていない方で伸び悩んでいる方は、毛嫌いせずにCSの基礎を学んでみてはいかがでしょうか?

まとめ

精進は続けることが大事というスタンスなので、極端に多くの問題は解いていません。
一方で、コンテストには出続けることが大事です。コンテストの直前、最中の集中力を生かさない手はありません。
また、アルゴリズムの本やCSの本を読んでいた分量は多く、個人的にはかなり重要なファクターだったと考えています。

終わりに

いつかは黄色になりたいです。とりあえずAGC-BかABC-Fを、それなりの勝率で解けるようにならないといけなさそうという感じです。
頑張りすぎたりサボりすぎたりして、習慣を失わないようにだけ気をつけつつ、気長に頑張っていきます。

今後もよろしくお願いします。