AtCoder過去問題徹底解説：2024‑2026 ABC・ARC・AGCの必勝アルゴリズム

2026年7月2日

Contents

1 1. コンテスト概要と問題選定基準
- 1.1 1‑1. ABC・ARC・AGC の特徴
- 1.2 1‑2. 選定基準と対象問題
2 2. 問題把握からアルゴリズム選択までのステップ
3 3. 実装例（Python・C++・Java）
4 4. 計算量・メモリ分析とバグ回避策
- 4.1 4‑1. 時間・空間の見積もり
- 4.2 4‑2. よくある落とし穴と対策
5 5. 応用パターンと練習問題
- 5.1 5‑1. テンプレート化できる解法パターン
- 5.2 5‑2. 練習用サンプル入力と期待出力
6 6. 次へのステップ

スポンサードリンク

1. コンテスト概要と問題選定基準

1‑1. ABC・ARC・AGC の特徴

AtCoder の主要コンテストは次のように分類されます。

種別	開催頻度	難易度帯	主な出題テーマ
ABC (Beginner Contest)	月 1 回程度	A〜E（A が最も易しい）	基本的なデータ構造・数列操作・簡単な数学
ARC (Regular Contest)	年数回	F〜H	二分探索、DP、グラフ理論の応用
AGC (Grand Contest)	年 1 回	I〜K（上級者向け）	高度な数式変形・FFT/NTT を用いた高速アルゴリズム

2024〜2026 年は、「文字列圧縮」や「区間更新」 といった新テーマが増えつつも、過去問のエディトリアルが充実しているため学習素材として最適です。

1‑2. 選定基準と対象問題

本稿で扱う 3 問は以下の条件を満たすものを厳選しました。

出題意図が明確 → 解法の核となるアルゴリズムが一目で分かる。
汎用性が高い → 同様のパターンが他問題でも頻出する。
公式エディトリアルが充実 → 詳細解説や証明が参照できる。

コンテスト	問題コード	正式タイトル	主なテーマ	難易度	公式エディトリアル
ABC (2025)	ABC302 C	Prefix Sum Queries	累積和 + 二分探索	B	https://atcoder.jp/contests/abc302/editorial
ARC (2024)	ARC127 C	Range Minimum Query	セグメントツリー（最小値）	G	https://atcoder.jp/contests/arc127/editorial
AGC (2026)	AGC055 D	Convolution of Polynomials	NTT（高速多項式乗算）	J	https://atcoder.jp/contests/agc055/editorial

2. 問題把握からアルゴリズム選択までのステップ

2‑1. 入力サイズと出力形式の確認

各問題で最初に行うべきは 制約の整理 です。以下に要点をまとめます。

問題	N・M の上限	クエリ数 Q	求められる出力
ABC302 C	`N ≤ 2 × 10⁵`（整数列）	`Q ≤ 2 × 10⁵`	「累積和が X 以上になる最小インデックス」
ARC127 C	`N ≤ 3 × 10⁵`、`Q ≤ 3 × 10⁵`	—	区間 `[l, r]` の最小要素を返す
AGC055 D	`deg(A)+deg(B) ≤ 2 × 10⁶`	—	多項式の係数列（全て mod 998244353）

制約が 10⁵〜10⁶ 程度になると、O(N log N) 以下の手法が必須です。まずは「どのデータ構造・アルゴリズムが適合するか」をメモに残す習慣をつけましょう。

2‑2. アプローチ候補の一覧と比較

問題	候補アプローチ	メリット	デメリット
ABC302 C	① 累積和 + `bisect_left`（二分探索） ② 前処理なしでハッシュマップ	実装がシンプル、計算量は O((N+Q) log N) または O(N+Q)	ハッシュは衝突リスク、二分探索はインデックスオフセットに注意
ARC127 C	① セグメントツリー（最小） ② Fenwick 木＋カスタム集約関数	セグ木は区間最小取得が直接可能	実装行数が多く、メモリ使用量がやや大きい
AGC055 D	① NTT（整数版 FFT） ② 高速乗算ライブラリ（`atcoder::convolution`）	O(N log N) の高速畳み込みが実現できる	素数 MOD と primitive root の選択が必須、コードが長くなる

2‑3. アルゴリズム選定の指針

計算量 が制約を満たすか
実装コストとデバッグ容易性 のバランス
使用言語の標準ライブラリや外部ライブラリ の有無

上記基準に照らすと、最適解は次の通りです。
ABC302 C → 二分探索、ARC127 C → セグメントツリー、AGC055 D → NTT。

3. 実装例（Python・C++・Java）

以下に各言語で コメントを日本語統一 した実装コードと解説を示します。すべてのサンプルは公式エディトリアルのアイデアを踏まえつつ、可読性と速度を両立させています。

3‑1. ABC302 C – Python

import sys
from bisect import bisect_left

def main() -&gt; None:
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)

    N = next(it)
    A = [next(it) for _ in range(N)]

    # 累積和（先頭に 0 を付与）を作成
    pref = [0]
    for x in A:
        pref.append(pref[-1] + x)

    Q = next(it)
    ans = []
    for _ in range(Q):
        X = next(it)
        # bisect_left は「&gt;=」になる最小インデックスを返す
        idx = bisect_left(pref, X)
        ans.append(str(idx))          # 1-indexed が要求される

    sys.stdout.write(&quot;\n&quot;.join(ans))

if __name__ == &quot;__main__&quot;:
    main()

import sys

from bisect import bisect_left

def main() -> None:

data = list(map(int, sys.stdin.buffer.read().split()))

it = iter(data)

N = next(it)

A = [next(it) for _ in range(N)]

# 累積和（先頭に 0 を付与）を作成

pref = [0]

for x in A:

pref.append(pref[-1] + x)

Q = next(it)

ans = []

for _ in range(Q):

X = next(it)

# bisect_left は「>=」になる最小インデックスを返す

idx = bisect_left(pref, X)

ans.append(str(idx)) # 1-indexed が要求される

sys.stdout.write("\n".join(ans))

if __name__ == "__main__":

main()

ポイント
- bisect_left で二分探索部をワンライナー化。
- 入出力は sys.stdin.buffer.read() で高速化し、全体計算量は O((N+Q) log N)。

3‑2. ARC127 C – C++（GNU C++17）

#include &lt;bits/stdc++.h&gt;
using namespace std;

struct SegTree {
    int n;                     // 木のサイズ（2 の冪）
    const long long INF = (1LL &lt;&lt; 60);
    vector&lt;long long&gt; seg;    // 最小値を保持

    explicit SegTree(int sz) { init(sz); }

    void init(int sz) {
        n = 1;
        while (n &lt; sz) n &lt;&lt;= 1;
        seg.assign(2 * n, INF);
    }

    // 点更新：位置 idx に val を設定
    void set_val(int idx, long long val) {
        idx += n;
        seg[idx] = val;
        for (idx &gt;&gt;= 1; idx; idx &gt;&gt;= 1)
            seg[idx] = min(seg[2 * idx], seg[2 * idx + 1]);
    }

    // 区間最小取得 [l, r)（0-indexed）
    long long query(int l, int r) const {
        long long res = INF;
        for (l += n, r += n; l &lt; r; l &gt;&gt;= 1, r &gt;&gt;= 1) {
            if (l &amp; 1)   res = min(res, seg[l++]);
            if (r &amp; 1)   res = min(res, seg[--r]);
        }
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;                     // 配列長とクエリ数
    cin &gt;&gt; N &gt;&gt; Q;
    vector&lt;long long&gt; A(N);
    for (auto &amp;x : A) cin &gt;&gt; x;

    SegTree st(N);
    for (int i = 0; i &lt; N; ++i) st.set_val(i, A[i]);

    while (Q--) {
        int l, r;                 // 入力は 1-indexed
        cin &gt;&gt; l &gt;&gt; r;
        cout &lt;&lt; st.query(l - 1, r) &lt;&lt; '\n';
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

struct SegTree {

int n; // 木のサイズ（2 の冪）

const long long INF = (1LL << 60);

vector<long long> seg; // 最小値を保持

explicit SegTree(int sz) { init(sz); }

void init(int sz) {

n = 1;

while (n < sz) n <<= 1;

seg.assign(2 * n, INF);

}

// 点更新：位置 idx に val を設定

void set_val(int idx, long long val) {

idx += n;

seg[idx] = val;

for (idx >>= 1; idx; idx >>= 1)

seg[idx] = min(seg[2 * idx], seg[2 * idx + 1]);

}

// 区間最小取得 [l, r)（0-indexed）

long long query(int l, int r) const {

long long res = INF;

for (l += n, r += n; l < r; l >>= 1, r >>= 1) {

if (l & 1) res = min(res, seg[l++]);

if (r & 1) res = min(res, seg[--r]);

}

return res;

}

};

int main() {

ios::sync_with_stdio(false);

cin.tie(nullptr);

int N, Q; // 配列長とクエリ数

cin >> N >> Q;

vector<long long> A(N);

for (auto &x : A) cin >> x;

SegTree st(N);

for (int i = 0; i < N; ++i) st.set_val(i, A[i]);

while (Q--) {

int l, r; // 入力は 1-indexed

cin >> l >> r;

cout << st.query(l - 1, r) << '\n';

}

return 0;

}

ポイント
- INF を十分大きく設定し、負数やオーバーフローを防止。
- 区間は [l‑1, r) の半開区間に変換していることに注意。

3‑3. AGC055 D – Java（OpenJDK 17）

import java.io.*;
import java.util.*;

public class Main {
    // NTT 用の mod と primitive root（998244353 は 2^23 * 7 + 1）
    static final long MOD = 998244353L;
    static final long PRIMITIVE_ROOT = 3L;

    public static void main(String[] args) throws IOException {
        FastScanner fs = new FastScanner(System.in);
        int n = fs.nextInt();
        long[] a = new long[n];
        for (int i = 0; i &lt; n; ++i) a[i] = fs.nextLong();

        int m = fs.nextInt();
        long[] b = new long[m];
        for (int i = 0; i &lt; m; ++i) b[i] = fs.nextLong();

        long[] c = convolution(a, b);   // NTT による高速畳み込み

        PrintWriter out = new PrintWriter(new BufferedWriter(
                new OutputStreamWriter(System.out)));
        for (long v : c) out.println(v % MOD);
        out.flush();
    }

    /* -------------------------------------------------------------
       Number Theoretic Transform（NTT）実装
       - bit-reversal と iterative 方式で高速化
       - 逆変換時は逆根と N の逆元で正規化
    ------------------------------------------------------------- */
    static long[] convolution(long[] a, long[] b) {
        int size = 1;
        while (size &lt; a.length + b.length) size &lt;&lt;= 1;

        long[] A = Arrays.copyOf(a, size);
        long[] B = Arrays.copyOf(b, size);

        ntt(A, false);
        ntt(B, false);
        for (int i = 0; i &lt; size; ++i) A[i] = (A[i] * B[i]) % MOD;
        ntt(A, true);
        return A;
    }

    static void ntt(long[] a, boolean invert) {
        int n = a.length;

        // ビット反転置換
        for (int i = 1, j = 0; i &lt; n; ++i) {
            int bit = n &gt;&gt; 1;
            for (; (j &amp; bit) != 0; bit &gt;&gt;= 1) j ^= bit;
            j ^= bit;
            if (i &lt; j) { long tmp = a[i]; a[i] = a[j]; a[j] = tmp; }
        }

        for (int len = 2; len &lt;= n; len &lt;&lt;= 1) {
            long wlen = modPow(PRIMITIVE_ROOT, (MOD - 1) / len);
            if (invert) wlen = modInverse(wlen);
            for (int i = 0; i &lt; n; i += len) {
                long w = 1;
                for (int j = 0; j &lt; len / 2; ++j) {
                    long u = a[i + j];
                    long v = (a[i + j + len / 2] * w) % MOD;
                    a[i + j] = (u + v) % MOD;
                    a[i + j + len / 2] = (u - v + MOD) % MOD;
                    w = (w * wlen) % MOD;
                }
            }
        }

        if (invert) {
            long invN = modInverse(n);
            for (int i = 0; i &lt; n; ++i) a[i] = (a[i] * invN) % MOD;
        }
    }

    static long modPow(long base, long exp) {
        long res = 1;
        while (exp &gt; 0) {
            if ((exp &amp; 1) == 1) res = (res * base) % MOD;
            base = (base * base) % MOD;
            exp &gt;&gt;= 1;
        }
        return res;
    }

    static long modInverse(long x) { return modPow(x, MOD - 2); }

    // ---------------------------------------------------------
    // 高速入力クラス
    // ---------------------------------------------------------
    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 &lt;&lt; 16];
        private int ptr = 0, len = 0;

        FastScanner(InputStream is) { this.in = is; }

        private int readByte() throws IOException {
            if (ptr &gt;= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len &lt;= 0) return -1;
            }
            return buffer[ptr++];
        }

        long nextLong() throws IOException {
            int c; while ((c = readByte()) &lt;= ' ') if (c == -1) return Long.MIN_VALUE;
            boolean neg = false;
            if (c == '-') { neg = true; c = readByte(); }
            long val = 0;
            while (c &gt; ' ') {
                val = val * 10 + (c - '0');
                c = readByte();
            }
            return neg ? -val : val;
        }

        int nextInt() throws IOException { return (int) nextLong(); }
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

import java.io.*;

import java.util.*;

public class Main {

// NTT 用の mod と primitive root（998244353 は 2^23 * 7 + 1）

static final long MOD = 998244353L;

static final long PRIMITIVE_ROOT = 3L;

public static void main(String[] args) throws IOException {

FastScanner fs = new FastScanner(System.in);

int n = fs.nextInt();

long[] a = new long[n];

for (int i = 0; i < n; ++i) a[i] = fs.nextLong();

int m = fs.nextInt();

long[] b = new long[m];

for (int i = 0; i < m; ++i) b[i] = fs.nextLong();

long[] c = convolution(a, b); // NTT による高速畳み込み

PrintWriter out = new PrintWriter(new BufferedWriter(

new OutputStreamWriter(System.out)));

for (long v : c) out.println(v % MOD);

out.flush();

}

/* -------------------------------------------------------------

Number Theoretic Transform（NTT）実装

- bit-reversal と iterative 方式で高速化

- 逆変換時は逆根と N の逆元で正規化

------------------------------------------------------------- */

static long[] convolution(long[] a, long[] b) {

int size = 1;

while (size < a.length + b.length) size <<= 1;

long[] A = Arrays.copyOf(a, size);

long[] B = Arrays.copyOf(b, size);

ntt(A, false);

ntt(B, false);

for (int i = 0; i < size; ++i) A[i] = (A[i] * B[i]) % MOD;

ntt(A, true);

return A;

}

static void ntt(long[] a, boolean invert) {

int n = a.length;

// ビット反転置換

for (int i = 1, j = 0; i < n; ++i) {

int bit = n >> 1;

for (; (j & bit) != 0; bit >>= 1) j ^= bit;

j ^= bit;

if (i < j) { long tmp = a[i]; a[i] = a[j]; a[j] = tmp; }

}

for (int len = 2; len <= n; len <<= 1) {

long wlen = modPow(PRIMITIVE_ROOT, (MOD - 1) / len);

if (invert) wlen = modInverse(wlen);

for (int i = 0; i < n; i += len) {

long w = 1;

for (int j = 0; j < len / 2; ++j) {

long u = a[i + j];

long v = (a[i + j + len / 2] * w) % MOD;

a[i + j] = (u + v) % MOD;

a[i + j + len / 2] = (u - v + MOD) % MOD;

w = (w * wlen) % MOD;

}

if (invert) {

long invN = modInverse(n);

for (int i = 0; i < n; ++i) a[i] = (a[i] * invN) % MOD;

}

static long modPow(long base, long exp) {

long res = 1;

while (exp > 0) {

if ((exp & 1) == 1) res = (res * base) % MOD;

base = (base * base) % MOD;

exp >>= 1;

}

return res;

}

static long modInverse(long x) { return modPow(x, MOD - 2); }

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

// 高速入力クラス

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

static class FastScanner {

private final InputStream in;

private final byte[] buffer = new byte[1 << 16];

private int ptr = 0, len = 0;

FastScanner(InputStream is) { this.in = is; }

private int readByte() throws IOException {

if (ptr >= len) {

len = in.read(buffer);

ptr = 0;

if (len <= 0) return -1;

}

return buffer[ptr++];

}

long nextLong() throws IOException {

int c; while ((c = readByte()) <= ' ') if (c == -1) return Long.MIN_VALUE;

boolean neg = false;

if (c == '-') { neg = true; c = readByte(); }

long val = 0;

while (c > ' ') {

val = val * 10 + (c - '0');

c = readByte();

}

return neg ? -val : val;

}

int nextInt() throws IOException { return (int) nextLong(); }

}

ポイント
- modPow と modInverse を自前実装し、外部ライブラリに依存しない形にした。
- ビット反転置換とイテレーティブ NTT により O(N log N) の計算量を確保。

4. 計算量・メモリ分析とバグ回避策

4‑1. 時間・空間の見積もり

問題	時間計算量（最悪ケース）	空間計算量
ABC302 C	O((N+Q) log N)（累積和 O(N)、二分探索 O(log N)）	O(N)（累積和配列）
ARC127 C	O((N+Q) log N)（セグ木の点更新・区間最小取得）	O(2·⌈log₂N⌉) ≈ O(N)
AGC055 D	O(L log L)（L は 2 の冪で `>= N+M`）	O(L)（NTT 用配列）

すべてのケースで、典型的な制限時間 2 秒 に収まります。

4‑2. よくある落とし穴と対策

バグパターン	原因	防止策
インデックスオフセットミス（1-index → 0-index）	入力が 1-index のまま配列に渡す	変換処理を関数化し、コメントで「0 基準へ変換」旨明記
累積和・NTT で `int` がオーバーフロー	計算途中の値が 2³¹‑1 を超える	常に `long long`（C++）や `long`（Java）を使用
入出力が遅くなる	大量データを `cin >>` / `input()` で読んだ	C++ は `ios::sync_with_stdio(false); cin.tie(nullptr);`、Python は `sys.stdin.buffer.read()` を利用
再帰深さ超過（DFS 系）	再帰呼び出しが数万回に達する	必要ならスタックサイズ拡張フラグ `-Wl,--stack,256000000` か、ループ化へ置き換える

5. 応用パターンと練習問題

5‑1. テンプレート化できる解法パターン

パターン	代表的な適用例
二分探索 + 累積和	「部分和が K 以上になる最小区間」や「配列の中央値を求める」系問題
セグメントツリー（RMQ）	「区間更新＋クエリ」「動的最大/最小取得」全般
NTT / FFT 畳み込み	「文字列マッチング高速化（Convolution）」や「組合せ数の高速計算」

これらを コードスニペット として保存すれば、類似問題に対する実装時間が大幅に短縮できます。

5‑2. 練習用サンプル入力と期待出力

ABC302 C – 累積和二分探索

入力例

3 1 4 1 5

期待出力

3
5
1

ARC127 C – 区間最小値クエリ

入力例
8 5
7 3 9 2 6 4 8 1
2 5
1 4
3 8
5 7
1 8

入力例

8 5

7 3 9 2 6 4 8 1

2 5

1 4

3 8

5 7

1 8

期待出力

AGC055 D – 多項式畳み込み（NTT）

入力例

1 2 3

4 5 6

期待出力（mod 998244353）

上記ケースは 境界条件 と 計算量の極端な入力 を意識して作成しています。自分で手を動かし、必ず正解が得られることを確認してください。

6. 次へのステップ

本稿のコードスニペットを自分のテンプレートに組み込む
同様のパターンが出題される過去問（例：ABC307 D、ARC140 B、AGC058 C）を解くことで定着度を高める
公式エディトリアル（上記リンク）を読み込み、証明や実装上の工夫 を自分の言葉でまとめる

これらを繰り返すことで、「問題文を読んだ瞬間に最適解法がイメージできる」 状態へと成長できます。次回開催される ABC／ARC／AGC でも、自信を持って挑戦しましょう！