InTheDayDream

ICPC国内予選2023 Problem E - Tampered Records（改竄された史料）

Published on 2025-04-09
Last Modified 2025-04-09

Table Of Contents

問題

以下 aoj1668 より引用

改竄された史料

太古の昔， International Collegiate Puzzle Contest (ICPC) というパズル大会が毎年開催されていた． 各大会は午前・午後の 2 つのラウンドで構成されていた． どちらのラウンドでも，参加者はまず自作のパズル 1 つを他の全参加者に提示し，その後に自分自身以外の全参加者が提示したパズルをできるだけ多く解こうとした．

参加者の順位は以下の規則に従って決めていた．

先日，ある年の ICPC の順位表とされる文書が発見された． 他の同様の資料から，この文書は各ラウンドで解いたパズルの数を上位の参加者から順に書き並べたものと考えられる． ところが学者たちは文書は何者かによって改竄されていて，いくつかの数が書き換えられているのではないかという疑いを持っている． もともとの順位表に上述の規則と矛盾がなかったと仮定したとき，少なくともいくつの数が書き換えられているのかを求めてほしい． なお，文書中の解いたパズルの数以外の部分への改竄はなく，参加者の追加や削除もありえない．

ICPCの参加者$n$はひとつのテストケースで$n \leq 6000$となる。含まれるテストケースはひとつのファイルで高々100であり、$n$の合計は$10 ^ 5$を超えない。

問題の言いかえ

問題を競プロ風に言い換える。 $n \leq 6000$個の数のペア$(x _ i, y _ i)$が与えられる。 二つのペア$(x _ i, y _ i), (x _ j, y _ j)$に対して、

であるとする。 任意に数を書き換えることで次の条件が成立するようにする。

書き換える必要のある数の最小値はいくつか？

考察

解法の概要

貪欲法ベースの「最適な決め方」みたいなものはなくて、全探索をベースにするしかない。端から確定させるとすると、一番最後が何だったか以外の情報を捨ててよいため、dpが出来そう。

率直にやると$\mathrm{dp}[i][j][k]$を先頭$i$項を処理して最後が$(j, k)$になる最小の変更回数となりそう。これは遷移先を良い感じに枝狩りしても$\Omega(N ^ 3)$とか。

$\mathrm{dp}[i][x][y] = \mathrm{dp}[i][p][q]$だったとしたら、$(x, y)$と$(p, q)$のうちより小さい方だけ保持しておけばよい。（より大きな方から遷移しても明らかに最適解になりえない。） 添字の入れ替えテクを用いて、同じコストを実現するもののうち、末尾のペアが最小になるものだけを残すようにする。

$\mathrm{dp}[i][j]$は先頭$i$項を処理してコストが$j$となる物のうち、最小の末尾ペアとなる。この時点で$\Omega(N ^ 2)$。配る遷移を考察すると$O(1)$個しかないので、$O(N ^ 2)$となる。（よくあるもらう形式にしてデータ構造でなんとかするみたいなことは無理そうなので無難に配った方がいい。）

実装例

AC提出 

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

constexpr int iINF = 1'000'000'000;

int cmp (const pair<int, int>& x, const pair<int, int>& y) {
    if (x.second == y.second) {
        if (x.first == y.first) return 0;
        return x.first < y.first ? -1 : 1;
    }
    return x.second < y.second ? -1 : 1;
}

int main () {
    while (true) {
        int n; cin >> n;
        if (n == 0) break;

        vector<int> x(n), y(n);
        for (int i = 0; i < n; i++) {
            cin >> x[i] >> y[i];
        }

        // dp[i][j] := 昇順にi個処理して、変更j回をしたとき、作れる最も小さいスコア
        vector<pair<int, int>> dp(n + 1), ndp(n + 1);
        for (int i = 0; i < n + 1; i++) {
            dp[i] = make_pair(iINF, iINF);
        }
        dp[0] = make_pair(0, 0);

        for (int i = n - 1; 0 <= i; i--) {
            for (int j = 0; j < n + 1; j++) {
                ndp[j] = make_pair(iINF, iINF);
            }

            for (int j = 0; j < n + 1; j++) {
                if (dp[j] == make_pair(iINF, iINF)) continue;

                auto cur = make_pair(x[i], y[i]);
                // 変更0回
                if (cmp(dp[j], cur) <= 0) {
                    if (cmp(cur, ndp[j]) <= 0) {
                        ndp[j] = cur;
                    }
                }

                if (j == n) continue;
                // 変更1回
                // どちらを変更するかで分ける。

                // 午前の部
                if (x[i] != 0
                        && cmp(dp[j], make_pair(0, y[i])) <= 0
                        && cmp(make_pair(0, y[i]), ndp[j + 1]) <= 0) {
                    ndp[j + 1] = make_pair(0, y[i]);
                }
                if (x[i] != dp[j].first
                        && cmp(dp[j], make_pair(dp[j].first, y[i])) <= 0
                        && cmp(make_pair(dp[j].first, y[i]), ndp[j + 1]) <= 0) {
                    ndp[j + 1] = make_pair(dp[j].first, y[i]);
                }

                // 午後の部
                if (y[i] != dp[j].second
                        && cmp(dp[j], make_pair(x[i], dp[j].second)) <= 0
                        && cmp(make_pair(x[i], dp[j].second), ndp[j + 1]) <= 0) {
                    ndp[j + 1] = make_pair(x[i], dp[j].second);
                }
                if (y[i] != dp[j].second + 1
                        && dp[j].second + 1 < n
                        && cmp(dp[j], make_pair(x[i], dp[j].second + 1)) <= 0
                        && cmp(make_pair(x[i], dp[j].second + 1), ndp[j + 1]) <= 0) {
                    ndp[j + 1] = make_pair(x[i], dp[j].second + 1);
                }

                if (j == n - 1) continue;
                // 変更2回
                // この場合は前とピッタリ合わせればok
                if (dp[j].first != x[i] && dp[j].second != y[i]) {
                    if (cmp(dp[j], ndp[j + 2]) <= 0) {
                        ndp[j + 2] = dp[j];
                    }
                }
            }

            swap(dp, ndp);
        }

        int ans = -1;
        for (int i = 0; i < n + 1; i++) {
            if (dp[i] != make_pair(iINF, iINF)) {
                ans = i;
                break;
            }
        }

        cout << ans << "\n";
    }
}

感想

ICPCに採用されるだけあって、かなり良い問題だと感じた。 dpの方針が見えるまで3日くらい。dpを詰めながら実装するのに2時間くらいかかった。疲れた。

実装が爆発してしまった。今思うとpair<int, int>はやめてoperator<=とかをオーバーロードすべきだったかも（chminみたいなことができるので。）

Tags for this post: 競技プログラミング 一問解説

Other posts tagged by "競技プログラミング"

more ...

Other posts tagged by "一問解説"

more ...
Power by Hugo / Theme simplog by michimani