AtCoderで入水しました！

## はじめに
<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">入水ｷﾀ━━━━(ﾟ∀ﾟ)━━━━!!<br>m1uneさんのAtCoder Beginner Contest 363での成績：1273位<br>パフォーマンス：1480相当<br>レーティング：1182→1218 (+36) :)<br>Highestを更新し、4 級になりました！<a href="https://twitter.com/hashtag/AtCoder?src=hash&amp;ref_src=twsrc%5Etfw">#AtCoder</a> <a href="https://twitter.com/hashtag/ABC363?src=hash&amp;ref_src=twsrc%5Etfw">#ABC363</a> <a href="https://t.co/QnYWC5qaHV">https://t.co/QnYWC5qaHV</a> <a href="https://t.co/rcUBdhDLtG">pic.twitter.com/rcUBdhDLtG</a></p>&mdash; みうね@競プロ (@m1une_kyopro) <a href="https://twitter.com/m1une_kyopro/status/1814671601172160884?ref_src=twsrc%5Etfw">July 20, 2024</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script> 

はじめまして、みうね（m1une）です！

ABC363で水色になったので、色変記事の文化にのっとって入水記事を書きます。この手の記事を書くのは初めてで色々手さぐり状態ですが、水色を目指す人の参考になれば嬉しいです。

### プロフィール
* 大学学部2回生
* 京都大学工学部情報学科計算機科学コース所属

### 競プロを始める前から持っていた経験等
* Scratchでのゲームプログラミング
* 授業でのPythonの経験
* C言語のごくごく基本的な知識（ポインタは理解してたくらい、mallocとかは知らない）
* C++の経験は無し

### 使用環境
* WindowsとMacを併用、最近はMacがメイン
* C++23 (gcc14)
* VS Code (online-judge-tools、atcoder-cli、Github Copilot導入済み)

私が水色になるまでにやったことを、精進（勉強）とその他に分けて説明します。

## やったこと(精進編)
### APG4b を埋める
https://atcoder.jp/contests/APG4b

2023年の年末ごろから[APG4b](https://atcoder.jp/contests/APG4b)を埋め始めました。APG4bはとてもわかりやすいので、とりあえず競プロでC++を使いたいならばこれを埋めるのが一番いいと思います。

C++で競プロをまともにやるには、APG4bの1~3章の内容は全て理解する必要があると思います。4章の内容は必ずしもすべて理解する必要はないですが、[イテレータ](https://atcoder.jp/contests/APG4b/tasks/APG4b_ai "AI - 4.04.イテレータ")は理解しておいたほうがいいでしょう。

### AtCoder Library Practice Contest を埋める
https://atcoder.jp/contests/practice2

2024年4月ごろにAPG4bを全て終わらせたあとすぐ、[AtCoder Library Practice Contest](https://atcoder.jp/contests/practice2)を埋め始めました。

このコンテストはAtCoder Library (ACL)の使い方を学べるもので、けんちょん(drken)さんがわかりやすい解説をあげてくれているのでとても勉強になります。

AtCoder LibraryはAtCoderでは必ず使えたほうがいいものなので、手元環境でも実行できるようにしておきましょう。

AtCoder Libraryの中で初心者がまず勉強するべきものは、[Disjoint Set Union](https://atcoder.jp/contests/practice2/tasks/practice2_a "A - Disjoint Set Union")と[Segment Tree](https://atcoder.jp/contests/practice2/tasks/practice2_j "J - Segment Tree")と[Lazy Segment Tree](https://atcoder.jp/contests/practice2/tasks/practice2_k "K - Range Affine Range Sum")（Lazy Segment Treeの練習問題は[もう一問](https://atcoder.jp/contests/practice2/tasks/practice2_l "L - Lazy Segment Tree")あります）でしょう。

[ACLのドキュメント](https://github.com/atcoder/ac-library/tree/master/document_ja "ac-library/document_ja")はブックマーク登録などしていつでも参照できるようにすると良いでしょう。

### AtCoder Problems で精進
![Screenshot 2024-07-27 at 19.00.54.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3847101/fa64569c-8c91-cc34-f870-935aef1874c8.png)

AtCoder Library Practice Contestを埋め終わった後、[AtCoder Problems](https://kenkoooo.com/atcoder/#/table/)での精進を始めました。上のdifficulty piesから分かる通り精進の量自体はそこまで多くないですが、水色問題を比較的多く解いています。

基本的には、User -> Recommendation -> difficult の問題を順番に埋めていきました。

![Screenshot 2024-07-27 at 20.06.53.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3847101/26888d38-3056-ff33-ca84-dc73c800e888.png)

私は基本的に「5分考えてわからなかったら解説を見る」といったスタンスで取り組んでいます。それは、わからない問題はそもそも必要となる前提知識が抜け落ちていることが結構多く、長時間悩むよりは解説をみて知識を蓄える方がいいと思うからです。

その結果私は早解きが苦手なタイプになっていますが、私は早く解くよりはより難しい問題が解けることの方が成長するうえでは大事だと思っているので今のところはこれでいいです。（いずれは早解きもできるようになるべきですが）

![Screenshot 2024-07-27 at 20.21.15.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3847101/d168e00f-2a50-6b94-9ac2-56a2f2542212.png)
↑ [Atcoder Type Checker](https://atcoder-type-checker.herokuapp.com/)でチェックした結果。私はかなり、多く解くタイプであることがわかる。

### EDPCを埋める
https://atcoder.jp/contests/dp

[EDPC](https://atcoder.jp/contests/dp "Educational DP Contest")は、競プロで必須となる考え方であるDPを練習するのにおそらく最適なコンテストページです。こちらはdrkenさんやkyopro_friendsさんが解説を書いてくださっているので、とても勉強になります。

後半の問題はかなり難しい問題も多いですが、（私も[V](https://atcoder.jp/contests/dp/tasks/dp_v "V - Subtree")までしか終わっていません）前半は初心者にもとてもためになる問題ばかりなのでぜひやりましょう。

~~EDPCをVまで埋めたのにABC364-Eが解けませんでした~~

### C++をより深く勉強する
https://theolizer.com/cpp-school-root/cpp-school/

https://theolizer.com/cpp-school-root/cpp-school2/

先述のAPG4bをすべてこなせば、競プロをやる上では十分なC++力を獲得できます。しかし、左辺値・右辺値やムーブ、可変長引数テンプレートなどAPG4bでは紹介されていないが他人のコードではしばしば登場する概念がC++にはいくつかあります。

そのようなコードを理解するために、Theoride Technologyが公開している[これらの講座](https://theolizer.com/cpp-school-root/cpp-school/)がわかりやすいです。私もまだ全ては読めていませんが、気になるところだけ読むのでもとてもためになると思います。

## やったこと（その他）
### GitHub Educationを申請する
https://github.com/education

もしあなたが学生ならば、[GitHub Education](https://github.com/education)は必ず申請するべきです。

GitHub Educationを申請することで、[GitHub Student Developer Pack](https://education.github.com/pack/offers)が使えるようになるのがとてもデカいです。

GitHub Copilotが無料で使えるのはもちろん、JetBrainsの無料ライセンスなど、さまざまな特典があるのでこれを申し込まない手はないです。学生ならぜひ申し込みましょう。

### AtCoder用の環境構築をする
[online judge tools](https://github.com/online-judge-tools/oj)や[atcoder-cli](https://github.com/Tatamo/atcoder-cli)を導入することで、問題とテストケースを自動で読み込み、ローカルでテストを行なったり、ローカルから提出を行なったりすることができます。

Windowsなら[この記事](https://yuulis.hatenablog.com/entry/atcoder-cpp-env-build#WSL-%E7%92%B0%E5%A2%83%E4%B8%8A%E3%81%AB-Git-%E3%82%92%E5%B0%8E%E5%85%A5%E3%81%99%E3%82%8B)、Macなら[この記事](https://qiita.com/Adaachill/items/3d4ddad56c5c2cc372cd)がとても参考になります。

https://yuulis.hatenablog.com/entry/atcoder-cpp-env-build#WSL-%E7%92%B0%E5%A2%83%E4%B8%8A%E3%81%AB-Git-%E3%82%92%E5%B0%8E%E5%85%A5%E3%81%99%E3%82%8B

https://qiita.com/Adaachill/items/3d4ddad56c5c2cc372cd

### テンプレート・ライブラリを整備する
私は[maspyさんの提出コード](https://atcoder.jp/contests/abc361/submissions/55258707)をベースにして、いろいろな改造をしたテンプレートを用いています。FAST I/Oは私がまだあまり理解できていないので導入していません。
このテンプレートはこの記事の最後の付録に貼付してあります。

また、ライブラリはいまなお整備中ですが、今のところ整備されているのは
* 2次元累積和
* クラスカル法
* ダイクストラ法
* ワーシャルフロイド法
* エラトステネスの篩
* 素因数分解
* 二項係数
* 行列
* 抽象ダブリング
* 座標圧縮
* ランレングス圧縮
* ローリングハッシュ
* 全方位木DP
* 最近共通祖先
* 木の直径
* 木の重心

などです。

### コードをGitHubで管理する
ひとつのパソコンしか使わないならこれは不要だと思います。

プライベートリポジトリを作り、AtCoderに関連するコードをすべてそのリポジトリ内に置くことで、別のパソコンからでもアクセスすることができます。

[GitHub Desktop](https://github.com/apps/desktop)を導入すれば、コマンドラインからGitの操作をする必要がなくなり、より簡単にGitを扱うことができます。

## おわりに
私が入水するまでにやったことはこれくらいです。皆さんの参考になれば幸いです。

次は青目指して頑張るぞ〜

## 付録
```C++:my_template.cpp
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#else
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif

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

// #include <atcoder/all>
// using namespace atcoder;
// using mint = modint998244353;

using ll = long long;
using u32 = unsigned int;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
using f128 = __float128;

template <class T>
constexpr T infty = 0;
template <>
constexpr int infty<int> = 1'000'000'000;
template <>
constexpr ll infty<ll> = ll(infty<int>) * infty<int> * 2;
template <>
constexpr u32 infty<u32> = infty<int>;
template <>
constexpr u64 infty<u64> = infty<ll>;
template <>
constexpr i128 infty<i128> = i128(infty<ll>) * infty<ll>;
template <>
constexpr double infty<double> = infty<ll>;
template <>
constexpr long double infty<long double> = infty<ll>;

using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
template <class T>
using vc = vector<T>;
template <class T>
using vvc = vector<vc<T>>;
using vvi = vvc<int>;
using vvl = vvc<ll>;
template <class T>
using vvvc = vector<vvc<T>>;
template <class T>
using vvvvc = vector<vvvc<T>>;
template <class T>
using vvvvvc = vector<vvvvc<T>>;
template <class T>
using pq = std::priority_queue<T>;
template <class T>
using pqg = std::priority_queue<T, vector<T>, greater<T>>;

// template <typename K>
// using tree = __gnu_pbds::tree<K, __gnu_pbds::null_type, std::less<>,
//                               __gnu_pbds::rb_tree_tag,
//                               __gnu_pbds::tree_order_statistics_node_update>;

#define vv(type, name, h, ...) \
    vector<vector<type>> name(h, vector<type>(__VA_ARGS__))
#define vvv(type, name, h, w, ...)     \
    vector<vector<vector<type>>> name( \
        h, vector<vector<type>>(w, vector<type>(__VA_ARGS__)))
#define vvvv(type, name, a, b, c, ...)         \
    vector<vector<vector<vector<type>>>> name( \
        a, vector<vector<vector<type>>>(       \
               b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))

// https://trap.jp/post/1224/
#define FOR1(a) for (ll _ = 0; _ < (ll)a; ++_)
#define FOR2(i, a) for (ll i = 0; i < (ll)a; ++i)
#define FOR3(i, a, b) for (ll i = a; i < (ll)b; ++i)
#define FOR4(i, a, b, c) for (ll i = a; i < (ll)b; i += (c))
#define FOR1_R(a) for (ll i = (a) - 1; i >= 0; --i)
#define FOR2_R(i, a) for (ll i = (a) - 1; i >= 0; --i)
#define FOR3_R(i, a, b) for (ll i = (b) - 1; i >= (ll)a; --i)
#define overload4(a, b, c, d, e, ...) e
#define overload3(a, b, c, d, ...) d
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FOR_R(...) overload3(__VA_ARGS__, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__)

#define FOR_subset(t, s) \
    for (int t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s)))
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(u32 x) { return __builtin_popcount(x); }
int popcnt(ll x) { return __builtin_popcountll(x); }
int popcnt(u64 x) { return __builtin_popcountll(x); }
int popcnt_mod_2(int x) { return __builtin_parity(x); }
int popcnt_mod_2(u32 x) { return __builtin_parity(x); }
int popcnt_mod_2(ll x) { return __builtin_parityll(x); }
int popcnt_mod_2(u64 x) { return __builtin_parityll(x); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int topbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2)
int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }

template <typename T>
T floor(T a, T b) {
    return a / b - (a % b && (a ^ b) < 0);
}
template <typename T>
T ceil(T x, T y) {
    return floor(x + y - 1, y);
}
template <typename T>
T bmod(T x, T y) {
    return x - y * floor(x, y);
}
template <typename T>
pair<T, T> divmod(T x, T y) {
    T q = floor(x, y);
    return {q, x - q * y};
}

template <typename T, typename U>
T POW(U x_, int n) {
    T x = x_;
    T ret = 1;
    while (n > 0) {
        if (n & 1) ret *= x;
        x *= x;
        n >>= 1;
    }
    return ret;
}

template <typename T, typename U>
T SUM(const vector<U> &A) {
    T sm = 0;
    for (auto &&a : A) sm += a;
    return sm;
}

#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define LB(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define UB(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define UNIQUE(x) \
    sort(all(x)), x.erase(unique(all(x)), x.end()), x.shrink_to_fit()

template <class T, class S>
inline bool chmax(T &a, const S &b) {
    return (a < b ? a = b, 1 : 0);
}
template <class T, class S>
inline bool chmin(T &a, const S &b) {
    return (a > b ? a = b, 1 : 0);
}

// ? は -1
vc<int> s_to_vi(const string &S, char first_char) {
    vc<int> A(S.size());
    FOR(i, S.size()) { A[i] = (S[i] != '?' ? S[i] - first_char : -1); }
    return A;
}

template <typename T, typename U>
vector<T> cumsum(vector<U> &A, int off = 1) {
    int N = A.size();
    vector<T> B(N + 1);
    FOR(i, N) { B[i + 1] = B[i] + A[i]; }
    if (off == 0) B.erase(B.begin());
    return B;
}

// stable sort
template <typename T>
vector<int> argsort(const vector<T> &A) {
    vector<int> ids(A.size());
    iota(all(ids), 0);
    sort(all(ids),
         [&](int i, int j) { return (A[i] == A[j] ? i < j : A[i] < A[j]); });
    return ids;
}

// A[I[0]], A[I[1]], ...
template <typename T>
vc<T> rearrange(const vc<T> &A, const vc<int> &I) {
    vc<T> B(I.size());
    FOR(i, I.size()) B[i] = A[I[i]];
    return B;
}

void YESNO(bool b) { cout << (b ? "YES" : "NO") << endl; }
void YesNo(bool b) { cout << (b ? "Yes" : "No") << endl; }

#ifdef LOCAL
// https://zenn.dev/sassan/articles/19db660e4da0a4
#include "/Library/cpp-dump/cpp-dump.hpp"
#define dump(...) cpp_dump(__VA_ARGS__)
#else
#define dump(...)
#define CPP_DUMP_SET_OPTION(...)
#define CPP_DUMP_SET_OPTION_GLOBAL(...)
#define CPP_DUMP_DEFINE_EXPORT_OBJECT(...)
#define CPP_DUMP_DEFINE_EXPORT_ENUM(...)
#define CPP_DUMP_DEFINE_EXPORT_OBJECT_GENERIC(...)
#endif


//----------------------------------------------------------------

void solve() {
    int N;
    cin >> N;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(20);
    CPP_DUMP_SET_OPTION(max_line_width, 80);
    CPP_DUMP_SET_OPTION(log_label_func, cpp_dump::log_label::filename());
    CPP_DUMP_SET_OPTION(enable_asterisk, true);
    solve();
    return 0;
}
```