Go to Qiita Advent Calendar 2024 Top
LoginSignup
18
14

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@m1une

AtCoderで入水しました！

Last updated at Posted at 2024-07-28

はじめに

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

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

プロフィール

  • 大学学部2回生
  • 京都大学工学部情報学科計算機科学コース所属

競プロを始める前から持っていた経験等

  • Scratchでのゲームプログラミング
  • 授業でのPythonの経験
  • C言語のごくごく基本的な知識（ポインタは理解してたくらい、mallocとかは知らない）
  • C++の経験は無し

使用環境

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

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

やったこと(精進編)

APG4b を埋める

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

C++で競プロをまともにやるには、APG4bの1~3章の内容は全て理解する必要があると思います。4章の内容は必ずしもすべて理解する必要はないですが、イテレータは理解しておいたほうがいいでしょう。

AtCoder Library Practice Contest を埋める

2024年4月ごろにAPG4bを全て終わらせたあとすぐ、AtCoder Library Practice Contestを埋め始めました。

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

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

AtCoder Libraryの中で初心者がまず勉強するべきものは、Disjoint Set UnionとSegment TreeとLazy Segment Tree（Lazy Segment Treeの練習問題はもう一問あります）でしょう。

ACLのドキュメントはブックマーク登録などしていつでも参照できるようにすると良いでしょう。

AtCoder Problems で精進

Screenshot 2024-07-27 at 19.00.54.png

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

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

Screenshot 2024-07-27 at 20.06.53.png

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

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

Screenshot 2024-07-27 at 20.21.15.png
↑ Atcoder Type Checkerでチェックした結果。私はかなり、多く解くタイプであることがわかる。

EDPCを埋める

EDPCは、競プロで必須となる考え方であるDPを練習するのにおそらく最適なコンテストページです。こちらはdrkenさんやkyopro_friendsさんが解説を書いてくださっているので、とても勉強になります。

後半の問題はかなり難しい問題も多いですが、（私もVまでしか終わっていません）前半は初心者にもとてもためになる問題ばかりなのでぜひやりましょう。

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

C++をより深く勉強する

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

そのようなコードを理解するために、Theoride Technologyが公開しているこれらの講座がわかりやすいです。私もまだ全ては読めていませんが、気になるところだけ読むのでもとてもためになると思います。

やったこと（その他）

GitHub Educationを申請する

もしあなたが学生ならば、GitHub Educationは必ず申請するべきです。

GitHub Educationを申請することで、GitHub Student Developer Packが使えるようになるのがとてもデカいです。

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

AtCoder用の環境構築をする

online judge toolsやatcoder-cliを導入することで、問題とテストケースを自動で読み込み、ローカルでテストを行なったり、ローカルから提出を行なったりすることができます。

Windowsならこの記事、Macならこの記事がとても参考になります。

テンプレート・ライブラリを整備する

私はmaspyさんの提出コードをベースにして、いろいろな改造をしたテンプレートを用いています。FAST I/Oは私がまだあまり理解できていないので導入していません。
このテンプレートはこの記事の最後の付録に貼付してあります。

また、ライブラリはいまなお整備中ですが、今のところ整備されているのは

  • 2次元累積和
  • クラスカル法
  • ダイクストラ法
  • ワーシャルフロイド法
  • エラトステネスの篩
  • 素因数分解
  • 二項係数
  • 行列
  • 抽象ダブリング
  • 座標圧縮
  • ランレングス圧縮
  • ローリングハッシュ
  • 全方位木DP
  • 最近共通祖先
  • 木の直径
  • 木の重心

などです。

コードをGitHubで管理する

ひとつのパソコンしか使わないならこれは不要だと思います。

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

GitHub Desktopを導入すれば、コマンドラインからGitの操作をする必要がなくなり、より簡単にGitを扱うことができます。

おわりに

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

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

付録

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;
}
18
14
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
18
14

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?