はじめに
こんにちは！ 中学3年生のAwashAmityOakと申します。私は競プロerで、AtCoderというサイトでコンテストに参加しています。今回の記事は、そのAtCoderで入青(Rating 1600に到達)したことについてです。
とても長いので、お時間があるときにお読みください。
前回の記事
入緑記事です。
入水記事は書いていません。入水したときは、ちょうど予定が詰まっていて多忙な時期だったので、後で書こうと思っていたら、1週間、1ヶ月が過ぎていってしまい…(言い訳)
対象読者
- AtCoderのコンテストに参加したことがある人(界隈の用語を多用するので、知らないと読みにくいです)
入青！
2024年10月19日に開催されたABC376で入青しました！
6月1日に入水してから、4ヶ月3週間経っていたそうです。AtCoderを始めてからは、1年と3週間経っています。(なので、タイトルは若干盛っています…)
入青したコンテストの感想
私は、ABC372で初めての6完を果たし、さらにABC375でも6完し、かなり波に乗っている状態でした。そこで臨んだ今回のコンテストですが、正直入青できるとは思っていませんでした。しかし、終了6分前にF問題をACし、3度目の6完をすることができました！また、上記のポストにもあるとおり、初めての黄パフォをとり、自分の最高順位を更新できたため、とても輝かしい結果となりました。(嬉しい
)
以下、ABC376のネタバレを含みます。(かなり長いです)
コンテスト中の詳しい様子
かなり難しい問題たちでした。今回のB問題とF問題はセットになっていて、同じような問題設定になっていました。https://atcoder.jp/contests/abc376/tasks/abc376_b
https://atcoder.jp/contests/abc376/tasks/abc376_f
簡単に言うと、あるリングを右手と左手で持ち、「右or左手をここに移動しろ」という指示が与えられ、これを最小手数で達成する問題でした。コンテスト中、初めて見たときは「これやばいな…。」と思いました。円環状の位置関係を扱う問題に苦手意識があり、解けるか不安になっていました。
A→C→D→E→Bの順番で5完した後、F問題を考え始めました。少し考察するとDPだということにはすぐ気づいたのですが、場合分けがかなり多くなることが予想されました。30分ほどかけてなんとか実装しても、サンプルは合わず。この時点で青パフォは取れていたので、「5完でも、もういいか」と心のどこかで思い始めていました。
しかし、6完できそうなチャンスを逃したくはありません。もう1度コードを見直してみると、場合分けの漏れがあることに気がつきました。それを付け加えようとした矢先、あるアイデアが頭の中に浮かびました。
移動先を0に固定して考えれば、場合分けが3分の1になる！
思いついたアイデアを実装するのはすぐできました。サンプルを試すとすべてAC。最後にバグがないか、コーナーケースがないかをざっとチェックし、いざ提出ボタンをポチ！
…数秒後、ステータスの表示がACに変わるやいなや、通ったことの喜びで歓声を上げました。改めて、ac-predictorの表示を見ると、黄パフォと入青の表示が出ていたので、はしゃぎまくっていました。また、コンテスト後にわかったことですが、始めてコンテスト中に黄diffを通したので、そのことについてもかなり嬉しかったです。
競プロにおいて、諦めない根気はかなり大きな強みだと、今回のコンテストで改めて感じました。
青Coderってどれくらいすごいの？
こちらの記事には、以下のように書かれています。
AtCoderにおける分布(2023/11/20現在)
実レーティング分布： 上位3.609%
内部レーティング分布： 上位5.725%
期待できる能力
普通のITエンジニアから見て、常軌を逸したコーディング速度を持ち、複雑なロジックにおいてもバグの少ない安定したロジック構築が可能となります。
大抵の業務においてはここまでのレーティングは必要とはなりませんが、例えば、大きなデータを扱う・数理的な処理を扱う・研究開発に近い業務を行う・論文などをキャッチアップして実装までするような業務を行う場合は、大きな力となります。
競技者としては、旧帝大や早慶などの、競プロ強豪校を除いた、大学のエース選手がこの水準です。よほど関連した業務などを行っていない限りは、競プロの練習なしにこの水準のパフォーマンスが安定して出せるITエンジニアはいないと言っても良いでしょう。
常軌を逸したコーディング速度！ 嬉しすぎます。
個人的な見解を述べると、中学生で青Coderはかなりすごいです。9月に終了したAtCoder Jounior League 2024 Summerを見ると、中学3年生には、青Coder以上が9人しかいません！
(上位10人に入れたぞ〜！ヾ(≧∇≦*)/やったー)
やったこと
コンテスト参加
これをしないとRatingが上がりません。私は、余程のことがない限り、毎週コンテストに参加しています。
余談ですが、7月頃に自分のPCのOSを消し去ってしまったときに、復旧のため、2週間ほどブランクが空いてしまったことを少し後悔しています。
過去問埋め
いわゆる「精進」です。私は、なるべく毎日、水diffを埋めることを意識してやってきました。青diffはそこまでたくさん解いているつもりはなかったので、入青できたのが少し不思議でもあります。
言いたいことは、自分のRating帯の問題を必ず解けるようにするということです。私は、自分の色よりはるかに上の難易度の問題を解くより、自分と同じ色の問題を大量に解く方が、効果があると思います。(もちろん個人差はあると思います。)
写真集
入青したときのデータを載せておきます。入青してから少し日が経ったときに撮影したため、解いた問題数などに多少のズレがあります。
 |
|---|
| https://atcoder.jp/users/AwashAmityOak |
 |
|---|
| https://kenkoooo.com/atcoder/#/list/AwashAmityOak |
 |
|---|
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
| https://kenkoooo.com/atcoder/#/user/AwashAmityOak |
 |
|---|
| https://atcoder-graphs.vercel.app/#contributorGraph |
アルゴリズムの習得
入青までに学んだアルゴリズムを紹介します。参考にしていただけると幸いです。
ある程度分類はしていますが、分類が難しいアルゴリズムもあるため、若干違和感があるかもしれません。ご了承ください。
「理解度」と「実装方法」という2つの項目を設けています。
「理解度」は以下のような観点で、5段階で評価しました。
| 数字 | 意味 |
|---|---|
| 1 | 名前だけ知っている |
| 2 | 仕組みだけ知っている |
| 3 | 習得済み(コンテストでは出たことがない or 解けたことがない) |
| 4 | コンテストで出たら大体解ける |
| 5 | コンテストで出たらほぼ確実に解け、自分が得意だと感じている |
「実装方法」は、私がコンテスト中にどのような方法で実装しているかを表しています。(未習得だったり、評価が難しかったりするものは、ないこともあります)
| 絵文字 | 意味 |
|---|---|
 |
その都度手打ちする |
 |
自作のテンプレートを使う |
| その他 | ライブラリ名とクラス名・関数名を記載 |
探索
| アルゴリズム | 理解度 | 実装方法 |
|---|---|---|
| 全列挙 | 5 | |
| bit全探索 | 5 | |
| 順列全探索 | 4 |
+STL(next_permutation) |
| 半分全列挙 | 2 | - |
| 配列の二分探索 | 5 | |
| 答えで二分探索(決め打ち二分探索) | 4 |
or STL(ranges::partition_point, views::iota) |
| 尺取り法 | 4 | |
| 三分探索 | 3 | |
テクニック系
| アルゴリズム | 理解度 | 実装方法 |
|---|---|---|
| 貪欲 | 5 | - |
| 座標圧縮 | 5 |
+STL(sort, unique, erase) |
| 平面走査 | 4 | - |
| マージテク | 4 | - |
| 主客転倒 | 4 | - |
| 平方分割 | 2 | - |
| Mo's Algorithm | 1 | - |
区間演算
| アルゴリズム | 理解度 | 実装方法 |
|---|---|---|
| 1次元累積和 | 5 | |
| 2次元累積和 | 5 | |
| 3次元累積和 | 5 | |
| imos法 | 4 | |
| 累積演算 | 4 | |
| フェニック木(BIT) | 3 | ACL(fenwick_tree) |
| セグメントツリー | 5 | ACL(segtree) |
| 遅延セグメントツリー | 4 | ACL(lazy_segtree) |
| 二次元セグメントツリー | 2 | - |
グラフ
| アルゴリズム | 理解度 | 実装方法 |
|---|---|---|
| グラフ上のDFS | 5 | |
| ゲームDFS | 5 | |
| グラフ上のBFS | 5 | |
| 状態を伝うBFS | 5 | |
| ダイクストラ法 | 5 | |
| ワーシャルフロイド法 | 5 | |
| ベルマンフォード法 | 3 | |
| UnionFind | 5 | ACL(dsu) |
| ポテンシャル付きUnionFind(重み付きUnionFind) | 3 | |
| モノイド付きUnionFind | 4 |
+
|
| 二部グラフ判定 | 4 |
+ACL(dsu) |
| クラスカル法 | 5 | |
| プリム法 | 3 | - |
| 強連結成分分解(SCC) | 4 | ACL(scc_graph) |
| 最近共通祖先(LCA) | 1 | - |
| オイラーツアー | 1 | - |
| 木の重心 | 3 | - |
| 木の直径 | 4 | |
| 重心分解 | 1 | - |
| 橋検出 | 2 | - |
| 関節検出 | 2 | - |
| Trie木 | 3 |
+
|
| 最大流 | 3 | ACL(mf_graph) |
| 最小費用流 | 3 | ACL(mcf_graph) |
| 二部グラフの最大マッチング | 3 | ACL(mf_graph) |
| 最小シュタイナー木 | 1 | - |
| Linc Cut Tree | 1 | - |
DP
| アルゴリズム | 理解度 | 実装方法 |
|---|---|---|
| 1次元DP | 5 | |
| 2次元DP | 5 | |
| 最長増加部分列(LIS) | 4 | |
| 最長共通部分列(LCS) | 3 | |
| 区間DP | 1 | - |
| 期待値DP | 5 | |
| 確率DP | 4 | |
| bit DP | 4 | |
| 全方位木DP | 3 | |
| 桁DP | 2 | - |
| 竹DP | 1 | - |
| chokudai DP | 5 | |
| 耳DP | 2 | - |
| inline DP | 5 | |
ハッシュ
| アルゴリズム | 理解度 | 実装方法 |
|---|---|---|
| ローリングハッシュ | 3 | |
| Zobristハッシュ | 4 | |
数学
| アルゴリズム | 理解度 | 実装方法 |
|---|---|---|
| 繰り返し二乗法 | 5 | |
| ダブリング | 4 | |
| 行列累乗 | 2 | - |
| 包除原理 | 3 | - |
| Grundy数 | 5 | |
| Nim | 5 | |
| 調和級数 | 4 | - |
| modint | 4 | ACL(mint) |
| 階乗 | 5 | |
| 二項係数 | 4 | |
| エラトステネスの篩 | 4 | |
| 素数判定 | 5 | |
| 素因数分解 | 5 | |
| ユークリッドの互除法 | 5 | |
| 拡張ユークリッドの互除法 | 3 | |
| 中国剰余定理(CRT) | 2 | - |
| 高速フーリエ変換(FFT) | 1 | - |
| 高速数論変換(NTT) | 1 | - |
| 形式的冪級数(FPS) | 1 | - |
| 高速ゼータ変換 | 1 | - |
| 高速メビウス変換 | 1 | - |
| floor sum | 1 | - |
| Convex Hull Trick | 2 | - |
見ての通り、私はテンプレートをあまり整備していません。ほとんどのアルゴリズムを手で打ちます。
新しいアルゴリズムを勉強するときは、主に鉄則本などの書籍や、EDPCなどの常設コンテストを利用しました。
Trie木や、全方位木DP、ローリングハッシュなどについては、解説されている本を持っていなかったり、学習サイトが見当たらなかったりしました。そのときには、これらアルゴリズムが想定解の問題を検索して、ネット上の記事を参考にしながら、解説ACしました。
テンプレートの整備
早解きで有利になるので、テンプレートを整備しましょう。(前述したとおり、私はあまりやっていませんが…)
ネット上に転がってる記事や、上位の人の提出コードを参考にするのが良いです。私は、このようなテンプレートを使っています。
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using mint = modint998244353;
istream& operator>> (istream& is, mint& x) { long long _x; is >> _x; x = _x; return is; }
ostream& operator<< (ostream& os, const mint& x) { return os << x.val(); }
template<class T, class U>
ostream& operator<< (ostream& os, const pair<T, U>& x) { return os << "{" << x.first << ", " << x.second << "}"; }
#define int ll
#define OVERLOAD_REP(_1, _2, _3, name, ...) name
#define REP2(i, l, r) for (int i = (int)(l); i < (int)(r); ++i)
#define REP1(i, n) REP2(i, 0, n)
#define rep(...) OVERLOAD_REP(__VA_ARGS__, REP2, REP1)(__VA_ARGS__)
#define RREP2(i, r, l) for (int i = (int)(r)-1; i >= (int)(l); --i)
#define RREP1(i, n) RREP2(i, n, 0)
#define rrep(...) OVERLOAD_REP(__VA_ARGS__, RREP2, RREP1)(__VA_ARGS__)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define pb push_back
#define mp make_pair
#define mt make_tuple
const int INF = 4e18;
const int MOD = 998244353;
const int MOD1 = 1e9 + 7;
template<class T> inline bool chmax(T &a, T b) { return a < b ? a = b, 1 : 0; }
template<class T> inline bool chmin(T &a, T b) { return a > b ? a = b, 1 : 0; }
template<class T> T pow(T a, T b, T m) { return b ? b&1 ? a*pow(a, b^1, m)%m : pow(a*a%m, b>>1, m)%m : 1; }
template<class T> T pow(T a, T b) { return b ? b&1 ? pow(a, b^1)*a : pow(a*a, b>>1) : 1; }
template<class... T> inline void input(T&... a) { ((cin >> a), ...); }
template<class T, class... U> inline void print(const T& a, const U&... b) { cout << a; ((cout << " " << b), ...); }
template<class T, class... U> inline void println(const T& a, const U&... b) { print(a, b...); cout << endl; }
inline void println() { cout << endl; }
template<class T> inline void print(vector<T>& A) { rep(i, A.size()) if (i) print("", A[i]); else print(A[i]); }
template<class T> inline void println(vector<T>& A) { print(A); cout << endl; }
const int di[8] = {-1, 0, 1, 0, -1, -1, 1, 1};
const int dj[8] = {0, -1, 0, 1, -1, 1, -1, 1};
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
AtCoder Daily Trainingへの参加
私は、余裕があるときだけやっていました。ADTALLでは、全ての問題に占める灰diffの割合が多めです。時間を計って問題を解くことで、早解き力が鍛えられます。
また、水Coderになってくると、ADTで1位を狙えることも増えてくるため、モチベアップに繋がります。(私はまだ1度も1位を取れたことはありませんが…)
私が競プロをするときに意識していること
とにかく長いです。
解説を見る前に1日おく
自力で解く力を身につけるために、私が実践していることです。精進をしていると、どうしても解けない問題が出てくると思います。そんなとき、解説やテストケースを見るのが一般的だと思いますが、私はそうする前に必ず1日おきます。日を跨ぐことで、解法が思いつくことがありますし、それで自力ACできれば自信もつきます。
もちろん、長い時間考えて自力ACできることに越したことはないのですが、時間は有限です。自分にとって難しすぎる問題を考え続けて時間を費やすよりは、難易度がちょうどよい問題を解くほうが効率的です。そこを吟味した結果、「1日」という時間が私にはぴったりでした。
実際に1日おくときは、学校の休み時間などに考察するようにしています。
AIを使わない
2024年10月19日現在、AtCoderは、ABCにおいて、AIに問題文のテキストや画像を直接与えることを禁止しています。しかし、人間が手打ちで入力した情報をAIに与えることは許可されています。
ここで言う「AIを使わない」ということは、このルールの範囲内でのAIの使用もやめるということです。これを念頭に置いた上でお読みください。
2024年11月15日、AtCoderでの生成AIに関するルールがさらに厳しくなりました。ABC/ARCにおけるAIの使用が、一部の例外を除いて、原則禁止になるようです。
ここでの話は、まだAIの使用が許可されていた頃のものなので、現在の状況とは少しずれています。ご了承ください。
コンテスト中にAIは使わないようにしましょうという話です。
私は、入水したABC356で、D問題をChatGPTで通してしまいました。
順位表からわかるとおり、コンテスト終了33秒前にこのコードを提出しました。切羽詰まった状況でもあり、AIを使ったことで生じる気持ち的な問題について、冷静な判断ができなくなっていました。
実際、コンテスト後、深い後悔を感じました。順位表と照合したところ、たとえD問題が解けていなくても入水できていたことがわかったのです。コンテスト中にAIを使ったことで、「水Coder」という称号が、「虚偽のものだ」というような気がしました。もし、AIを使っていなかったら、晴れ晴れとした気持ちで「水Coder」を名乗れていたはずなのに…
このようなことがあって以降、AIを使わないことを心に決めました。AIによって自分の実力をかさ増しすることはできますが、それは本当の実力ではありません。「いや、そんなことない。今の時代、AIを使いこなせてこそ、実力があると言える」と言って、特に気にしない方もいるかもしれません。しかし、競技プログラミングという世界で生きている自分にとって、自分のRatingにAIの分が含まれたことは、自分の名前に泥を塗るのと同じでした。
今、灰Coderや茶Coder、緑Coderの中で、コンテスト中にAIを使用している人もいるかと思います。しかし、AIに頼ってばかりでは、いずれRatingが上がらないときが来ます。AIを補助的(自分の実装速度を補うため)に使っている場合でも、やはりAIを使わずに得たRatingの方が嬉しいと思います。
いつか悔しい思いをしたくなければ、AIは使わないようにしましょう。
(ここまで言っておいてですが、私は別にAIを使っているからといって、その人を嫌うことはありません。AIを使っている方であっても、普通に仲良くしてください！)
(前述したとおり、AIの使用が原則禁止になったので、こういうことは言えなくなってしまった…)
1LL << K(C++)
私が1番さいなまされてきたバグなので書かせていただきます。C++で実装をするときの注意点です。
Pythonなどと違って、C++などのコンパイル言語では、数値がオーバーフローをすることがあります。競プロでも気をつけなければいけないことの1つで、int型の代わりに、long long型を使うことで回避するのが一般的です。
必要に応じて、
using ll = long long;
のように型エイリアスを作ったり、
#define int long long
のようにマクロを定義したりして、コーディングしやすいようにすることが多いと思います。(業務プログラミングでは厳禁ですが…)
このようにマクロを定義すれば、int型とlong long型の区別がいらないため、オーバーフローの心配はありません。が、bit演算(特に左シフト)をするときには、オーバーフローするかもしれないことを意識することがあります。
例えば
1 << K
のように書いたとき、1がint型として処理されるため、Kが31以上だと、オーバーフローしてしまいます。
解決策は、
1LL << K
と書くことです。
このようにすれば、1LLがlong long型として処理されるため、(Kが63未満ならば)オーバーフローは起きません。でも、何にせよ忘れやすい…
先述した、入水したABC356でのD問題でも、これができていなかったため自力ACできずに、AIに頼ってしまったという背景があります。さらに過去にも、3回ほど、これが原因となってコンテスト中に解けなかった問題があります…
bit全探索やbitDPでは、2^20ほどまでしか探索しないので、1 << Kと書いてもこういうバグは起きません。そのため、必要なときに忘れてしまいがちです。
私のトラウマなので、自分への戒めとして、そして同じ思いをする競プロerがいなくなることを願って、書かせていただきました。
勝手にライバル認定する
私が緑Coderのころから実践していることです。ちょっと嫌に思う人もいると思います…(小声)
Xには、競プロerの方々がたくさんいます。コンテスト後に解法をポストしたり、わからない問題を教え合ったりすることもあります。その中で、特に仲の良いフォロワーさんを選び、勝手にライバル認定するというのをやっています…(笑)
具体的には、Ratingの伸び方が自分と似ていたり、自分より100ほどRatingが上の人を2〜3人選びます。その人たちのAtCoderアカウントをお気に入り登録して、順位表に加えています。こうすることで、「この人たちに勝つ！」と闘志を燃やすことができます。また、その人たちが解いた問題を自分も解いたり、その人たちが実践している精進内容を取り入れたりすることで、嫌でもRatingが上がります。
Q: 自分から「ライバル認定してもいい？」って声をかけにいくことはしないの？
A: なんとなくおこがましい気がして、そんなことできない…
AJLへの参加(中高生限定)
青Coderってどれくらいすごいの？でも少し言及しましたが、AtCoder Jounior Leagueというものがあります。中高生が参加することができ、AtCoderのコンテストに参加してスコアを得ることができます。そのスコアで、学年別個人と学校別で順位がつき、アルゴリズム部門で20位以内に入ると賞状ももらえます。
これに参加しましょう。競プロに取り組む理由付けになります。先ほど話した「勝手にライバル認定する」のと同じように、コンテストに参加するモチベーションを上げてくれます。さらに、参加者は同年代という属性を持っているため、よりやる気が出ること間違いなしです！
ちなみに、私はAJL2024Summerのアルゴリズム部門個人ランキングの中3で、12位を獲得することができました！
頑張ってきた甲斐があったと思います！
これからの競プロ人生
入青して一区切りつきましたが、これからもコンテストに参加し続けて、入黄を目指す所存です。
ARC精進
黄Coderに近づいていくにつれて、だんだんARCが主戦場となってきます。黄Coder以上は、ABCでRatingが変化しません。そのため、ARC精進をしなければ、たとえ入黄できたとしても、ARCで勝てないと停滞してしまうことが目に見えています。そうならないために、今のうちから戦える力を身につけておきたいです。
新たなアルゴリズムの勉強
桁DPは、一刻も早く学ばなければいけないと思っています(diff帯が水上位のため)。それ以外のアルゴリズムについては、まずは中国剰余定理などから手をつけたいです。
JOI本戦突破
私は去年の9月末に競プロを始めましたが、そのころはJOIの存在を知らなかったため、参加しませんでした。そのため、今年が初参加となります。緑〜水Coderくらいの実力を持っていれば、2次予選を突破できるという話なので、さらに1つ上の本戦を突破することを目標にしています。(春合宿行きた〜い！)
Writer & Testerへの興味
やりたいです。Xを見ていると緑〜水Coderのあたりから、yukicoderでの作問をしている人が多少いるような気がします。入黄に必須ではありませんが、普段とは違う視点でコンテストを見てみたいという気持ちは、前々からあります。
目指せ暖色Coder!
おわりに
青Coderというのは、誰もが必ずしもなれるわけではないと思います。私も決して楽々なったわけではありません。日々の精進の積み重ねがあってこそ、結果が出たのだと考えています。努力は報われないこともありますが、何事も努力無しに達成できるわけでもありません。
一緒に精進頑張りましょう！
宣伝
Xのアカウントを載せておきます。競プロerであれば、Ratingがいくつであれフォロバします。もちろん非競プロerでも大歓迎です！
良かったらこの記事へのいいねをお願いします！
最後まで読んでくださり、ありがとうございました！