この問題に似てた

問題概要

$1, 2, \dots, M$ の順列 $p$ を最適化したい。以下の手順にしたがって、各要素 $i = 1, 2, \dots, M$ のスコアが定まる。この $M$ 個のスコアの最大値の最小値を求めよ。

値が $1, 2, \dots, M$ のいずれかであるような数列 $a_{1}, a_{2}, \dots, a_{N}$ ( $N$ 項) が与えられる
に対して、順列中の、であるようなに対して
- $l \lt r$ ならば、要素 $p_{l}, p_{l+1}, \dots, p_{r-1}$ のスコアを 1 加算する
- $l \gt r$ ならば、要素 $p_{r+1}, p_{r+2}, \dots, p_{l}$ のスコアを 1 加算する
最後に $p_{l} = a_{N}$ であるような $l$ に対して $p_{l}$ のスコアを 1 加算する

制約

$1 \le N \le 10^{5}$
$1 \le M \le 20$

考えたこと

まず $N$ が大きいのは完全にどうでもよい。なぜなら操作の順序はどうでもいいので、

num[ i ][ j ] := 要素 i と要素 j に関するクエリの個数

という風にしてしまえば、 $O(M^{2})$ 回の処理を考えればよくなるからだ。

さて、順列を最適化する問題なので、第一感では bitDP を考えたくなる。そして実際に bitDP で解くことができる。

dp[ bit ] := $1, 2, \dots, M$ のうち、bit で表される要素のみを先に並べてしまったときに、その内部におけるスコアの最大値の最小値

とすれば OK。これを効率よく更新するために、前処理として以下の値を求めておく。

score[ bit ][ v ] := bit で表される要素がすでに並んでいる状態で、その直後に要素 v を並べたときの要素 v のスコア

注意したいことは、この値が (bit, v) の組のみに依存するということだ。むしろその構造を見抜くことがこの問題のポイントだと言えそう。この score を前処理しておけば、

chmin(dp[ bit | (1 << v) ], max(dp[ bit ], score[ bit ][ v ])

という遷移によって DP できる。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const int INF = 1<<29;
int main() {
    int N, M;
    cin >> N >> M;
    vector<int> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i], --a[i];
    vector<vector<int>> num(M, vector<int>(M, 0));
    for (int i = 0; i + 1 < N; ++i) num[a[i]][a[i+1]]++;

    // 前処理
    vector<vector<int>> score(1<<M, vector<int>(M, INF));
    for (int bit = 0; bit < (1<<M); ++bit) {
        int base = 0;
        for (int j = 0; j < M; ++j) {
            if (!(bit & (1<<j))) continue;
            for (int k = 0; k < M; ++k) {
                if (bit & (1<<k)) continue;
                base += num[j][k] + num[k][j];
            }
        }
        for (int v = 0; v < M; ++v) {
            if (bit & (1<<v)) continue;
            int add = 0, sub = 0;
            for (int j = 0; j < M; ++j) {
                if (!(bit & (1<<j))) continue;
                sub += num[j][v]; // [j, v) は除外
            }
            for (int k = 0; k < M; ++k) {
                if ((bit & (1<<k))) continue;
                if (k == v) continue;
                add += num[v][k]; // [v, k) は追加
            }
            score[bit][v] = base + add - sub + (v == a.back());
        }
    }

    // bitDP
    vector<int> dp(1<<M, INF);
    dp[0] = 0;
    for (int bit = 0; bit < (1<<M); ++bit) {
        for (int v = 0; v < M; ++v) {
            if (bit & (1<<v)) continue;
            int nbit = bit | (1<<v);
            chmin(dp[nbit], max(dp[bit], score[bit][v]));
        }
    }
    cout << dp[(1<<M) - 1] << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 3191 Watering (AUPC 2020 day3-G)

問題概要

制約

考えたこと