C++で解く「石を動かして連続配置にする II」― 移動回数の最小値と最大値を求める

問題概要

無限に続く数直線を考えます。i 番目の石の位置は配列 stones で与えられ、stones[i] が i 番目の石の座標を表します。最も小さい位置、または最も大きい位置にある石を「端点の石」と呼びます。各ターンでは、端点の石を1つ選び、それ以上端点にならないように、まだ占有されていない空き位置へ移動させます。

例えば stones = [1,2,5] の場合、位置 5 にある端点の石は動かせません。0 や 3 など、どの空き位置に置いてもその石は再び端点になってしまうためです。

この操作を繰り返し、すべての石が連続した位置に並んでこれ以上手が打てなくなった時点で、ゲームは終了します。

求めたいのは、ゲーム終了までに行われる移動回数の最小値と最大値です。答えは [min_moves, max_moves] のペアとして返します。

例えば入力が [7,3,9] なら、出力は [1,3] となります。

解法のアプローチ

以下の手順でこの問題を解いていきます。

• サイズ2の配列 ans を用意する。

• ans[0] に無限大、ans[1] に−無限大、n に配列 a の要素数を代入する。

• 配列 a を昇順にソートする。

• x := 1 とし、x < n かつ a[x] − a[x−1] = 1 である間 x を増加させる（先頭から何個の石が連続しているかを調べる）。

• x == n なら、すべての石が既に連続しているため {0, 0} を返す。

• minVal := 0、j := 1 と初期化する。

• i を 0 から順に走査し、各 i について次の処理を行う。

  • curr := a[i]、lastPossible := a[i] + n − 1 とする。

  • lastPossible > a[n−1] ならループを抜ける。

  • spaceInBetween := false とする（窓の中に隙間があるかどうかを示すフラグ）。

  • j <= i なら j := i + 1 に更新する。

  • j < n かつ a[j] <= lastPossible の間、隣接する石の間隔が1より大きければ spaceInBetween := true とし、j を1ずつ進める。

  • idx := j − 1 とする。

  • 窓の外に2個以上の石が残る場合（n − (idx − i + 1) > 1）も spaceInBetween := true とする。

  • ballLeft := i、ballRight := n − (idx + 1) とし、minVal = ballLeft + ballRight + (spaceInBetween ? 0 : 1) を計算する。

  • ans[0] = min(ans[0], minVal) で最小移動回数を更新する。

• ans[1] = max(a[n−2] − a[0], a[n−1] − a[1]) − (n − 2) として最大移動回数を求める。

• ans を返す。main 関数からは solve(stones) を呼び出します。

ポイント解説

最小移動回数は、長さ n の「窓」を数直線上でスライドさせ、窓内に収まる石の数が最大になる位置を探すことで求められます。窓の外に残った石を窓内の空きマスへ1つずつ移す回数が基本となり、窓内に隙間がない場合はさらに1手余分に必要になります。

最大移動回数は、「どちらか一方の端の石のみを固定し、残りの n−2 個の石をすべて詰め直す」戦略で達成できます。これが max(a[n−2] − a[0], a[n−1] − a[1]) − (n − 2) という式に対応します。

C++ 実装例

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class Solution {
    public:
    vector<int> solve(vector<int> a) {
        vector <int> ans(2);
        ans[0] = INT_MAX;
        ans[1] = INT_MIN;
        int n = a.size();
        sort(a.begin(), a.end());
        int x = 1;
        while(x < n && a[x] - a[x - 1] == 1)
            x ++;
        if(x == n){
            return {0,0};
        }
        int minVal = 0;
        int j = 1;
        for(int i = 0; i < a.size(); i++){
            int curr = a[i];
            int lastPossible = a[i] + n - 1;
            if(lastPossible > a[n - 1])
                break;
            bool spaceInBetween = false;
            if(j <= i)
                j = i + 1;
                while(j < n && a[j] <= lastPossible){
                    if((a[j] - a[j - 1]) > 1) {
                        spaceInBetween = true;
                    }
                    j++;
                }
                int idx = j - 1;
                if(n - (idx - i + 1) > 1)
                    spaceInBetween = true;
                int ballLeft = i;
                int ballRight = n - (idx + 1);
                minVal = ballLeft + ballRight + (spaceInBetween? 0 : 1);
                ans[0] = min(minVal, ans[0]);
        }
        ans[1] = max(a[n - 2] - a[0], a[n - 1] - a[1]) - (n -2);
        return ans;
    }
    vector<int> numMovesStonesII(vector<int>& stones) {
        return solve(stones);
    }
};
main(){
    Solution ob;
    vector<int> v1 = {7,3,9};
    print_vector(ob.numMovesStonesII(v1));
}

入力

[7,3,9]

出力

[1, 3]