問題

2612. 最小反転操作回数

整数 n と、範囲 [0, n - 1] 内の整数 p が与えられます。これらは、長さが n でインデックスが 0 から始まる配列 arr を表します。この配列では、インデックス p の位置だけが 1 で、他のすべての要素は 0 です。

同時に、整数配列 banned も与えられます。この配列には、配列内のいくつかの位置が含まれています。banned の第 i 個の位置は、arr[banned[i]] = 0 を意味します。問題では、banned[i] != p であることが保証されています。

配列 arr に対して、いくつかの操作を実行できます。1つの操作では、サイズ k の 部分配列 を選択し、それを 反転 します。いかなる反転操作の後も、arr 内の唯一の 1 が banned に含まれる位置に到達しないようにする必要があります。言い換えれば、arr[banned[i]] は常に 0 のままにする必要があります。

配列 ans を返してください。これは、[0, n - 1] の任意のインデックス i に対して、ans[i] が位置 i に 1 を配置するための 最小 反転操作回数であり、位置 i に配置できない場合は -1 となります。

• 部分配列 とは、配列内の連続した 非空 の要素のシーケンスを指します。
• すべての i に対して、ans[i] は独立して計算されます。
• 配列の要素を 反転 するとは、配列の値を 逆順 にすることを指します。

**例 1：**

入力：n = 4, p = 0, banned = [1,2], k = 4
出力：[0,-1,-1,1]
解説：k = 4 なので、実行可能な反転操作は配列全体を反転する1つだけです。1は最初に位置 0 にあるため、位置 0 に配置するための操作回数は 0 です。
banned にある位置に 1 を反転させることができないため、位置 1 と 2 の答えは -1 です。
1回の反転操作で、1を位置 3 に配置できます。したがって、位置 3 の答えは 1 です。

**例 2：**

入力：n = 5, p = 0, banned = [2,4], k = 3
出力：[0,-1,-1,-1,-1]
解説：この例では 1 は最初に位置 0 にあるため、このインデックスの答えは 0 です。
反転する部分配列の長さは k = 3 です。1 は現在位置 0 にあるため、部分配列 [0, 2] を反転できますが、反転後のインデックス 2 は banned に含まれているため、この操作は実行できません。
1 が位置 0 から離れることができないため、他の位置の答えはすべて -1 です。

**例 3：**

入力：n = 4, p = 2, banned = [0,1,3], k = 1
出力：[-1,-1,0,-1]
解説：この例では、長さ 1 の部分配列に対してのみ反転操作を実行できます。したがって、1 は初期位置から離れることができません。

**ヒント：**

• 1 <= n <= 10^5
• 0 <= p <= n - 1
• 0 <= banned.length <= n - 1
• 0 <= banned[i] <= n - 1
• 1 <= k <= n
• banned[i] != p
• banned 内の値は 一意 です。

考え方

まず問題を理解しましょう。問題文は長いですが、ここでの 反転 は、要素の順序を逆にすることを意味します。初期状態では、配列に1つの値が1です。インデックス p にある1が、1回の反転操作で到達できる位置を考えてみましょう：

• もし p が部分配列の右端として機能する場合、反転後の最小値は p - k + 1 に到達できます。
• もし p が部分配列の左端として機能する場合、反転後の最大値は p + k - 1 に到達できます。

もちろん、上記は最も理想的な場合です。部分配列の長さが固定の k であるため、現在のノード p が部分配列の左端または右端として機能できない場合があります。この2つのケースについて、さらに分類して考察します：

• もし p < k - 1 の場合、p は部分配列の右端として機能できません。p を最も左の部分配列 [0, k-1] に移動させることができます。このとき、p が移動する位置は k - 1 - p です。
• もし p > n - k の場合、p は部分配列の左端として機能できません。p を最も右の部分配列 [n-k, n-1] に移動させることができます。このとき、p が移動する位置は 2 * n - p - 1 - k です。

これで、p が1回の反転操作で到達できる位置の範囲を取得しました。ここで注意すべき点は、範囲内のすべての位置が到達可能であるわけではないことです。実際、部分配列をスライドさせる場合、部分配列を1つスライドさせるごとに、p の反転後の位置は2ずつ移動します。

また、banされた位置を除外する必要があります。これらの位置は永遠に到達できません。

1回の移動で到達できるすべての位置を知ったので、BFS（幅優先探索）の考え方を使って、前回到達した新しい位置に対してさらに探索を続けることができます。ここで重要なのは、毎回新しく到達した位置のみを探索し、以前に到達した位置は、再び到達しても、より少ない反転回数で到達したことが確定しているため、スキップすることです。

#### 最適化

提出したところ、TLE（Time Limit Exceeded）が発生しました。

問題の原因を分析すると、毎回の探索で [min, max] の間のすべての位置を2ずつスキップして探索しているためです。もし k が大きい場合、この間の位置は非常に多くなります。banされた位置や以前に到達した位置はスキップする必要はありませんが、それでも大きな無駄が発生します。可能な値を [min, max] の間からのみ正確に探索するのが最善です。

各 [min, max] の間で到達できる位置の内部では、奇数と偶数が一貫しています（2つの [min, max] の間では奇数と偶数が異なる場合があります）。したがって、未到達の位置を、奇数と偶数で分けて2つの TreeSet に格納し、TreeSet から [min, max] の可能な値を取得することができます。

#### 最適化後のコード

import java.util.*;

public class Solution {
    public int[] minReverseOperations(int n, int p, int[] banned, int k) {
        // 禁止された位置をセットに格納
        Set<Integer> bannedSet = new HashSet<>();
        for (int ban : banned) {
            bannedSet.add(ban);
        }

        // 未到達の位置を、奇数と偶数で分けて管理
        // 幅優先探索では、到達できる位置はすべて奇数または偶数になる
        TreeSet<Integer>[] oddEvenSets = new TreeSet[]{new TreeSet<>(), new TreeSet<>()};
        for (int i = 0; i < n; i++) {
            if (bannedSet.contains(i) || i == p) {
                continue;
            }
            oddEvenSets[i & 1].add(i);
        }

        int[] results = new int[n];
        Arrays.fill(results, -1);
        results[p] = 0;

        // 幅優先探索のキュー
        Queue<Integer> queue = new LinkedList<>();
        queue.add(p);

        while (!queue.isEmpty()) {
            int currentPos = queue.poll();
            
            // 現在の位置から反転できる範囲を計算
            int minPos, maxPos;
            if (currentPos < k - 1) {
                minPos = k - 1 - currentPos;
            } else {
                minPos = currentPos - k + 1;
            }
            if (currentPos > n - k) {
                maxPos = 2 * n - k - 1 - currentPos;
            } else {
                maxPos = currentPos + k - 1;
            }

            // 現在の位置と同じ奇偶性を持つ到達可能なセットを選択
            TreeSet<Integer> reachableSet = oddEvenSets[minPos & 1];
            Iterator<Integer> iterator = reachableSet.tailSet(minPos).iterator();

            while (iterator.hasNext()) {
                int nextPos = iterator.next();
                if (nextPos > maxPos) {
                    break;
                }
                // 結果を更新し、キューに追加
                results[nextPos] = results[currentPos] + 1;
                queue.add(nextPos);
                // 到達した位置はセットから削除
                iterator.remove();
            }
        }
        return results;
    }
}

#### 実行時間