C++で解く「回転関数（Rotate Function）」問題 ― 漸化式でO(n)高速化する方法

問題の概要

長さ n の整数配列 A が与えられます。B_k を「配列 A を時計回りに k 個分回転させた配列」とするとき、回転関数 F(k) は次のように定義されます。

F(k) = 0 × Bk[0] + 1 × Bk[1] + … + (n−1) × Bk[n−1]

このとき、F(0)、F(1)、…、F(n−1) の中から最大値を求めるのが本問題の目的です。

具体例：A = [4, 3, 2, 6] の場合

回転ごとの値は以下のように計算できます。

• F(0) = (0×4) + (1×3) + (2×2) + (3×6) = 0 + 3 + 4 + 18 = 25
• F(1) = (0×6) + (1×4) + (2×3) + (3×2) = 0 + 4 + 6 + 6 = 16
• F(2) = (0×2) + (1×6) + (2×4) + (3×3) = 0 + 6 + 8 + 9 = 23
• F(3) = (0×3) + (1×2) + (2×6) + (3×4) = 0 + 2 + 12 + 12 = 26

したがって、この入力に対する答えは最大値の 26 となります。

効率的なアプローチ：漸化式を使った O(n) 解法

すべての k について F(k) を個別に計算する素朴な方法では、計算量が O(n²) となり、配列が大きい場合には非効率です。ここで鍵となるのは、隣り合う F(k) 同士の関係に着目することです。

配列を1回転させるたびに、各要素の係数は1ずつ増加します。ただし末尾の要素だけは先頭へ移動するため、係数が (n−1) から 0 へと大きく減少します。この差分を整理すると、次の漸化式が成り立ちます。

F(k) = F(k−1) + sum(A) − n × A[n−k]

sum(A) は配列全体の総和です。この式により、F(0) から順に各値を定数時間で更新できるため、全体の計算量は O(n)、追加メモリも O(1) で済みます。

アルゴリズムの手順

• n を配列 A のサイズとし、n が 0 なら 0 を返す
• 1回の走査で総和 sum と初期値 F(0) = Σ i×A[i] を求める
• k = 1 から n−1 まで、漸化式 F(k) = F(k−1) + sum − n×A[n−k] で値を更新しながら最大値を記録する
• 記録した最大値を返す

C++での実装例

以下は上記の考え方を実装したコードです。オーバーフローを防ぐため、64ビット整数型 long long を使用しています。

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
    int maxRotateFunction(vector<int>& A) {
        lli n = A.size();
        if(n == 0) return 0;

        lli sum = 0;  // 配列の総和
        lli f = 0;    // 初期値 F(0)
        for(lli i = 0; i < n; i++){
            sum += A[i];
            f += i * A[i];
        }

        lli ret = f;
        for(lli k = 1; k < n; k++){
            f += sum - n * A[n - k];  // 漸化式で F(k) を更新
            ret = max(ret, f);
        }
        return ret;
    }
};
int main(){
    Solution ob;
    vector<int> v = {4, 3, 2, 6};
    cout << ob.maxRotateFunction(v);
}

実行結果

入力：

[4,3,2,6]

出力：

26

計算量

• 時間計算量：O(n) ― 配列を2回走査するだけ
• 空間計算量：O(1) ― 定数個の変数のみを使用

このように漸化式を活用することで、O(n²) の素朴な解法を O(n) まで高速化でき、大きな入力でも効率的に最大値を求めることができます。