結論から言うと、命令数の最小値は \(\displaystyle\left\lceil\max\left(\log_2 N, \tfrac25(N-1)\right)\right\rceil\) になります。

下界 1 : \(\log_2 N\)

\(L\) 回の操作で作ることのできる整数列の長さが \(2^L\) 以下であることから明らかです。

\(N ≤ 8\) の場合は以下で下界を達成できます。

下界 2 : \(\frac25(N-1)\)

以下 \(N ≥ 9\) とします。

• \((l, l + 1, …, r - 1, r)\) の形以外の整数列を作ることは無意味です。
  • これを使って \((l, l + 1, …, r - 1, r)\) の形を作れないため
• 以下どの変数に入れるか (どの変数を上書きするか) を考えず、計算したことがあれば全部使えるものとします。
• 同じ区間を複数回作ることは無意味です。
  • 計算したことがあれば使えるので、 \(2\) 回目以降を消してしまって、 \(1\) 回しか作らないことにして問題ないです。
• 同じ区間を \(1\) 回しか作れないことから、「区間 \([l, r]\) を作った (\(l < r\)) \(\implies\) 唯一の \(l ≤ d < r\) が存在して、\([l, d] + [d + 1, r]\) によって \([l, r]\) を作った」がわかります。
  • どれから作ったかのグラフを考えると、区間 \([1, 1], [1, 2], …, [1, N]\) のそれぞれから二分木が生えているような構造になることがわかります。
• このグラフから \([1,N]\) を作るのに必要な部分のみを取り出すと、これは演算を \(N-1\) 回含む、\(2N-1\) 頂点 \(2N-2\) 辺の二分木になっています。この二分木を \(T\) とします。
  • \(T\) を根から下がっていく方向に見ていくと、ある区間を \(2\) 分割することを繰り返しています。したがって、\(T\) から \(2\) 頂点を取ると、それらは包含関係にあるか交わらないかのどちらかです。
• 総演算回数を固定し、これを \(S\) とします。命令数は \(\frac{S}{4}\) 以上になります。
• \(T\) に含まれる \([1,i]\) の形の頂点の数を \(A\) とします。これらの頂点は、「計算するのに \(1\) つ前の計算結果が必要」という依存関係があるので、命令数は \(A - 1\) 以上になります。
  • \(2\) つ以上前の計算結果を使うと仮定すると、包含関係にないが共通部分のある \(2\) 頂点ができてしまいます。
• \(T\) を計算するための演算回数が \(N-1\) 回、\(T\) に含まれない \([1,i]\) の形の頂点を計算するための演算回数が \(N-A\) 回以上なので、\((N-1)+(N-A)≤S\) が成り立ちます。
  • これより、\(A≥2N-1-S\) となり、命令数は \(2N-2-S\) 以上になります。
• \(\max\left(\frac{S}{4},2N-2-S\right)\) は \(S = \frac85(N-1)\) のとき最小化され、 \(\frac{S}{4} = 2N-2-S = \frac25(N-1)\) になります。したがって、\(\frac25(N-1)\) は命令数の下界です。

下界を達成する : \(\left\lceil\frac25(N-1)\right\rceil\)

どうすればこれを達成できるでしょうか？

\(1\) 並列の場合は累積和の要領で \(N - 1\) 命令、\(N\) 並列の場合はセグメント木の要領で \(\log_2 N\) 命令になります。

\(4\) 並列はこの中間と考えることができます。例えば、平方分割をしてみるのはいいアイデアでしょう。

---

\(N = 16, L = 6\) の場合を考えます。これは例えば以下のように達成できます。

\(16\) マスを \(4\) マスずつ \(4\) ブロックに区切り、各ブロック内を並列に累積和し、ブロック全体を累積和しています。

二分木 \(T\) に含まれる \([1, i]\) の形の頂点は \([1,1], [1,2], [1,3], [1,4], [1,8], [1,12], [1,16]\) の \(7\) 個で、これに含まれない \([1,i]\) の形の頂点はブロック内で部分的に累積和をしています。

これをうまく一般化しましょう。マス \(1,2,…,N\) を \(L+1\) 個のブロックに区切り、各ブロック内を累積和しながら、ブロック全体の累積和も進めていきます。ただし、ブロックが \(L+1\) 個あるので、「ブロック全体の累積和」は毎回の命令で \(1\) 個進める必要があります。

これを踏まえてブロックに区切ります。以下のように、「ブロック全体の累積和」を毎回進めることに注意しながら、できるだけ各ブロックが長くなるようにします。

ブロックの長さが十分になったら、各ブロックを伸ばす代わりに残した部分を計算します。

\(L = \left\lceil\frac25(N-1)\right\rceil\) のとき、これで命令数 \(\left\lceil\frac25(N-1)\right\rceil\) を達成できるので、命令数の最小値は \(\left\lceil\frac25(N-1)\right\rceil\) です。

実装例 (Python)