【AtCoder】「分野別　初中級者が解くべき過去問精選 100 問」解答例【全探索：全列挙】

この記事は 【AtCoder】初中級者が解くべき過去問精選 100 問を緑色コーダーが C++ で解いてみた の子記事です。お読みになる前に親記事をご確認ください。

1. ITP1_7_B – How Many Ways?

• 問題へのリンク

この問題を難しく感じる方は レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【初級編：競プロを始めよう】 の「1-6. 「茶色コーダー」になるためのガイドライン」を確認し、未実施なステップがあれば、そちらから挑戦した方がいいかもしれません。

n は高々 100 までのため、3 つの数字の組み合わせを全て列挙しても、計算量は O(n^3) = 10^6 程度です。時間制限は 1 秒のため、十分に間に合います。
基本的には 3 重の for 文を使って組み合わせを列挙します。ただし、下記のように列挙すると同じ組み合わせの異なる並び (例: (1, 3, 5) と (3, 1, 5)) をすべて列挙してしまいます。

for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
        if (j == i)
            continue;
        for (int k = 1; k <= n; ++k) {
            if (k == i || k == j)
                continue;

組み合わせの個数を問われているため、同じ組み合わせの異なる並びを区別して数えてしまうことを防ぐ工夫が必要です。例えば、下記のように 2 つめの for 文の j の初期化を i + 1, 3 つめの for 文の k の初期化を j + 1 とすると、必ず i < j < k が成り立つため、(1, 3, 5) などの昇順の並びのみを列挙することができます。

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

1 つの組み合わせに対し、1 つの並びを列挙するため、同じ組み合わせの異なる並びの列挙を防ぐことができます。

あとは、組み合わせの数を数える変数 cnt を用意して、i + j + k == x が成立する場合に cnt の値を 1 大きくすれば、組み合わせを数えられます。

int cnt = 0;
for (int i = 1; i <= n; ++i) {
    for (int j = i + 1; j <= n; ++j) {
        for (int k = j + 1; k <= n; ++k) {
            if (i + j + k == x)
                ++cnt;
        }
    }
}

• 解答例 1

この問題については上記の解法で十分なのですが、n が 10^4 程度の大きさの場合、計算量は \Omega(n^3) = 10^{12} 程度となり時間制限に違反する可能性が高いです。計算量 O(n^2) の解法も存在するため、そちらも紹介します。

前述の解法では i, j, k を全て決めてから、i + j + k == x の真偽を確認しました。ですが、i, j が決まった時点で i + j + k == x を満たす k の値の候補は x - i - j に定まります。k = x - i - j とした時に k が j < k かつ k <= n を満たすならば、(i, j, k) は数えるべき組み合わせになります。
プログラムとしては下記のようになります。

int cnt = 0;
for (int i = 1; i <= n; ++i) {
    for (int j = i + 1; j <= n; ++j) {
        int k = x - i - j;
        if (j < k && k <= n)
            ++cnt;
    }
}

k についての for 文がなくなったため、計算量は O(n^2) となります。

• 解答例 2

2 つめの解法では「和が x になる 3 つの数の組み合わせの最後の数は x から 2 つめまでの数の和を引けば計算できる」という考え方を使って計算量を O(n^3) から O(n^2) に減らしました。この考え方と二分探索を使って、計算量を O(n^4) を O(n^2\log(n)) まで削減する問題もあるため、覚えておくとよいかと思います。

2. AtCoder Beginner Contest 106 B – 105

• 問題へのリンク

約数の列挙については、レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】 の「高速な素数判定法」と類似した手法が AtCoder 版！マスター・オブ・整数 (素因数分解編) の「3. 約数列挙」で解説されています。この手法を使って数 N の約数を列挙したときの計算量は O(\sqrt{N}) です。1 から N までの奇数を全て試したとしても O(N\sqrt{N}) で N \leq 200 なら間に合います。
この問題では約数の個数がわかればよいため、下記のような約数を数える関数を作成します。

int count_divisors(int N)
{
    int cnt = 0;
    for (int i = 1; i * i <= N; ++i) {
        if (N % i == 0) {
            ++cnt;
            if (N / i != i)
                ++cnt;
        }
    }
    return cnt;
}

あとは for 文で N までの奇数を列挙して、約数の個数が 8 個である数を数えれば解けます。奇数の列挙は初期値の奇数を 2 づつ増やしていけばできます。

int cnt = 0;
for (int i = 1; i <= N; i += 2) {
    if (count_divisors(i) == 8)
        ++cnt;
}

• 解答例

3. AtCoder Beginner Contest 122 B – ATCoder

• 問題へのリンク

S の部分文字列の先頭と末尾を表す添字をそれぞれ i, j とし S の i 番目の文字から j 番目の文字までを取り出した部分文字列を S[i, j] とします。また、S の k 番目の文字を S[k] とします。

i \leq k \leq j を満たす任意の k について S[k] が ‘A’, ‘T’, ‘G’, ‘C’ のいずれかであるとき、S[i, j] は ATGC 文字列です。そのため、以下の解法が考えられます。

1. すべての部分文字列を列挙します。
2. 各部分文字列に対し、ATGC 文字列であるかを判定します。
3. 部分文字列が ATGC 文字列になる場合、部分文字列の長さをこれまでの最大値と比較し最大値を更新します。

S の長さを N をすると、上記の解法の計算量は

• 先頭 i の選び方 O(N)
• 末尾 j の選び方 O(N)
• ATGC 文字列の判定 (k のループ) O(N)

の組み合わせで O(N^3) です。N \leq 10 のため、この解法でも間に合います。

• 解答例 1

j についての漸化式的な考え方で計算量を減らすことを考えます。
S[i, j] が ATGC 文字列であるとき、S[i, j + 1] が ATGC 文字列であるかは S[j + 1] が ‘A’, ‘T’, ‘G’, ‘C’ のいずれかであるか、で判定できます。i 文字目から j 文字目までが ‘A’, ‘T’, ‘G’, ‘C’ のいずれかであることは S[i, j] が ATGC 文字列であるため、確認済だからです。
また、S[i, j] が ATGC 文字列でないときを考えます。このとき i \leq k \leq j を満たす、ある k について S[k]は ‘A’, ‘T’, ‘G’, ‘C’ のどれでもありません。そのため、j_2 > j なる j_2 について、S[i, j_2] が ATGC 文字列になることはありません。毎回 k 番目の文字の判定で否定されます。つまり、一度 ATGC 文字列でなくなった場合、それ以降、末尾を長くして (j の値を増やして) 調べる必要がありません。

例として “ATCODER” という文字列の i = 0 のときを考えます。

j = 0 のとき S[j] は ‘A’ のため、S[i, j] は ATGC 文字列です。
j = 1 のとき S[j] は ‘T’ のため、j = 0 のときとあわせて S[i, j] は ATGC 文字列です。
j = 2 のとき S[j] は ‘C’ のため、j = 1 のときとあわせて S[i, j] は ATGC 文字列です。
j = 3 のとき S[j] は ‘O’ のため、 S[i, j] は ATGC 文字列ではありません。
j \geq 4 のとき S[i, 3] が ATGC 文字列ではないため、S[i, j] は ATGC 文字列ではありません。

以上のように、これまでの結果を使うことにより計算量 O(1) で ATGC 文字列の判定ができます。

全体の計算量は

• 先頭 i の選び方 O(N)
• 末尾 j の選び方 O(N)
• ATGC 文字列の判定 O(1)

で O(N^2) となります。

また、最大の長さを求める問題であるため、S[i, j], S[i, j + 1] が共に ATGC 文字列である場合は S[i, j] の長さと現時点の最長の長さを比較する必要はありません。もし S[i, j] の方が長くても S[i, j + 1] の方が更に長いためです。比較は S[i, j] が ATGC 文字列, S[i, j + 1] が ATGC 文字列でない場合のみで十分です。

int max_len = 0;
for (int i = 0; i < N; ++i) {
    int len = 0;
    for (int j = i; j < N; ++j) {
        // is_ATGC() は引数が 'A', 'T', 'G', 'C' のいずれかの文字であるかを判定する関数
        if (is_ATGC(S.at(j)))
            ++len;
        else
            break;
    }
    if (max_len < len)
        max_len = len;
}

• 解答例 2

今度は i に着目して計算量を減らす方法を考えます。
S[i, j] が ATGC 文字列, S[i, j + 1] が ATGC 文字列でないとします。このとき、S[j + 1] は ‘A’, ‘T’, ‘G’, ‘C’ のどれでもありません。i + 1 \leq i_2 \leq j + 1 となる i_2 について S[i_2, j_2] が ATGC 文字列のとき、S[i_2, j_2] の長さは S[i, j + 1] の長さより短いです。なぜなら S[j + 1] が　’A’, ‘T’, ‘G’, ‘C’ のどれでもないことから、j_2 \leq j がわかるためです。
2 つめの解法で S[i, j] が ATGC 文字列, S[i, j + 1] が ATGC 文字列でない j を見つけた後に i を 1 大きくするのではなく、i を j + 2 に更新すれば、先頭が i + 1, \dots, j + 1 番目の文字である部分文字列の無駄な探索を減らせます。この方法は全体を通して j が 0 から N – 1 までの場合を一度しか試さないため、計算量は O(N) になります。
プログラムとしては i, j の for 文を以下のように変更します。

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

• 解答例 3

4. パ研杯2019 C – カラオケ

• 問題へのリンク

M 曲から曲 T_1, T_2 を選ぶ組み合わせが \frac{M(M – 1)}{2} 通りです。N 人が歌うため、各 (T_1, T_2) の組み合わせに対し、グループの得点の計算には O(N) かかります。全体の計算量は O(M^2N) で時間制限に違反せずに計算できます。

A_{ij} の上限が 10^8 と大きく、グループの得点は最大、10^{10} になります。32bit の整数型だと、オーバーフローを起こす可能性があるため、64bit 整数型などの、より大きな整数型を使います。

int64_t max_score = -1;
for (int t1 = 0; t1 < M; ++t1) {
    for (int t2 = t1 + 1; t2 < M; ++t2) {
        int64_t score = 0;
        for (int i = 0; i < N; ++i)
            score += max(A[i][t1], A[i][t2]);
        if (max_score < score)
            max_score = score;
    }
}

• 解答例