C++で解く「電球スイッチャーIII」― マップと優先度付きキューによる効率的な解法

問題概要

部屋にn個の電球があり、1からnまでの番号が付けられて、左から右へ一列に並んでいます。最初はすべての電球が消えています。時刻k（kは0からn-1までの範囲）に、light[k]番目の電球を点灯させていきます。ある電球が青色に変わるのは、その電球が点灯しており、かつそれより左側にあるすべての電球も点灯している場合だけです。点灯しているすべての電球が青色になっている瞬間の数を求めるのが、この問題の目的です。

次の図のようなイメージです。

この例の出力は3となり、条件を満たすのは時刻1、2、4です。

解法のアプローチ

この問題は、マップと最小ヒープ（優先度付きキュー）を組み合わせることで効率的に解けます。手順は以下のとおりです。

• 答えを格納するretを0で初期化し、集合x、配列のサイズn、マップmを用意する。
• 最小ヒープベースの優先度付きキューpqを定義する。
• iを0からn-1までループする。
  • m[light[i]] := i とし、iをpqに挿入する。
• iを1からnまでループする。
  • m[i]をxに挿入する。
  • pqが空でなく、pqの先頭要素がxに含まれている間、pqから削除する。
  • pqが空、またはpqの先頭がi以上であればretに1を加算する（そうでなければ0）。
• 最後にretを返す。

なぜこの方法で正しく判定できるのか

マップmは「電球iが何番目の時刻（インデックス）で点灯するか」を記録しています。ヒープpqには、まだ点灯していない電球の点灯予定時刻が格納されており、先頭にはその最小値が来ます。i番目の電球を点灯させた直後に、すでに点灯済みの時刻をヒープから取り除くと、ヒープの先頭は「まだ消えている電球の中で最も早く点灯する時刻」を表します。この値が現在のi以上であれば、位置1〜iの電球だけが点灯していることになり、すべて青色になっていると判定できます。また、ヒープが空の場合は全電球が点灯済みなので、やはり条件を満たします。

C++による実装例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int numTimesAllBlue(vector<int>& light) {
        int ret = 0;
        set <int> x;
        int n = light.size();
        map <int, int> m;
        priority_queue <int, vector <int>, greater <int> > pq;
        for(int i = 0; i < n; i++){
            m[light[i]] = i;
            pq.push(i);
        }
        for(int i = 1; i <= n; i++){
            x.insert(m[i]);
            while(!pq.empty() && x.count(pq.top())) pq.pop();
            ret += (pq.empty() || (pq.top() >= i));
        }
        return ret;
    }
};
main(){
    vector<int> v = {2,1,3,5,4};
    Solution ob;
    cout << (ob.numTimesAllBlue(v));
}

入力

[2,1,3,5,4]

出力

3

計算量の目安

各要素は高々1回ずつヒープに挿入・削除されるため、時間計算量はO(n log n)、空間計算量はO(n)となります。

補足：もっとシンプルなO(n)解法

実は、これまでに点灯した電球の位置の最大値を追跡するだけで解くこともできます。時刻k（0始まり）に点灯した電球の位置の最大値がk+1と一致するとき、点灯中の電球はちょうど1〜k+1番目だけであり、すべて青色になっています。

int numTimesAllBlue(vector<int>& light) {
    int ret = 0, mx = 0;
    for (int i = 0; i < (int)light.size(); ++i) {
        mx = max(mx, light[i]);
        if (mx == i + 1) ++ret;
    }
    return ret;
}