【AtCoder】ABC 352 D - Permutation Subsequence | 茶コーダーが解くAtCoder

atcoder.jp

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 714

問題概要

の順列 が与えられる。長さ の正整数列 であって、以下の条件を満たすものを「良い添字列」と定義する。すべての添字列における の最小値を求めよ。

定義 :

• を満たす。
• 数列 はある連続する 個の整数の順列である。

制約

• 入力はすべて整数。
• 

考察

サンプルケース3を例に考察を進めてみよう。

まず、 は連続する 個の整数列になる必要があるので、考えやすいように配列 に「 となるような 」を格納しよう。すると、 の中身はそれぞれ下図のようになる。

は をindexに、 を値としている感じ。

ここで、問題文中の を から まで増やしたとき、 の値がどう変わるかを見ていくと、下図のようになる。

赤が最大要素、青が最小要素を示す。

を進めるごとに の中での探索範囲が右に一つずつずれていっていることが分かる。そして、 の値は探索範囲内の要素の集合を として、 となっている。

つまり、求めるべき値は の最小値である。

これを高速に求めるにはどうしたらよいであろうか。上の二つの図を見比べると、 を一つ進めるごとに の中から要素 が追い出され、新たに が追加されて を構成していることに気付くはずだ。したがって、「配列の要素の削除・追加」と「配列内の最大値・最小値の取得」を高速 (できれば定数時間) で行えるデータ構造が欲しい。これを実現するには、 C++ ではsetが適当だろう。

setでは、ポインタを用いることで配列内の最大値・最小値の取得を で行える。

ここまで分かれば、あとは を全探索していけばよい。具体的なアルゴリズムはコード例の通り。

コード

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

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

template <typename T>
inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }

// ======================================== //

int main()
{
    int N, K;
    cin >> N >> K;
    vector<int> v(N);
    rep(i, 0, N)
    {
        int P;
        cin >> P;
        P--;
        v[P] = i;
    }

    set<int> st;
    rep(i, 0, K) st.insert(v[i]);

    int ans = *st.rbegin() - *st.begin();
    rep(i, 0, N - K)
    {
        st.erase(v[i]);
        st.insert(v[i + K]);
        chmin(ans, *st.rbegin() - *st.begin());
    }

    cout << ans << endl;
}

atcoder.jp

実装時間: 40分

別解 : Segment Tree を利用する

上述の考察内では、「ある区間内の最大値・最小値」を求めることが最終的な目標となった。区間に関するクエリを処理するのに有効なデータ構造として、 Segment Tree というものがある。このデータ構造は C++ の標準ライブラリにはないのだが、実は AtCoder Library には用意されている。

github.com

別解として、これを使ったコードも載せておく。アルゴリズムとしては、最大値と最小値を求める用の Segment Tree をそれぞれ用意しておき、全探索によって両者の差の最小値を求めるというものである。

#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

constexpr auto INF = 1e+9;

template <typename T>
inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }

// ======================================== //

int op_min(int a, int b) { return min(a, b); }
int e_min() { return INF; }

int op_max(int a, int b) { return max(a, b); }
int e_max() { return 0; }

int main()
{
    int N, K;
    cin >> N >> K;
    segtree<int, op_min, e_min> segMin(N);
    segtree<int, op_max, e_max> segMax(N);
    rep(i, 0, N)
    {
        int P;
        cin >> P;
        segMin.set(P - 1, i);
        segMax.set(P - 1, i);
    }

    int ans = INF;
    rep(i, 0, N - K + 1)
    {
        int min = segMin.prod(i, i + K);
        int max = segMax.prod(i, i + K);
        chmin(ans, max - min);
    }
    cout << ans << endl;
}

atcoder.jp

Segment Tree に関してはまだまだ勉強不足感が否めない。