2023-07-29

AtCoder AGC 062 B - Split and Insert (橙色, 700 点)

opt さん、とよさんと一緒に解いた。楽しかった！

問題へのリンク

問題概要

数列 $1, 2, \dots, N$ に対して、最大 $K$ 回の操作を繰り返すことで順列 $P_{1}, P_{2}, \dots, P_{N}$ を作りたい。

$i$ 回目の操作では、値 $k$ ( $0$ 以上 $N$ 以下) を選ぶと、コスト $k C_{i}$ がかかる
値 $k$ を選んだとき、数列の末尾 $k$ を取り出して、順番を崩さずに残りの $N-k$ 個の隙間に挿入していく (挿入箇所が連続でなくてもよい)

所望の順列を作るための最小コストを求めよ。ただし、 $K$ 回の操作で作れない場合は -1 と出力せよ。

制約

$2 \le N \le 100$
$1 \le K \le 100$

考えたこと：判定問題から

まず判定問題から解くことにした。僕は当初は「順列 $P$ を色塗りして、同一色の部分は単調増加となるようにしたいとき、最小個数の色は何個か？」という問題の答えが、必要回数ではないかと予想した。

しかし、この予想は早々に裏切られることとなった。もしこの予想のまま突っ走っていたら......と思うと恐ろしい。

たとえば、 $P = (4, 3, 2, 1)$ は次のように作れる。

$(1, 2, 3, 4)$
→ $(3, 1, 4, 2)$ ( $k = 2$ )
→ $(4, 3, 2, 1)$ ( $k = 2$ )

というように 2 回でできる。実は同様に、 $N = 8$ の場合も $3$ 回でできることが言える。どうも、対数回数でできるようだ。

一般の場合に、必要回数を示すのは難しそうだと思った。問題のコストの構造が、線形なことに注目したいと opt さんが言った。これが天才だった。

コストを解釈する

たとえば、 $P = (8, 7, 6, 5, 4, 3, 2, 1)$ を作るとしよう。次のように 3 ステップで作れる。ここで、1, 2, 3, 4 には目印をつけている。

1 2 3 4 | 5 6 7 8
o o o o

5 1 6 2 | 7 3 8 4
  o   o     o   o

7 5 3 1 | 8 6 4 2
    o o       o o

8 7 6 5 | 4 3 2 1
          o o o o

この構造をよく見ると、最初の 1 回でグループ $(1, 2, 3, 4)$ とグループ $(5, 6, 7, 8)$ に分解したあとは

$(1, 2, 3, 4)$ について所望の順序にするためのコスト
$(5, 6, 7, 8)$ について所望の順序にするためのコスト

とに分けて別々に計算してから足しても、必要コストが等しくなることに気づく。これ、気づいた opt さんがすごい！！！

なので、次の DP ができる。

dp[i][l][r] ← 操作 $i$ 回目のときに、 $l$ 以上 $r$ 未満の値がこの順に並んでいると仮定して、それらを所望の順序にするために必要な最小コスト

計算量は $O(N^{4})$ となった。

コード

最初、メモ化再帰で書いて TLE して、for 文に書き直すとあっさり通った。

メモ化再帰で TLE した原因は、「不可能な場合は dp[i][l][r] の値が更新されないが、本当に未計算である場合と区別がつかない」状態になっていたことだった。

メモ化再帰で書く (240ms)

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

int main() {
    // 入力
    long long N, K;
    cin >> N >> K;
    vector<long long> C(K), P(N);
    for (int i = 0; i < K; ++i) cin >> C[i];
    for (int i = 0; i < N; ++i) {
        cin >> P[i];
        --P[i];
    }
    
    // l 以上 r 未満の数が順列 P において順番通りになっているかどうかを前処理
    vector issorted(N+1, vector(N+1, false));
    vector<int> invP(N);
    for (int i = 0; i < N; ++i) invP[P[i]] = i;
    for (int l = 0; l < N; ++l) {
        for (int r = l+1; r <= N; ++r) {
            bool ok = true;
            int prev = -1;
            for (int j = l; j < r; ++j) {
                if (invP[j] < prev) ok = false;
                prev = invP[j];
            }
            issorted[l][r] = ok;
        }
    }
    
    // 区間 DP
    vector dp(K+1, vector(N, vector(N+1, INF)));
    vector seen(K+1, vector(N, vector(N+1, false)));
    auto dfs = [&](auto self, int i, int l, int r) -> long long {
        // メモ
        if (seen[i][l][r]) return dp[i][l][r];
                    
        // 終端条件
        if (issorted[l][r] && i <= K) return 0;
        
        // 終了条件
        if (i >= K) return INF;
        
        // 何個ずつ分けるかを場合分け
        long long res = self(self, i+1, l, r); // 1 回パス
        for (int m = l+1; m < r; ++m) {
            long long add = C[i] * (r - m);
            long long left = self(self, i+1, l, m);
            long long right = self(self, i+1, m, r);
            chmin(res, left + right + add);
        }
        seen[i][l][r] = true;
        return dp[i][l][r] = res;
    };
    long long res = dfs(dfs, 0, 0, N);
    cout << (res < INF ? res : -1) << endl;
}

非再帰でも書く (42 ms)

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

int main() {
    // 入力
    long long N, K;
    cin >> N >> K;
    vector<long long> C(K), P(N);
    for (int i = 0; i < K; ++i) cin >> C[i];
    for (int i = 0; i < N; ++i) {
        cin >> P[i];
        --P[i];
    }
    
    // l 以上 r 未満の数が順列 P において順番通りになっているかどうかを前処理
    vector issorted(N+1, vector(N+1, false));
    vector<long long> invP(N);
    for (int i = 0; i < N; ++i) invP[P[i]] = i;
    for (int l = 0; l < N; ++l) {
        for (int r = l+1; r <= N; ++r) {
            bool ok = true;
            int prev = -1;
            for (int j = l; j < r; ++j) {
                if (invP[j] < prev) ok = false;
                prev = invP[j];
            }
            issorted[l][r] = ok;
        }
    }

    // 区間 DP
    vector dp(K+1, vector(N+1, vector(N+1, INF)));
    for (int i = K; i >= 0; --i) {
        for (int bet = 1; bet <= N; ++bet) {
            for (int l = 0; l + bet <= N; ++l) {
                int r = l + bet;
                if (issorted[l][r]) {
                    dp[i][l][r] = 0;
                    continue;
                }
                if (i == K) continue;
                
                chmin(dp[i][l][r], dp[i+1][l][r]);  // 1 回パス
                for (int mid = l + 1; mid < r; ++mid) {
                    chmin(dp[i][l][r]
                          , dp[i+1][l][mid] + dp[i+1][mid][r] + C[i]*(r-mid));
                }
            }
        }
    }
    cout << (dp[0][0][N] < INF ? dp[0][0][N] : -1) << endl;
}

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

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