はじめに

　本記事はプログラミング初心者向けにfor文の入れ子構造を簡潔に書く方法を紹介するものです。競技プログラミングを念頭に置きながら書いていますが、競技プログラミングに限らず様々なコードを書く場面で役に立つテクニックだと思うので是非覚えておいてください。
　初心者にありがちな良くない書き方として過度に深いネスト構造があります。具体例として、ABC080のC問題を解く際、for文の入れ子を10回書いても間違いではありませんがコードの書き方として望ましくないのは明らかでしょう。
ABC080C問題
この書き方の問題は主に二つで、一つ目はコードを書くにしても読むにしてもとても辛いという点、二つ目はN重ループのNの値がコンパイルの時点で確定していなければ困ってしまう点です。個人の感覚にもよるところですがfor文の入れ子は3重が限度だと思います。それ以上にfor文を繰り返したい場合、簡潔なコードを書くための工夫を考えるべきでしょう。

問題設定

　今回は「5桁の4進数を00000から33333まで順に出力する」という問題を通して多重for文の書き方を二つ紹介します。

いけないやり方

for文の入れ子を5回繰り返します

ダメな例

include<iostream>
using namespace std;

typedef long long LL;

//ここからメイン
int main(void) {
    LL i, j, k, n, m;

    for (i = 0; i < 4; i++) {
        for (j = 0; j < 4; j++) {
            for (k = 0; k < 4; k++) {
                for (n = 0; n < 4; n++) {
                    for (m = 0; m < 4; m++) {
                        cout << i << j << k << n << m << endl;
                    }
                }
            }
        }
    }

    return 0;
}

正しい出力は得られますが桁数が増えると大変です。

やり方１

n進数を管理するクラスを使って繰り返しを行います

やり方１

#include<iostream>
#include<vector>
#include<string>

using namespace std;

typedef long long LL;
typedef vector<LL> VLL;


//n進数を管理するクラス
class N_Number {
public:
    N_Number(LL n, LL keta) {
        this->N_Shinsuu = n;

        VLL temp(keta, 0);
        this->numbers = temp;

    }

    //数を足す
    void plus(LL a) {
        this->numbers[0] += a;
        LL size = this->numbers.size();
        for (LL i = 0; i < size; i++) {
            if (i + 1 < size) {
                this->numbers[i + 1] += this->numbers[i] / this->N_Shinsuu;
            }
            this->numbers[i] %= this->N_Shinsuu;
        }
    }

    //全ての桁が同じ数字になっていればその数字を返す。それ以外の場合は -1 を返す
    LL check() {
        LL a = this->numbers[0];

        for (LL i = 0; i < this->numbers.size(); i++) {
            if (this->numbers[i] != a)return -1;
        }

        return a;
    }

    LL getNumber(LL keta) {
        return this->numbers[keta];
    }

    LL getKeta() {
        return this->numbers.size();
    }

    LL getShinsuu() {
        return this->N_Shinsuu;
    }

    void setNumber(LL keta, LL number) {
        if (0 <= number && number < this->getShinsuu()) {
            if (0 <= keta && keta < this->getKeta()) {
                this->numbers[keta] = number;
                return;
            }
        }

        cout << "er" << endl;
    }

    void setAllNumbers(LL number) {
        LL size = this->getKeta(), i;
        for (i = 0; i < size; i++) {
            this->setNumber(i, number);
        }
    }

private:
    VLL numbers;
    LL N_Shinsuu;
};

//ここからメイン
int main(void) {
    N_Number i(4, 5);

    while (true)
    {
        string s;
        for (LL j = i.getKeta() - 1; j >= 0; j--) {
            s += to_string(i.getNumber(j));
        }

        cout << s << endl;

        if (i.check() == i.getShinsuu() - 1)break;
        i.plus(1);
    }

    return 0;
}

ネストが深くなりませんし桁数が変わっても簡単に対応できます。

やり方２

再帰を使います。

やり方２

#include<iostream>
#include<vector>
#include<string>

using namespace std;

typedef long long LL;
typedef vector<LL> VLL;

//再帰で繰り返しを行う
void ForCout(LL n, LL keta, VLL numbers) {
    if (numbers.size() == keta) {
        string s;
        for (LL i = 0; i < numbers.size(); i++) {
            s += to_string(numbers[i]);
        }
        cout << s << endl;
        return;
    }

    for (LL i = 0; i < n; i++) {
        VLL temp = numbers;
        temp.push_back(i);
        ForCout(n, keta, temp);
    }
}

//ここからメイン
int main(void) {

    VLL numbers;
    ForCout(4, 5, numbers);

    return 0;
}

再帰は少し難しいかもしれませんが便利な概念なので練習しましょう。

さいごに

　今回はネストが深くなりすぎない多重ループの書き方を紹介しました。最初に紹介した問題とは別に今回の内容を練習できる問題を一つ記事の最後に置いておきますので、一度自分で書いてみることをお勧めします。また、間違いや直した方がいい点がありましたら指摘して頂けると幸いです。
ABC119C問題

N重ループの書き方

はじめに

問題設定

いけないやり方

やり方１

やり方２

さいごに