C++で解く「K Empty Slots（空きスロット）」問題

問題概要

1からNまでの番号が付けられたN個の電球が一列に並んでおり、最初はすべて消えています。毎日ちょうど1個の電球を点灯させ、N日後にはすべての電球が点灯状態になるとします。長さNの配列 bulbs が与えられ、bulbs[i] = x は「(i+1) 日目に位置 x の電球を点灯させる」ことを表します。さらに整数 K が与えられたとき、「点灯している2つの電球の間に、消えたままの電球がちょうど K 個挟まれている」という状況が初めて成立する日の番号（最小値）を求めます。そのような日が存在しない場合は -1 を返してください。

例として、入力が bulbs = [1,3,2]、K = 1 の場合を考えてみましょう。このとき出力は 2 になります。その理由は以下の通りです。

• 1日目：bulbs[0] = 1 により、1番目の電球が点灯 → [1,0,0]

• 2日目：bulbs[1] = 3 により、3番目の電球が点灯 → [1,0,1]

• 3日目：bulbs[2] = 2 により、2番目の電球が点灯 → [1,1,1]

2日目の時点で、点灯している2つの電球（1番目と3番目）の間に、消えている電球がちょうど1個存在するため、答えは 2 となります。

解法の考え方（スライディングウィンドウ）

この問題は、スライディングウィンドウ（尺取り法）の発想を使うことで効率よく解けます。まず、各位置の電球が「何日目に点灯するか」を記録した配列 days を作成します。days[pos] には、位置 pos+1 の電球が点灯する日が格納されます。

次に、間にちょうど K 個の電球を挟む2つの位置 left と right（right = left + K + 1）に注目し、ウィンドウを右へずらしていきます。両端の間にある電球がすべて「両端よりも遅く」点灯するならば、max(days[left], days[right]) 日目に「点灯している2つの電球の間に消えた電球がちょうど K 個ある」という条件が成立します。条件を満たす候補の中で最小の日数を求めればよいのです。

アルゴリズムの手順

• n := bulbs のサイズとする

• i := 0 から n-1 まで、各 i について days[bulbs[i] - 1] = i + 1 を設定する

• left := 0、right := K + 1、ret := 無限大（INT_MAX）で初期化する

• right < n の間、i を 1 ずつ増やしながら次を繰り返す：

  • days[i] < days[left] または days[i] <= days[right] の場合：

    • i == right であれば、ret := min(ret, max(days[left], days[right])) として答えを更新する

    • left := i、right := i + K + 1 としてウィンドウを張り直す

• 最後に、ret が依然として無限大であれば -1 を、そうでなければ ret を返す

この手法では各位置を高々一度ずつ調べるだけでよく、時間計算量は O(N)、追加で必要なメモリも O(N) に抑えられます。

C++での実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int kEmptySlots(vector<int>& bulbs, int k) {
        int n = bulbs.size();
        vector<int> days(n);
        for (int i = 0; i < n; i++) {
            days[bulbs[i] - 1] = i + 1;
        }
        int left = 0;
        int right = k + 1;
        int ret = INT_MAX;
        for (int i = 0; right < n; i++) {
            if (days[i] < days[left] || days[i] <= days[right]) {
                if (i == right) {
                    ret = min(ret, max(days[left], days[right]));
                }
                left = i;
                right = i + k + 1;
            }
        }
        return ret == INT_MAX ? -1 : ret;
    }
};
main(){
    Solution ob;
    vector<int> v = {1,3,2};
    cout << (ob.kEmptySlots(v, 1));
}

入力

{1,3,2},

出力

2