C++で最高スコアを得る最小の回転量Kを求める方法

問題の概要

配列 A が与えられたとします。この配列を K だけ回転すると、配列は A[K], A[K+1], …, A[A.length−1], A[0], A[1], …, A[K−1] の順に並び替えられます。そして、回転後の配列において「値がそのインデックス以下である要素」に対して 1 点が与えられます。

例として、配列 [2, 4, 1, 3, 0] を K = 2 で回転すると [1, 3, 0, 2, 4] になります。このときの得点は次のように計算され、合計 3 点となります。

• 1 > 0 → 得点なし
• 3 > 1 → 得点なし
• 0 <= 2 → 1 点
• 2 <= 3 → 1 点
• 4 <= 4 → 1 点

この問題では、最も高い得点が得られる K を求めます。答えが複数存在する場合は、その中で最も小さい K を返します。

例えば、入力が [2, 3, 1, 5, 1] の場合、出力は 3 になります。各 K における配列と得点は以下の通りです。

K = 3 のときに最大の得点 4 が得られるため、答えは 3 となります。

解法のアプローチ（差分配列・いもす法）

すべての K について実際に回転を試して得点を数えると、計算量は O(n²) となり非効率です。そこで「各要素がどの K の範囲で得点を獲得できるか」に着目し、差分配列を使って O(n) で解きます。

要素 A[i] は、回転後に位置 (i − K + n) mod n へ移動します。この新しいインデックスが元の値 A[i] 以上になるときに 1 点を獲得できます。これを K の範囲で整理すると、次のようになります。

• A[i] <= i の場合：K ∈ [0, i − A[i]] または K ∈ [i + 1, n − 1] の範囲で得点を獲得
• A[i] > i の場合（ただし A[i] < n）：K ∈ [i + 1, i + (n − A[i])] の範囲で得点を獲得
• A[i] >= n の場合：どの K でも得点を獲得できないため無視

これらの区間を差分配列 cnt に記録し、最後に累積和を取ることで、各 K における合計得点を効率的に求められます。

アルゴリズムの手順

1. ret := 0、n := 配列 A のサイズとする
2. サイズ n の差分配列 cnt を定義する
3. i = 0 から n − 1 まで以下を繰り返す
   • A[i] <= i の場合：
     • minI := 0 として cnt[minI] を 1 増やす
     • maxI := i − A[i] とし、maxI + 1 < n なら cnt[maxI + 1] を 1 減らす
     • i + 1 < n なら cnt[i + 1] を 1 増やす
   • それ以外の場合：
     • A[i] >= n なら次の反復へスキップ
     • minI := i + 1 として cnt[minI] を 1 増やす
     • maxi := i + (n − A[i]) とし、maxi + 1 < n なら cnt[maxi + 1] を 1 減らす
4. maxCnt := −1、temp := 0 とする
5. i = 0 から n − 1 まで temp += cnt[i] と累積し、temp > maxCnt なら maxCnt := temp、ret := i を更新する
6. ret を返す

C++での実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int bestRotation(vector<int>& A) {
        int ret = 0;
        int n = A.size();
        vector<int> cnt(n);
        for(int i = 0; i < n; i++){
            if(A[i] <= i){
                int minI = 0;
                cnt[minI]++;
                int maxI = i - A[i];
                if(maxI + 1 < n) cnt[maxI + 1]--;
                if(i + 1 < n) cnt[i + 1]++;
            }else{
                if(A[i] >= n) continue;
                int minI = i + 1;
                cnt[minI]++;
                int maxi = i + (n - A[i]);
                if(maxi + 1 < n)cnt[maxi + 1]--;
            }
        }
        int maxCnt = -1;
        int temp = 0;
        for(int i = 0; i < n; i++){
            temp += cnt[i];
            if(temp > maxCnt){
                maxCnt = temp;
                ret = i;
            }
        }
        return ret;
    }
};
main(){
    Solution ob;
    vector<int> v = {2,3,1,5,1};
    cout << (ob.bestRotation(v));
}

入力

[2,3,1,5,1]

出力

3