C++で数値Kを0未満に減らすために必要な操作回数を求める方法

問題概要

正整数Kと、整数を含む配列Ops[]が与えられます。この記事の目的は、Kが0未満になるまで減らすために必要な操作回数を求めることです。操作の手順は以下の通りです。

• 最初の操作は「K + Ops[0]」。つまり、配列の先頭要素をKに加算します。
• その後、K < 0 になるまで Ops[i] をKに加算し続けます。インデックスiは循環的に変化し、0 ≤ i < N(NはOps[]の要素数)です。

注意: K < 0 になるまで Ops[i] を加算し続けます。iが最後の要素 Ops[N-1] に達した場合は、再び i=0 からやり直します(循環方式)。

解き方のポイント

まず、配列Ops[]の全要素の合計が0以上かどうかを確認します。合計が正である場合、どれだけ操作を繰り返してもKは減らせないため、-1を返します。そうでなければ、Ops[i] を順番にKへ加算しながら、K < 0 になったかどうかを判定し、条件を満たした時点でループを抜けます。

加算を行うたびに、操作回数のカウントを1ずつ増やしていきます。

例で理解しよう

入力:

ops[]= { -4,2,-3,0,2 }, K=5

出力: 数値を減らすために必要な操作回数 ― 3

説明: Kは5です。操作は以下のように進みます。

1. K+ops[0]= 5+(-4) = 1
2. K+ops[1]= 1+2 = 3
3. K+ops[2]= 3+(-3) = 0

入力:

ops[]= { 5,5,3,-2 }, K=10

出力: Kは減らせません!!

説明: Kは10です。操作は以下のように進みます。

1. K+ops[0]= 10+5= 15
2. K+ops[1]= 15+5= 20
3. K+ops[2]= 20+3= 23
4. K+ops[3]= 23+-2= 22
5. K+ops[0]= 22+5= 27
6. K+ops[1]= 27+5=32
7. …………

事前にops[]の全要素の合計を計算すると、5+5+3-2=11 となり、11+10 は常に正の値になります。したがって、Kを0未満に減らすことはできません。

プログラムで使用しているアプローチ

• ランダムな整数で初期化された整数配列ops[]を用意します。
• 変数Kには正の値を設定します。
• 関数 countOperations(int op[], int n, int k) は、配列Ops[]とその長さを引数として受け取り、Kを0未満に減らすのに必要な操作回数を返します。
• 操作回数の初期値として、count に 0 を設定します。
• ops[]の要素の合計を計算して sum に格納します。sum ≥ 0 の場合は -1 を返します。
• そうでなければ、k > 0 の間、ops[i] を加算しながら count を増やしていきます。k < 0 になったらループを抜けます。
• 最後に結果として count を返します。

コード例

#include <bits/stdc++.h>
using namespace std;
long countOperations(int op[], int n, int k){
    long count = 0;
    int sum=0;
    int i=0;
    for(int i=0;i<n;i++){
        sum+=op[i];
    }
    if(sum-k>=0)
        { return -1; } // sum-kが常に正または0のため、kは減らせない
    while(k>0){
        for(i=0;i<n;i++){
            if(k>0){
                count++;
                k+=op[i];
            }
            else
                { break; }
        }
    }
    return count;
}
int main(){
    int Ops[] = { 1,-1,5,-11};
    int len= sizeof(Ops) / sizeof(Ops[0]);
    int K=10;
    long ans=countOperations(Ops,len,K);
    if(ans==-1)
        { cout<<"K cannot be reduced!!"; }
    else
        { cout<<"Number of operations : "<<ans; }
    return 0;
}

出力

上記のコードを実行すると、以下の出力が得られます。

Number of operations : 8