こんにちは milkcoffeeです。AtCoderで青色になりました！
青になったら色変記事を書こうと決めていたので、早速はてなブログに登録してこの記事を書いています。
AtCoderを始めてから約一年経ちましたが、今までどんな勉強をしてきたのかをざっくり書こうと思います。
自己紹介
情報系学部に通っている大学三年生です。
AtCoderではmilkcoffeeという名前でやってます。
使用言語はC++です。
Twitterもやってます。(@milkcoffeen)
twitter.com
どんなアルゴリズムを勉強したか、どんな感じで問題を解いていたかを書きます。
AtCoder Problems の記録です(青になった時点)
大学の長期休暇に集中して精進しました。
基本は今の自分と同じ色と、自分より一つ上の色の問題をメインでやってました。水色になってからはVirtual Contest（主にくじかつ）によく参加していました。
Training や Recommendation はあまり使わず、ABCの過去問Tableを見て目に入ったものを解くことをやっていました。
ちなみに、考察にはノート(グリッド付き)を使っています。
以下では、各色のときに具体的に何をやっていたかを書いていきます。
灰色前半でやったこと
コンテストに出て、ひたすら言語に慣れることを繰り返していました。特に私は途中でC言語からC++に変えたこともあり、慣れるのに時間がかかりましたが、コンテスト中に調べながら問題を解いて勉強していきました。
コンテスト以外で問題を解くということはあまりしていませんでした。
灰色→茶色でやったこと
全探索（bit全探索、順列全探索など）や、簡単なアルゴリズム（累積和、いもす法、約数全列挙、素因数分解）を勉強しました。
精進では、過去のABCのB~C問題(主に灰Diff)を埋めていました。この辺りは分からなかったらすぐ解説を見てとりあえずコードを完成させる訓練をしていました。
茶色→緑色でやったこと
アルゴリズムは、UnionFindやBFS、DFSといったグラフ系のものを覚え始めました。しかし、どちらも内容を理解したというよりは、ライブラリとして使えるようにしただけでした。それでも基本的な問題は解けることもあったので良かったと思います。
また、蟻本を買ったんですが、内容が難しく感じてあまり読んでませんでした。(ナップザックDPが全く理解できなかった。)
精進では、過去のABCのD～Eの中で解けそうなもの(主に茶～緑Diff)を埋めていました。また、Streakを繋ぐためだけに灰色の問題を解く日もありましたが、やっぱりコードは毎日書いた方が書くのが早くなって良いと思います。
緑色→水色でやったこと
この時期に一番アルゴリズムについて勉強しました。主にE8さんの競プロ上達ガイドライン中級編に書かれていることを勉強していきました。
最短経路問題(ダイクストラ法、ワーシャルフロイド法、ベルマンフォード法)、最小全域木問題(プリム法、クラスカル法)、動的計画法(ナップザックDP)について勉強し、理解できました。また、BFSやDFSについての応用問題も解けるようになりたいと思い、何も見ないで自力で書けるようにしました。蟻本の内容も理解できるようになり、寝られない夜に布団の中で読んだりしてました。
また、C++のSTLにあるデータ構造(stack、queueなど)を勉強して使えるようにしました。
精進について、Virtual Contest(主にくじかつ)に積極的に参加しました。Virtual Contestのように限られた時間で問題を解く練習は、本番中に良いパフォーマンスを出す練習としてかなり効果が高いと思います。
この頃に競プロ用のTwitterアカウントを作り、同じくらいのレベルの人や強い人をたくさんフォローしました。コンテスト終了後は問題の感想や別解などが見れるので、勉強にもなりますし、モチベーション維持にも最適ですね。
水色→青色でやったこと
アルゴリズムについては、これまで理解できなかった難しいものを理解して自力で実装できるようにしました(bitDP、区間DP、桁DPなど)。EDPC(Educational DP contest)の問題を埋めて、DPへの理解を深めました。EDPCの効果はかなり大きいと思います。他にはセグメント木、行列累乗、写像12相、LIS、LCAなども勉強しました。(セグメント木についてはもっと早くやっとくべきでした。)
精進については、続けてくじかつに参加しました。それ以外にも、実装練習のために緑Diff、考察訓練のために水～青Diffを解く、という感じの精進をしました。水Diffについてはできるだけ早めに解く、青Diffについては時間をかけてじっくり解くという感じです。
また、Codeforces に参加するようになりました。典型問題の練習になったと思います。
個人的に「原理を理解しやすい」と思った順に、自分が知っているアルゴリズムを並べました。出やすさ、実装しやすさはほとんど考慮してません。色は自分がそのアルゴリズムを勉強したときの色です。
アルゴリズムの基礎的な問題はAOJ(Aizu Online Judge)にたくさんあります。AtCoderの問題はアルゴリズムを応用する問題が多いので、勉強したばかりのものは先にAOJで定着させると良いです。
何から勉強していいか分からないときはこれの順にやってみてください。
- 約数全列挙
- 順列全探索
- 逆元
- bit全探索
- 二分探索
- 累積和
- いもす法
- 素因数分解(エラトステネスの篩)
- しゃくとり法
- Union Find
- 幅優先探索
- 深さ優先探索
- ナップザックDP
- ワーシャルフロイド法
- ベルマンフォード法
- ダイクストラ法
- クラスカル法
- 半分全列挙
- 写像12相
- LIS(最長増加部分列)
- bitDP
- 区間DP
- 桁DP
- セグメント木
- BIT
- LCA(最長共通祖先)
- 行列累乗
やって成功だったこと
青色になるまでの取り組みで、レートを上げるのに貢献したであろう行動です。
当たり前ですが、これは私が一番大切にしていたことです。時間に少し遅れたり、提出したことでレートが下がるのが不安だったりしても必ず参加(提出)していました。コンテストに出たことで一時的にレートが下がっても、そのコンテストに出た経験のおかげで、将来的にレート上昇につながると考えていました。実際に、本番の時間内で考察をしてコード化するスピードが身に付き、問題を通せなかった悔しさは勉強のモチベーションになりました。
Virtual ContestやCodeforcesに参加した理由も同様で、やはりコンテストで良いパフォーマンスを出すにはコンテストに出るのが一番の訓練になると思っています。
自分と同じくらいのレベルのライバルがたくさん見つかることでモチベーションになりました。また、分からないときは強い人がすぐに教えてくれるので助かりました。コンテスト後に他の人の感想を見るのも楽しいですね。
水色になったあたりから始めた取り組みで、自分で競プロの問題の案を作ってスマホのメモ帳に貯めていました。問題を考えることで、パソコンを触ってない時間にも考察トレーニングになるし、作問者の気持ち(ひっかけポイントなど)も分かります。また、自分の考えた問題が本番中に出ると爆アドです。一度ARCで自分のオリジナル問題と完全に同じ問題が出たことがあります。作問についてはまた別の記事でお話しようと思います。
反省点
皆さんはコンテスト後に自分が解けなかった問題を復習しますか？自分はコンテスト終了後は気が抜けてしまって復習をほぼせず、しばらくしてから解き直すみたいな感じです。コンテストの復習はその日のうちにやる方が良いと思いますが、中々できませんでした・・・
精進のとき、パッと見で苦手そうなときや、少し考えて全然分からなそうなときは、解説を見ずに別の問題に移ることがよくありました。これでは自分の苦手分野が克服されず、また新しい知識や考え方も得られないと思うので、直したいです。
まとめ
青になったばかりですが、黄色を目指して頑張りたいですね。まずは水Diffと青Diffを埋めて、少しずつ黄Diffも解けるようになっていきたいです。一年後に黄色を目指します！（最終的には橙色になってABCで作問するのが夢）
記事はこれで終わりです。初めての競プロ記事ですが読んで下さりありがとうございました！これからまた競プロに関する記事を投稿するかと思います。
