【競プロ】AtCoder早解きテクニック10選 (灰 ~ 緑コーダー向け)

はじめに

AtCoderでは問題を早く解くことによるパフォーマンスの変化が比較的大きいです．
例えば，これは執筆時 (2020/2/24) 直近三回のABC600 (A, B, Cの３問正解) 点のパフォーマンス表です．

	最大パフォ	最低パフォ	差
ABC156	998(緑)	117(灰)	881
ABC155	1431(水)	308(灰)	1123
ABC154	571(茶)	92(灰)	479

少し比較するコンテストが悪いような感じはしますが，同じ600点でもパフォーマンスに大きな差があることがわかります．
本記事ではいかにして問題を早く解くのか，テクニック （アルゴリズム） を10個ほど紹介したいと思います．

スニペット(ライブラリ)作成テクニック

多くのテキストエディタ(VScode, Atom, Emacsなど)には「スニペット」という機能があります．
この機能を使うと，あらかじめ書いておいたコードを，画面に瞬時に表示させることができます．

例えばVSCodeの場合はこちらのサイトを参考にすると登録することができます．
他のエディタを使用されている方は「(ここにエディタ名)　スニペット」とかで検索🔍すると簡単にヒットします！

以降，スニペットに登録しておくと便利なアルゴリズムを紹介します．
(注意: 紹介しているAtCoderの問題はちょっと難しいかもしれません．これは検索するのが面倒だったからです．随時募集します．)

1. 最大公約数

まずは最大公約数です．最大公約数はユークリッドの互除法を用いて実装できます．

int gcd(int a, int b) {
    return b ? gcd(b, a%b) : a;
}

最大公約数や，以降に出てくる最小公倍数はint型では収まらない数を使用することも多いので，int型の部分はlong long int型にしても良いでしょう．
また，n個の最大公約数を求めるシーンもよくあります．その時は以下のように，それぞれの最大公約数を求めてあげれば大丈夫です．

int ngcd(vector<int> a){
    int res;
    res = a[0];
    for(int i = 1; i < a.size() && res != 1; i++) {
        res = gcd(a[i], res);
    }
    return res;
}

以下のような問題で使用できます．
ABC109-C Skip
ABC125-C GCD on Blackboard

2. 最小公倍数

最大公約数と同じく，最小公倍数もよく出てきます．
最小公倍数は最大公約数から求められるので (参考)，最大公約数も一緒に呼び出しましょう

int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

int nlcm(vector<int> numbers) {
    int res;
    res = numbers[0];
    for (int i = 1; i < numbers.size(); i++) {
        res = lcm(res, numbers[i]);
    }
    return res;
}

以下のような問題で使用できます．
ABC148-C Snack
ABC70-C Multiple Clocks

3. 素数判定

素数かどうか判定する問題も多く存在します．
素数判定はちょっと工夫すると$O(\sqrt{N})$でできます．
($N$が素数の時，$1$と$N$以外の約数がないので，判定したいときは約数の有無を確かめる．ある約数iがあったとき，$N/i$もNの約数となる．ここで，$i=N/i$となる$i$は$\sqrt{N}$なので，$i$の候補は$1$~$\sqrt{N}$となる)

bool isPrime(int x){
    int i;
    if(x < 2)return 0;
    else if(x == 2) return 1;
    if(x%2 == 0) return 0;
    for(i = 3; i*i <= x; i += 2) if(x%i == 0) return 0;
    return 1;
}

以下のような問題で使用できます．
ABC149-C Next Prime
ARC44-A 素数判定

4. 桁和

各桁の和は問題の途中に出てくることが多いので，これは高速に表示できると楽だと思います．
「res += n%10;」を「res++;」に変えると桁数を求める関数になります．

int digsum(int n) {
    int res = 0;
    while(n > 0) {
        res += n%10;
        n /= 10;
    }
    return res;
}

以下のような問題で使用できます．
ABC136-B Uneven Numbers
ABC114-B 754

5. 約数全列挙

ABCでは約数を全列挙できると答えが見える問題多いですよね（体感）．

vector<int> enum_div(int n){
    vector<int> ret;
    for(int i = 1 ; i*i <= n ; ++i){
        if(n%i == 0){
            ret.push_back(i);
            if(i != 1 && i*i != n){
                ret.push_back(n/i);
            }
        }
    }
    return ret;
}

以下のような問題で使用できます．
ABC106-B 105
ABC122-D Partition

6. 累乗 (二分累乗 or 繰りかえし二乗法)

ABC-D,Eで組み合わせ(数え上げ)の問題が出た時に使用する頻度が高いです．

// xのn乗%modを計算
long long int mod_pow(long long int x, long long int n, long long int mod){
    long long int res = 1;
    while(n > 0){
        if(n & 1) res = res*x%mod;
        x = x*x%mod;
        n >>= 1;
    }
    return res;
}

以下のような問題で使用できます．
ABC55-B Training Camp
ABC156-D Bouquet

7. 文字列中に存在する特定の文字の個数カウント

これは覚えれば良いんですが，私はcbegin()という呪文が覚えられないんですね．
そこでスニペットの出番です！！名前を変えて関数にして登録しちゃいましょう！！
例えば，stringcount("xoxoooxoxx", 'o')とすると"xoxoooxoxx"にある'o'の数，つまり5を返します．

int stringcount(string s, char c) {
    return count(s.cbegin(), s.cend(), c);
}

以下のような問題で使用できます．
Tenka1-A Accepted...?

8. 幅優先探索

幅優先探索は茶色->緑の時にほぼ必須なアルゴリズムで，詳しくはdrkenさんのこのサイトなどを参考にしていただければと思います．
ですが，私は幾度か幅優先探索をしてて思いました．

「なんか毎回ほぼおんなじように書いてない...?」

そう！！型があってその通りにやって，ちょっと変えるだけで良いんですよ！！
だから型だけスニペットに登録しておきます．

コードは長いので隠しました．

幅優先探索のソースコード

// 各座標に格納したい情報を構造体にする
// 今回はX座標,Y座標,深さ(距離)を記述している
struct Corr {
    int x;
    int y;
    int depth;
};
queue<Corr> q;
int bfs(vector<vector<int>> grid) {
    // 既に探索の場所を1，探索していなかったら0を格納する配列
    vector<vector<int>> ispassed(grid.size(), vector<int>(grid[0].size(), false));
    // このような記述をしておくと，この後のfor文が綺麗にかける
    int dx[8] = {1, 0, -1, 0};
    int dy[8] = {0, 1, 0, -1};
    while(!q.empty()) {
        Corr now = q.front();q.pop();
        /*
            今いる座標は(x,y)=(now.x, now.y)で，深さ(距離)はnow.depthである
            ここで，今いる座標がゴール(探索対象)なのか判定する
        */
        for(int i = 0; i < 4; i++) {
            int nextx = now.x + dx[i];
            int nexty = now.y + dy[i];

            // 次に探索する場所のX座標がはみ出した時
            if(nextx >= grid[0].size()) continue;
            if(nextx < 0) continue;

            // 次に探索する場所のY座標がはみ出した時
            if(nexty >= grid.size()) continue;
            if(nexty < 0) continue;

            // 次に探索する場所が既に探索済みの場合
            if(ispassed[nexty][nextx]) continue;

            ispassed[nexty][nextx] = true;
            Corr next = {nextx, nexty, now.depth+1};
            q.push(next);
        }
    }
}

以下のような問題で使用できます．
ABC7-C 幅優先探索

その他のテクニック

9. テンプレート

提出用ファイルをあらかじめ決めておいて，そのコードに「int main(void)」など書いておくと手間が省けます(?)
私のテンプレートはこれですが，そんなに使わないものが多いので，良い感じにしたバージョンも用意しました
includeの箇所に関して，普段「<bits/stdc++.h>」を使用している場合はそちらに書き換えてください(私の環境では使えないので)．

私のテンプレート

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cassert>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <unordered_set>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define irep(it, stl) for(auto it = stl.begin(); it != stl.end(); it++)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout << (ans) << '\n'
#define mp(p,q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
#define itn int;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
template <class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;} return 0;}
template <class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;} return 0;}
struct io{io(){ios::sync_with_stdio(false);cin.tie(0);}};
const int INF = INT_MAX;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;
const double EPS = 1e-9;

int main(void) {


}

良い感じに削ったテンプレート

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
using namespace std;
typedef long long int ll;
typedef vector<int> vi;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define Sort(a) sort(a.begin(), a.end())
const int INF = 1<<30;
const ll MOD = 1000000007;

int main(void) {

}

10. エイリアス

Windowsの方はこのサイトを参考にしてください><
以下，mac,linux用です．
macやlinuxにはシェルってのがありますね．macの場合ターミナル，Ubuntuの場合端末ってのがあります．
VSCodeにも標準搭載されていて，こんな感じのやつです．

このシェルにうまく設定すると，コンパイルと実行をコマンド一つにできます．
macではデフォルトでzsh(Catalina以前はbash)という種類のシェルが使われていて，以下のように入力すると開けます．

.zshrc

open ~/.zshrc

その他，bashを使われている方はこちらで開けます．

.bashrc

open ~/.bashrc

ここでは，普段使っているコンパイルコマンドを「g++ template.cpp」で，実行コマンドを「./a.out」とします．
（もし違う場合はこの後の文字列を変えればうまく動くとおもいます）
この二つのコマンドをまとめて「atcoder」というコマンドにします．

.zshrc

alias atcoder='g++ template.cpp ; ./a.out'

.zshrc

alias 変えたいコマンド名='元のコマンド名'

にしてあげれば大丈夫です．ただし，二つのコマンドをまとめたい場合は間に「;」を入れてください．

私の設定はこれです．

.zshrc

alias gpp='g++ -std=c++1z -fsanitize=address -D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUG_PEDANTIC -o a.out template.cpp ; ./a.out'

[追記(2020.9.24)]
AtCoder STLをコンパイルできるよう，コンパイルコマンドをちょっと変えました．

.zshrc

alias gpp='g++ -std=c++1z -fsanitize=address -D_GLIBCXX_DEBUG -fsanitize=undefined -D_GLIBCXX_DEBUG_PEDANTIC -o a.out -I . template.cpp ; ./a.out'

これで，多少は時短になったと思います．
また，同じようなことをGNUmakefileというものを作ることでも実現できます．
同じフォルダにGNUmakefileという名前で以下のようなファイルを作ってください．

GNUmakefile

atcoder: template.cpp
    g++ template.cpp ; ./a.out

すると 「make」または「make atcoder」で同じようなことができます．

番外編 (緑/水コーダー向け)

セグメント木 (Segment Tree)

ABC-Cで区間和を求めよ，的な問題はたくさん存在します．
それらは尺取法や累積和が想定解法ですが，セグメント木を使うと入力する文字数が少なく済むことがあります．
以下のセグメント木クラスはコンストラクタに配列を渡すと，

• query(l,r)で区間[l,r)の和を計算
• update(k,x)でk番目の値(0-indexed)をxに変更 ということをしてくれます．

セグメント木 (Segment Tree)のソースコード

class Monoid {
public:
    // 単位元
    int unit;

    Monoid() {
        // 単位元
        unit = 0;
    }

    // 演算関数
    int calc(int a, int b) {
        return a + b; 
    }
};

class SegmentTree {
public:
    // セグメント木の葉の要素数
    int n;

    // セグメント木
    vector<int> tree;

    // モノイド
    Monoid mono;

    SegmentTree(vector<int> &v) {
        n = 1 << (int)ceil(log2(v.size()));
        tree = vector<int>(n << 1);
        for(int i = 0; i < v.size(); i++) {
            update(i, v[i]);
        }
        for(int i = v.size(); i < n; i++) {
            update(i, mono.unit);
        }
    }

    // k番目の値(0-indexed)をxに変更
    void update(int k, int x) {
        k += n;
        tree[k] = x;
        for(k = k >> 1; k > 0; k >>= 1){
            tree[k] = mono.calc(tree[k << 1 | 0], tree[k << 1 | 1]);
        }
    }

    // [l, r)の最小値(0-indexed)を求める．
    int query(int l, int r) {
        int res = mono.unit;
        l += n;
        r += n;
        while(l < r) {
            if(l & 1) {
                res = mono.calc(res, tree[l++]);
            }
            if(r & 1) {
                res = mono.calc(res, tree[--r]);
            }
            l >>= 1;
            r >>= 1;
        }
        return res;
    }
    int operator[](int k) {
        // st[i]で添字iの要素の値を返す
        if(k - n >= 0 || k < 0) {
            return -INF;
        }
        return tree[tree.size()-n+k];
    }

    void show() {
        int ret = 2;
        for(int i = 1; i < 2*n; i++) {
            cout << tree[i] << " ";
            if(i == ret - 1) {
                cout << endl;
                ret <<= 1;
            }
        }
        cout << endl;
    }
};

例えば，以下のコード(別途セグメント木も書いてください)で配列に要素を格納し，区間の和を$O(\log{N})$で．計算できます．(セグ木の構築に$O(N)$)

int main(void) {
    int n;
    cin >> n;
    vector<int> arr(n);
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    SegmentTree st(arr);
    int sum = st.query(3, 5); // 例として，区間[3,5)の和
    cout << sum << endl;
}

以下のような問題で使用できます．
ABC154-D Dice in Line
ABC122-C GeT AC
ABC125-C GCD on Blackboard

おわりに

時短テクといえばタイピングの速度が，と思いがちですが，意外と他のことの方が時短になったりします．
是非上記のライブラリをスニペットに貼ったりして，早解きライフを楽しんでみてください！