中学一年生のMagentorです。2022/12/10のABC281にて無事入水しました。
0 はじめに
0.1 自己紹介
こんにちは、Magentorです。某国立中学校に入っていて、半年ほどAtcoderをしています。
使用言語はC++です。
また、Atcoderの他にも、yukicoderやOMCをしています。
0.2 この記事について
この記事では、私が入水するまでの精進や、入水するまでの出来事について話したいと思います。
多くの方に読んでいただければと思っています。(ですが、入水記事は山程あるので、参考になる部分は少ないと思います)
途中、競技プログラミングにあまり関係のないことが書かれているので、Atcoderでの精進などについて知りたい方は読み飛ばして下さい。
1 競プロ、そしてAtcoderに出会うまで
1.1 始まり
中学受験が終わった後、2月ごろにPythonを始めました。しかし、その時はまだ忙しく、よく分からなかったので挫折してしまいました。
その後、中学校に入学してゲームを作ろうと思い、パソコン研究部に入りました。
このパソコン研究部の公式サイトで競プロやAtcoderを知ったので、Atcoderを始めることにしました。
つまり、プログラミングを始めたのは競技プログラミングが目的ではありません。
パソコン研究部の先輩にC++を始めるように言われたので、C++を学ぶことを始めました。
幸い、C++にはAPG4bがあったので、基本的な文法や計算量の概念をある程度身につけることが出来たとは思います。
1.2 初めてのコンテスト
パソコン研究部に入学した時はゴールデンウィークが近く、主要なコンテストもあまりないので、ABC(Atcoder Beginner Contest)の問題を数問解きました。
そして、ABC250に参加しました。初めてのABCです。そのころは、アルゴリズムや計算量の概念についてあまり理解していなかったので、2完。当然の結果です。
しかし、その頃は同レート帯の中では比較的A,B問題を早く解く方だったので、C問題が難しかったこともありパフォーマンスは417でした。
その後、パソコン研究部の新入生を対象にしたバーチャルコンテストに参加しました。
2 入茶まで
2.1 アルゴリズムを学ぶ
その後もコンテストに参加しましたが、C問題が中々解けず、パフォーマンスもあまり上がりませんでした。そこで、まずは基礎的な文法知識を身につけるため、A,B問題を埋めることを始めました。
最初のうちは、B問題を解くのに30分以上の時間を要していましたが、精進によって簡単なものであれば10分でB問題を解くことが出来るようになりました。
そこで、C問題にも手をつけ始めました、比較的簡単な工夫で出来る、dpなどのアルゴリズム,データ構造を用いないものはAC出来ますが、AC出来ない問題がありました。
その問題の解説を見ると、dpやmultisetなどのアルゴリズムやデータ構造について書かれていたので、色々なアルゴリズムやデータ構造を学ぶことにしました。
(「アルゴリズムとデータ構造」と聞くと、大槻兼資氏の「問題解決力を鍛える! アルゴリズムとデータ構造」を思いつきますが、この本については次の章で扱います)
アルゴリズムやデータ構造を学ぶ際に利用したのが「レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】」です。この記事は、水色になるために必要なアルゴリズムやデータ構造、関数についてとても分かりやすくまとめられており、アルゴリズムの理解に役立ちました。茶色になるためにはこれらのアルゴリズムは必要ないかもしれませんが、結果的に入茶した後に早く入緑することが出来たので、十分意味があったと考えています。
また、精進をすることで、計算量を改善するための考え方が少し分かるようになったと思います。(C問題程度のものですが)
そして、ABC255で初めてC問題をACしました。C問題が数学問であることも影響していたと思います。
その後、ABC257でD問題をACして緑perfを出し、入茶しました。D問題のいもす法を自力で思いついたことが影響していると思います。
入茶するまでに学んだアルゴリズム/データ構造
理解度について:
- A:仕組みを完全に理解し、応用も出来る
- B:実際にそのアルゴリズム/データ構造を使うことが出来る
- C:そのアルゴリズム/データ構造について学習した
- D:まだ学習していない
| 全探索 | A |
| bit全探索 | A |
| 順列全探索 | A |
| 二分探索 | A |
| DFS | C |
| BFS | C |
| 基本的な動的計画法 | B |
| 高速な素数判定法 | B |
| べき乗を高速に計算する手法 | B |
| 累積和,imos法 | B |
| 木 | C |
| グラフ | C |
| Unionfind | C |
このように、茶コーダーになるために必要なアルゴリズムは非常に少ないです。
実際、現在のABC-C程度の問題は、これらのアルゴリズムが必要となる問題は少なく、少し工夫をすることでAC出来る問題が多くなっています。
3 入緑まで
2.1でも述べた通り、入茶した後はグラフ理論やそれに関連するアルゴリズム、動的計画法など、ABC-D問題で良く出るようなアルゴリズムをすでに学んでいたので、入茶してから約10回ほどのコンテストである、ABC263で入緑することが出来ました。この回では、2回目の水perfを出すことが出来ました。
入緑するまでに学んだアルゴリズム/データ構造
理解度について:
- A:仕組みを完全に理解し、応用も出来る
- B:実際にそのアルゴリズム/データ構造を使うことが出来る
- C:そのアルゴリズム/データ構造について学習した
- D:まだ学習していない
| 全探索 | A |
| bit全探索 | A |
| 順列全探索 | A |
| 二分探索,三分探索 | A |
| DFS | A |
| BFS | A |
| ダイクストラ法 | B |
| ワーシャルフロイド法 | C |
| クラスカル法 | B |
| 基本的な動的計画法 | A |
| 高速な素数判定法 | A |
| べき乗を高速に計算する手法 | A |
| 累積和,imos法 | A |
| 木 | A |
| グラフ | A |
| Unionfind | B |
4 入水まで
順調に入緑することが出来ましたが、ここで私は苦しみました。
レートが1000台までは順調に上がりましたが、その後、レートが下がることが多くなりました。
この原因として、
- D問題を早く解くことが出来なかった
- 同色レベルの実装力が無かった
- E問題を全く解けずにいた
などがありました。この問題を解決するため、精進を繰り返しました。しかし、私の学校では10月に文化祭があり、文化祭の作業などもあって精進をあまりすることが出来ませんでした。そこで、なるべく少ない量の精進で水色になるため、分野別 初中級者が解くべき過去問精選 100 問の問題などを埋めることを意識しました。
結果、文化祭が終わった後の11/12月頃に水perfを安定して出せるようになり、12/10のABC281で入水しました！
(しかし、E問題を早く解くことや、実装力を上げることなど、多くの課題が残っています。)
入水するまでに学んだデータ構造やアルゴリズム
入水するために特に必要だと感じたアルゴリズムは太字になっています。
理解度について:
- A:仕組みを完全に理解し、応用も出来る
- B:実際にそのアルゴリズム/データ構造を使うことが出来る
- C:そのアルゴリズム/データ構造について学習した
- D:まだ学習していない
| 全探索 | A |
| bit全探索 | A |
| 順列全探索 | A |
| 二分探索,三分探索 | A |
| DFS | A |
| BFS | A |
| ダイクストラ法 | A |
| ワーシャルフロイド法 | B |
| クラスカル法 | B |
| 基本的な動的計画法 | A |
| 高速な素数判定法 | A |
| べき乗を高速に計算する手法 | A |
| 逆元の計算 | A |
| 累積和,imos法 | A |
| 座標圧縮 | B |
| 半分全列挙 | B |
| 行列累乗 | B |
| ダブリング | A |
| Grundy数 | C |
| Roling Hash | D |
| 平方分割 | D |
| 最大流,最小カット,二部マッチング | B |
| 木 | A |
| グラフ | A |
| Unionfind | B |
| セグメント木 | A |
| 遅延評価セグメント木 | C |
5 さいごに
ここまでこの記事を読んでくださった方、ありがとうございます。もしよろしければ感想などをいただけると嬉しいです。
1章でも述べた通り、プログラミングを始めた理由はゲームを作るためでした。そのため、しばらくAtcoderでレートを上げ、入水したらゲームを作り始めようと考えていました。ですが、競技プログラミングをしているうちに、もう少し高いレートを目指したいと思い、入水しても競技プログラミングを続けようと思いました。
入水が元々の目標で、入青することはあまり考えていませんでしたが、もう少し頑張ってみようと思います。入青出来た際にはまたqiitaで記事を書こうと思っているので、読んでいただければと思っています。