青色コーダー(AtCoder)になりました！！

　初めまして、趣味で競技プログラミングをやっているk1suxuと申します。言語は主にC++を使用しています。先日のAtCoder Beginner Contest 251にて、幸いにも初黄パフォを出すことができ、念願の入青を果たしました。自分の進捗を残すためにもブログに書き起こしてみます。

競技プログラミングを始めて約一年、初の黄パフォとともに念願の入青です！！
k1suxuさんの成績:140位
パフォーマンス:2335相当
レーティング:1505→1621 (+116) :)
Highestを更新し、2 級になりました！#AtCoder #ABC251 #パナソニックグループプログラミングコンテスト2022 https://t.co/g6q5FkQCFa pic.twitter.com/wpCq1NGIPZ

— k1suxu (@k1suxu) 2022年5月14日

目次

現在のAtCoderの進捗状況

最近は一気に青色を解き進めた後に少しずつ黄色を解いています。

青色になるまでに学んだこと

　この章では、私が青色になるまでに学んだ知識について列挙しています。一部抜けがあるかもしれませんがご了承ください。 また、色ごとの勉強方法やその色の時期に何を学んだかなどについては、次の章をご参照ください。

1.数学的な知識

青色になるまでに学んだ数学的な知識は以下の通りです。

高校数学

　競技プログラミングを始めたのが高校2年生の4月であって、今も高校生なので、特に追加で学んだことはないのですが、競技プログラミングで重要だと思う分野は以下です。

・ベクトル(平面、空間)

・初等幾何(三角関数、三平方の定理、多角形の面積など)

・初等関数(n次関数や三角関数、指数対数関数などといった関数の概形に関する知識)

・方程式(問題文に対して適切に未知数を定め、計算式にまとめる能力がしばしば求められます)

・不定方程式(不定方程式の考え方を用いて、二つの未知数に対して一つを全探索してもう一つを求めるというような考察が必要となることがあります)

・数え上げ(場合の数)(いわゆる写像12相などです)

・確率(条件付確率や包除原理など)

・期待値(特に期待値の線形性)　私の苦手分野です。

・数列(等差数列、等比数列、漸化式、特性方程式、一般項や総和、級数の公式など)

・複素数平面(図形問題を複素数平面上で解くとうまくいったりします)

その他

・行列の基礎的な知識(行列を用いて連立方程式の解を求める方法、行列式、転置、逆行列)

・群論における基礎、特に演算子の定義やモノイドなど

・オーダー表記(計算機科学？)による計算量、メモリ量の見積もり

・グラフ理論の基礎

・パスカルの三角形

・フェルマーの小定理(逆元の計算に必要です)

・拡張ユークリッドの互除法(不定方程式の解を一つ求めます)

2.アルゴリズム・データ構造

青色になるまでに学んだアルゴリズム・データ構造は以下の通りです。

DP

・配るDP, 貰うDP, 区間DP, bitDP, 期待値DP, 桁DP, 文字列DPなど

・LCS(Longest Common Subsequences)

・LIS(Longest Increasing Subsequences)

数学

・MOD上での各種計算、高速累乗(繰り返し二乗法)

・逆元の計算

・パスカルの三角形を用いたnCrの計算

・エラトステネスの篩

・Euler Phi

・転倒数

・スライド最小値・最大値

探索法

・順列全探索

・bit全探索

・二分探索

・三分探索

・半分全列挙

グラフ理論

〇最短経路探索

・BFS, DFS

・Dijkstra

・Warshall Floyd

・Bellman_Ford

〇BFS, DFSの応用知識

・Euler Tour

・01BFS

・BFS Tree, DFS Tree

・強連結成分分解 Strongly Connected Components(SCC)

・二部グラフ判定

・LowLink グラフ上の橋、関節点の検出

・木の直径

〇フロー

・最大流(最小カット)問題(Ford_Fulkerson法、Dinic法)　まだコンテストで使ったことはないです。

〇素集合データ構造

・Union Find

・Weighted Union Find 重み付きUnion Findのことです

〇木構造に関するクエリ

・LCA (Lowest Common Ancestor)

・Topological Sort (DAGの判定にも使えます)

・無向最小全域木(Kruskal法、Prim法)

〇区間に対するクエリを高速に答えるデータ構造など

・BIT(Binary Indexed Tree)

・Fenwick Tree

・セグメント木、遅延セグメント木

・Mo's Algorithm

文字列

・Z_Algorithm

・Rolling_Hash

・ランレングス圧縮

　これらのアルゴリズムは引数を何らかの配列にすることで文字列以外にも適用できます。 例えばランレングス圧縮の場合、c++では以下のように実装できます。

▶クリックで展開

template<typename T>
vector<pair<T, int>> run_length_encoding(vector<T> s) {
    T need = s[0];
    int cnt = 0;
    vector<pair<T, int>> ret;
    for(T c : s) {
        if(c == need) {
            cnt++;
        }else {
            ret.emplace_back(need, cnt);
            need = c;
            cnt = 1;
        }
    }
    if(cnt != 0) ret.emplace_back(need, cnt);
    return ret;
}

その他

・累積和

・imos法

・座標圧縮

・マンハッタン距離の性質(45度回転)

・しゃくとり法

・調和級数を用いた計算量解析

2.ライブラリの整備

テンプレートの作製

　コンテストに出るにあたりテンプレートファイルを作成しました。現在使用しているものは以下です。特にfor文をマクロで短縮するのはおすすめです。

▶クリックで展開

#include <bits/stdc++.h>
using namespace std;

#define rep(i,n) for(int i = 0; i < (int)n; i++)
#define FOR(n) for(int i = 0; i < (int)n; i++)
#define repi(i,a,b) for(int i = (int)a; i < (int)b; i++)
#define pb push_back
#define m0(x) memset(x,0,sizeof(x))
#define fill(x,y) memset(x,y,sizeof(x))
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
//#define mp make_pair
#define vi vector<int>
#define vvi vector<vi>
#define vll vector<ll>
#define vvll vector<vll>
#define vs vector<string>
#define vvs vector<vs>
#define vc vector<char>
#define vvc vector<vc>
#define pii pair<int,int>
#define pllll pair<ll,ll>
#define vpii vector<pair<int,int>>
#define vpllll vector<pair<ll,ll>>
#define vpis vector<pair<int,string>>
#define vplls vector<pair<ll, string>>
#define vpsi vector<pair<string, int>>
#define vpsll vector<pair<string, ll>>

template<typename T>
void chmax(T &a, const T &b) {a = (a > b? a : b);}
template<typename T>
void chmin(T &a, const T &b) {a = (a < b? a : b);}

using ll = long long;
using ld = long double;
using ull = unsigned long long;

const ll INF = numeric_limits<long long>::max() / 2;
const ld pi = 3.1415926535897932384626433832795028;
const ll mod = 1e9 + 7;
int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1};
int dy[] = {0, -1, 0, 1, -1, 1, -1, 1};

void solve() {

}

signed main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    solve();
    return 0;
}

現在使用しているライブラリ

　前述したアルゴリズムたちにあるものはほぼすべてライブラリ化しています。その他持っているライブラリは以下です。

・構造体：有理数(分数)
・構造体：行列
・素因数分解
・商(整数除算)の列挙
・幾何ライブラリ
->多角形の面積や内外判定など多数

色ごとの勉強

　この章では、私が青色になるまでの色の遷移とその時々にしていた勉強について記述しています。具体的に何を学んだかについては前章をご参照ください。

灰～茶(2021年4月24日～2021年6月13日)

　私がプログラミングそのものの勉強を始めたのは2021年の3月辺りで、その約1か月後に友人に教えてもらったことをきっかけにAtCoderに登録し、競技プログラミングを始めました。当時私はPythonで競技プログラミングしており、多重配列の入力の受け取りや初期化に苦労してた記憶があります。初参加のABC199では2完にとどまりました(当時の私は計算量という概念を知らず、C問題で一生TLEしていました...)。この頃は特に競技プログラミング向けの勉強はしておらず、ひたすらプログラミングの基礎に触れるという感じでした。計算量について少しだけ学びましたが、「ソートって時間かかるんだ。へ～。」程度にしか思っていませんでした。もともとタイピングはそれなりに速かったので、簡単な問題を早く解くことのみに専念していました。

茶～緑(2021年6月13日～2021年9月11日)

　茶色になってからも数か月は、灰色を虚無埋めしていました。7月ごろになり、学校が夏休みに入ったころ、E869120さんの「レッドコーダーが教える、競プロ・AtCoder上達のガイドライン」という記事を見たことをきっかけにアルゴリズムの面白さに引き込まれました(本当におすすめでとても為になる記事です。ぜひ検索してみてください)。そこからはBFSやDFSなどの基礎的なアルゴリズムを学びつつ、AOJ(AiZU ONLINE JUDGE)などを利用してライブラリの整備などをしていました。そうしている間に緑色になりました。

　ここまでで最短経路アルゴリズム、nCr, nPr, nHrなどのライブラリが整いました。

緑~水(2021年9月11日～2022年1月30日)

　ちょうど緑色になったころ、日本情報オリンピック(JOI)の存在を知り応募しました。一次予選突破が確定したあたりからはJOIの過去問をといていました。私にとっては最初で最後のJOIだったので、この頃はJOI二次予選突破を第一目標に精進していました。今年は例年よりも定員が多かったため、無事に二次予選を突破し、本選に進むことができました。

　JOIが一段落ついたので高校二年生の冬休みはAtCoderに傾倒することにしました。むやみやたらに簡単な問題を解いても成長しないだろうということは経験でわかっていたので、自分の得意不得意やコンテストでの動きについて分析してみることにしました。分析してみた結果当時の私はDPに弱く、早解きはできるが、difficulty*1が緑色以上の問題に対してACできていないということがわかりました。また、グラフの問題に強いという傾向も見て取れました。

　分析の結果を踏まえてDPを扱う問題を解こうと思いEDPCを少し解き進めました。これにより、DPの基礎を学ぶことができました。また、緑色以上の問題を安定して解けるようになることを目標にABC中の緑色の問題を埋めてみることにしました。緑色が安定してきたら、次に水色へと移りました。この頃から、ScrapBoxにて解いた問題の感想や考察の手順、振り返りを始めました。これを始めてから実力が一気に伸びた気がします(知識と解法の点と点が線で結ばれるような感覚です)。水色を60問ほど埋めたあたりでついに水色になれました！！

　この時点で、現在そろっているライブラリの7割ほどは完成しています。具体的には(フローライブラリ, fenwick_tree, rolling_hash, 幾何ライブラリの一部, mo's algorithm, 行列ライブラリ + α以外です)。

水～青(2022年1月30日～2022年5月14日)

　水色になった後はひたすら青問題を埋めました。知らないアルゴリズムが出てくるということはあまりなく、典型考察力*2が鍛えられたという感想です。そのままScrap Boxで問題の感想を書くことを続けつつ精進していると順調にレートが伸びていき2022年5月14日についに青色になることができました。

問題を解く度の振り返りの勧め

　前述した通り私は、競技プログラミングの問題を解いたら、常にScrap Boxを用いてその問題についてメモを行うようにしています。具体的には以下のようなものです(ABC107_D_Median_of_Medians)。

＊注意＊ABC107 D Median of Mediansのネタバレを含みます。見たくない方は飛ばしてください！！

▶ABC107 D 振り返り(クリックで開きます)

・abc107 D Median of Medians
　見た目的に「代表値の代表値」なので決め打ち二分探索だろう。medianが以上となるペアが個(すなわちmedian of mediansが以上となる)かという判定問題に帰着する。
　medianに関する判定問題なのでいつも通り数列を用意して にする。
あとは累積和をとって式を整理してみる。ここで数列をの累積和として、区間上のについて1が以上があればいいのでこれはなる半開区間について を満たす様なi, jの組の個数を求めればよい。


が判定条件となりとすればこれが解ける。ここでとなる可能性があることを考慮してを座標圧縮して0以上の整数に統一するとこれをindexとしたfenwick_treeで解けるので判定のオーダーは
よってこの問題が で解ける

　これを行うことにより、自分の思考の過程をアウトプットすることになるので、考察がその場しのぎではなく、ほかの問題への応用も可能な状態になります。また、自分の持っている知識たちのかけ合わせが文字になって表れるので、複雑な典型考察を言語化、簡略化して覚えることができます。

これからの予定

　とりあえずは、学業をおろそかにしない程度に精進していこうと思います。最近はABCの黄色diffの問題を解き進めていますがやっぱり難しいですね、また色変したら記事にしようかと思います。ここまで読んでいただきありがとうございました。またここに色変記事を投稿できるよう頑張ります！！

*1:AtCoder Problemsさんが算出提供してくださっている、AtCoder内の各問題の難易度をAtCoder Ratingで示したようなものです。

*2:特に、座標圧縮してfenwick_treeのような、よく使うけど知らないと難しい。というような考察がパッとできるようになりました