**問題リンク**

解析

---

操作1の性質

最小値が配列の末尾に存在する場合、その値は他の数を更新することができないため、削除されることになる。一方、最小値が末尾以外に存在する場合は、必ずその右側にある更大的な値によって更新される。

したがって、操作1を適用すると、最小値は必ず更新（または削除）される。

---

操作2の性質

同様の考察から、操作2を適用すると、最大値は必ず更新（または削除）される。

---

貪欲戦略の導出

以上の性質から、以下の貪欲戦略が成立する：

• 操作1をm回先行して実行する
• その後、操作2をn-m-1回実行する

操作1をm回実行した後の配列に対してのみ操作2を適用する場合、最終的に残るのは残った数の最小値となる。

---

計算量の分析

操作1を素直にm回実行する場合、時間計算量はO(NM)となり、部分点（40点）の取得にとどまる。しかし、この処理はもっと効率的に実装できる。

---

操作1の最適化

m回の操作1を通じて、位置iの要素はa_{i+1}, a_{i+2}, ..., a_{i+m}の影響を受けなくなる。言い換えると、操作1の適用後、位置iの値は区間[i+1, i+m]内の最大值になる。

この問題は「各要素について、右隣m個の要素の最大值を求める」と言い換えられる。これには優先キュー（モノトンキュー）を用いてO(N)で解決できる。

---

実装コード

部分点解法（40点）

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;
int n, m;
vector<int> data;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> m;
    data.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> data[i];
    }
    
    for (int step = 1; step <= m; step++) {
        for (int idx = 1; idx <= n - step; idx++) {
            data[idx] = max(data[idx], data[idx + 1]);
        }
    }
    
    int result = INT_MAX;
    for (int i = 1; i <= n - m; i++) {
        result = min(result, data[i]);
    }
    
    cout << result << '\n';
    return 0;
}

満点解法（100点）

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;
int n, m;
vector<int> input_data;
vector<int> result_data;
deque<int> dq;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> m;
    input_data.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> input_data[i];
    }
    
    for (int i = 1; i <= n; i++) {
        if (!dq.empty() && i - dq.front() > m) {
            dq.pop_front();
        }
        while (!dq.empty() && input_data[dq.back()] < input_data[i]) {
            dq.pop_back();
        }
        dq.push_back(i);
        if (i >= m + 1) {
            result_data[i - m] = input_data[dq.front()];
        }
    }
    
    int answer = INT_MAX;
    for (int i = 1; i <= n - m; i++) {
        answer = min(answer, result_data[i]);
    }
    
    cout << answer << '\n';
    return 0;
}

---

計算量の比較

解法	時間計算量	空間計算量
部分点解法	O(NM)	O(N)
満点解法	O(N)	O(N)

満点解法のポイント

モノトンキューの deque を活用し、スライディングウィンドウ形式で最大值を管理することで、操作1のm回の処理全体をO(N)に最適化する。各位置iに対して、区間(i, i+m]の最大值即时的に取得可能となる。