C++で可変長ループを書こう！

この記事は、きりさんの記事「可変長ループを書こう！」のコードを読むのに時間がかかったので、それを解きほぐしていこうという趣旨の記事です。（後でコピペして使い回せる様にしたいというのもあります。）

きりさんの元記事では、愚直なやり方との比較や空間計算量に関する利点、他のアプローチとの比較などが書かれていますので、まずはそちらを読んで頂きたいと思います。

コードの内容はほぼきりさんの Python のコードの例３を C++ にしただけで、解説のコメントを各ステップ毎につけました。最初はデバッガーで１ステップずつ追わないと何やってるか分かりませんでしたが、コメントをつけていくとやっている事は単純だと分かります（というか動きは多重ループそのものですね）。

可変長の多重ループ（つまり k 重のネストされた for 文で k が変数になっているもの）、多用するかは分かりませんが、夢がありません？
プログラミングを始めた時に、こんな事できないのかなって一度は思ったことあるのではないでしょうか。
競技プログラミングでは計算量を抑える必要があるので、なんでもかんでも可変長多重ループにする事はできませんが、可変長多重ループが使える問題も存在します。

きりさんのコードから変えた変数名は以下の通り。インデックス配列ZをIに、ループの階層を表す変数iをkにしました。ループのインデックスはよく i, j, k, ... というのが使われるので、$i_0$, $i_1$, $i_2$, ... , $i_{K-1}$ にしたという感じで、コードの中で $i_k$ をI[k]で表しています。また、条件を満たしていないかチェックする関数chkは満たされていない時にtrueということだったのでNGという名前にしました。

また、コードにつけたコメント中で階層が上（外側）というのは k がより小さい事を表し、階層が下（内側）というのは k がより大きいことを表します。

# include <bits/stdc++.h>
using namespace std;

vector<int64_t> I; // I はループのインデックスをまとめた配列。第 k 階層のインデックスが I[k]。条件チェック関数内で使うなら global で定義しておくのが手軽。

bool NG(int64_t k) //複数のループインデックスが、所望の条件を満たしているかをチェックする関数。満たさない場合に true となるように定義している。
{
  if (k == 0) //今考えている例では第 0階層では条件を満たす。配列外参照を起こさない為にも例外的に最初に記述している。
    return false;
  if ((I[k - 1] + I[k]) % 3 == 0) //この条件を問題に応じて変える。
  {
    return true;
  }
  else //シンプルに可変長多重ループするだけならいつも false を返せば良い。
  {
    return false;
  }
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  constexpr char endl = '\n';
  ///////////////////////////

  int64_t K = 10;                    //可変長多重ループの長さ（階層数）。問題に応じて他の変数やインプットから与えられる。
  vector<int64_t> L(K, 0), R(K, 0); //第 k 階層で半開区間 [L[k], R[k]) を考える。つまり L[k] <= I[k] < R[k]。
  I.assign(K, 0);                   //インデックスの配列を初期化する。
  R[0] = 1;                         //第0階層のループの右端は予め決まっているものとする。この値は状況に応じて変える。
  int64_t k = 0;                    // ループの階層を表す。第 0階層（0-index）から始める。
  int64_t cnt = 0;                  //これは今ループ内でカウントする例を考えているのでカウンター変数。問題によって変える。
  while (k >= 0)                    //普通の多重ループと同じような動きをするため第 k 階層の k が増えたり減ったりする。kが非負の間は続け、kが負になったら終了。
  {
    while (k < K - 1) //ループの最下層にいない場合に以下の処理をする。既に最下層にいたらスキップ。
    {
      k++;              //下の階層へ進む
      L[k] = 0;         //第k階層のループの左端を設定する。I[k] に依存して範囲が変わらないのであれば前処理をしてもよい（それほど計算量は変わらないと思いますが）。
      R[k] = accumulate(I.begin(), I.begin() + k, 0) + 2; //同様にループの右端を設定する。
      I[k] = L[k];      //第 k 階層のループインデックス I[k] を左端に設定する。
      if (NG(k))        //条件を満たさない事が分かれば下の階層の探索を打ち切る。
        break;
    }
    if (!NG(k)) //最下層（多重ループの最も内側）にいて条件を満たすときだけこの if 文の中に入る。（最下層にいない場合は上の処理で自動的にNG(k)==trueになっている。）
    {
      cnt++; //問題に応じた処理をする。
    }
    I[k]++;                       //処理が終わったので、あるいは条件を満たさないと分かったのでインクリメント。
    while (I[k] >= R[k] || NG(k)) //通常の for 文と同じように、インデックスをインクリメントしたら範囲内にあるか、条件を満たすかチェックする。片方でも満たさなければ以下の処理をする。
    {
      if (I[k] < R[k])     //この if 文が評価されるなら、上の while 文の条件と合わせて NG(k) == true になっている。
        I[k]++;            // インデックスは範囲内なので単純に１増やして探索する。
      while (I[k] >= R[k]) //上の if文が評価された場合インデックスを増やしているので、改めて範囲内かをチェック。
      {                    //（固定された上の階層のインデックス達に対して）第 k 階層は全て探索しきった。これからやりたいのは上の階層に戻ってインクリメントしてから下の階層に戻って探索をやり直すこと。
        k--;               //上の階層に上がる。
        if (k < 0)         //階層を 0-index にしたので、負になったら全て探索しきったことになる。
          break;
        I[k]++; //上がってきた階層でインデックスをインクリメントする。
      }
      if (k < 0) //上の while 文内の処理で k が負になっている場合は探索が終了した事を表す。
        break;   // この後一番外側の while 文の条件に戻って k < 0 なのでコードが終了する。
    }
  }
  cout << cnt << endl;
}

同じものをコメント無しで貼っておきます。

# include <bits/stdc++.h>
using namespace std;

vector<int64_t> I;

bool NG(int64_t k)
{
  if (k == 0)
    return false;
  if ((I[k - 1] + I[k]) % 3 == 0)
  {
    return true;
  }
  else
  {
    return false;
  }
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  constexpr char endl = '\n';
  ///////////////////////////

  int64_t K = 10;
  vector<int64_t> L(K, 0), R(K, 0);
  I.assign(K, 0);
  R[0] = 1;
  int64_t k = 0;
  int64_t cnt = 0;
  while (k >= 0)
  {
    while (k < K - 1)
    {
      k++;
      L[k] = 0;
      R[k] = accumulate(I.begin(), I.begin() + k, 0) + 2;
      I[k] = L[k];
      if (NG(k))
        break;
    }
    if (!NG(k))
    {
      cnt++;
    }
    I[k]++;
    while (I[k] >= R[k] || NG(k))
    {
      if (I[k] < R[k])
        I[k]++;
      while (I[k] >= R[k])
      {
        k--;
        if (k < 0)
          break;
        I[k]++;
      }
      if (k < 0)
        break;
    }
  }
  cout << cnt << endl;
}