C++でゼロ配列から目標配列へ到達するための最小ステップ数を求める方法

問題概要

数値を含む配列 target[] が与えられます。すべての要素が0である配列 [0,0,0,…] を、次の2つの操作のみを使って target[] に変換するとき、必要な最小ステップ数を求めるのが課題です。

• インクリメント操作: 要素を1つずつ選んで1増やします。各インクリメントは個別にステップとしてカウントされます(n個の要素にn回のインクリメントを行う場合、ステップ数はn)。
• 倍加操作(ダブリング): 配列全体を一括して2倍にします。すべての要素が同時に2倍になるため、この操作は1ステップとしてカウントされます。

たとえば [0,0,0] は、全要素へのインクリメント操作によって最小3ステップで [1,1,1] になり、さらに1回の倍加操作で [2,2,2] に到達できます。この場合の合計ステップ数は4(インクリメント3回+倍加1回)です。

入力例1

target[]= { 1,2,2,3 }

出力例1

{0,0,0,0} から target への最小ステップ数 : 6

解説:

• 初期状態:{ 0,0,0,0 }
• インクリメント操作3回 → { 0,1,1,1 }(各要素は個別に増加)
• 倍加操作1回 → { 0,2,2,2 }(全要素が同時に2倍)
• インクリメント操作2回 → { 1,2,2,3 }

合計ステップ数 = 3 + 1 + 2 = 6

入力例2

target[]= { 3,3,3 }

出力例2

{0,0,0} から target への最小ステップ数 : 7

解説:

• 初期状態:{ 0,0,0 }
• インクリメント操作3回 → { 1,1,1 }
• 倍加操作1回 → { 2,2,2 }
• インクリメント操作3回 → { 3,3,3 }

合計ステップ数 = 3 + 1 + 3 = 7

アルゴリズムの考え方(逆算アプローチ)

このプログラムでは、「ゼロからターゲットへ向かう」のではなく、「ターゲットからゼロへ向かう」逆算のアプローチを採用しています。倍加操作の逆は半分にすること、インクリメント操作の逆は1減らすことなので、逆向きに辿ることで効率的に最小ステップ数を求められます。

• 整数型配列 target[] に到達すべき目標値を格納します。
• 関数 minSteps(int target[], int n) は、ターゲット配列とその長さ n を受け取り、全ゼロからターゲットに到達するための最小ステップ数を返します。
• 変数 count はステップ数を格納し、初期値は0です。
• 変数 max は最大値を格納し、初期値は target[0]、変数 pos はそのインデックスを格納し、初期値は0です。
• target[] の全要素がすでに0の場合は、操作不要のため0を返します。
• まず、奇数の要素から1を引いてすべて偶数にします。各減算ごとに count を1増やします(これはインクリメント操作の逆に相当します)。同時にループ内で最大値とその位置も更新していきます。
• 次に、最大値が1になるまで配列全体を2で割り続けます。除算の過程で奇数が出現した場合は1を引いて count を増やし、配列全体の除算操作1回につき count を1増やします。
• 最終的にすべての要素は0または1になります。残った1を0にするために各要素から1を引き、その回数だけ count を増やします。
• count に蓄積されたステップ数を結果として返します。

計算量は、除算フェーズが最大値のビット長に比例する O(log(max)) 回、各フェーズで配列全体を走査するため、全体としておよそ O(n log(max)) となります。

C++実装例

#include <bits/stdc++.h>
using namespace std;
int minSteps(int target[],int n){
    int i;
    int count=0;
    int max=target[0];
    int pos=0;
    // 全要素が0なら操作不要
    for(i=0;i<n;i++)
        if(target[i]==0)
            count++;
    if(count==n)
        return 0;
    count=0;
    // 奇数から1を引いてすべて偶数にしつつ、最大値と位置を記録
    for(i=0;i<n;i++){
        if(target[i]%2==1){
            target[i]=target[i]-1;
            count++;
        }
        if(target[i]>=max){
            max=target[i];
            pos=i;
        }
    }
    // 最大値が1になるまで配列全体を2で割る
    while(target[pos]!=1){
        for(i=0;i<n;i++){
            if(target[i]%2==1){
                target[i]=target[i]-1;
                count++;
            }
            target[i]=target[i]/2;
        }
        count++; // 倍加操作の逆(全体除算)を1ステップとしてカウント
    }
    // 残った1を0にする
    while(target[pos]!=0){
        for(i=0;i<n;i++){
            if(target[i]!=0){
                target[i]=target[i]-1;
                count++;
            }
        }
    }
    return count;
}
int main(){
    int target[]={15,15,15};
    cout<<"\nMinimum steps to get the given desired array:"<<minSteps(target,3);
    return 0;
}

出力

Minimum steps to get the given desired array:15

まとめ

本記事では、全要素が0の配列から「インクリメント」と「倍加」の2操作のみを使って目標配列を作る際の最小ステップ数を求める方法を紹介しました。ポイントは、ターゲット側からゼロ側へ逆算する発想です。奇数を偶数に整え→全体を半分に→残った1を消す、という流れで処理することで、無駄のない最少手順を効率よく導き出せます。同様の「逆から考える」テクニックは、操作が可逆な多くの最短手数問題に応用できるので、ぜひ覚えておきましょう。