こういう個数合わせ系の問題は実は得意かもしれない

問題へのリンク

問題概要

長さ $N$ の数列 $A_{1}, \dots, A_{N}$ が与えられる。これに対して $1, \dots, N$ の順列 $p_{1}, \dots, p_{N}$ であって、 $A_{p_{1}}, \dots, A_{p_{N}}$ のどの隣接する二項も同じ数値でないようなものを考える。

そのような順列 $p$ のうち、 $|p_{i} - p_{i+1}| = 1$ を満たさない $i$ の個数の最小値を求めよ。そのような順列が存在しない場合は -1 を出力せよ。

制約

$n$ の総和 $\le 10^{5}$

考えたこと

つまり、数列 $A$ を

いくつかの区間に分割して
そのうちのいくつかの区間については左右を reverse して
それを上手に並び替えて連結させる

ことによって「どの隣接二項も値が異なる」という条件を満たすようにする問題だと考えてよい。たとえば最後のサンプルは次のような感じ。

1 2 3 4 1 1 2 3 4 1
↓
|1 2|3 4 1|1 2 3 4 1|
↓
|1 2 3 4 1|3 4 1|2 1|

このとき、区間の個数を $K$ としたとき、そのスコアは $K-1$ となる。

順列が存在する条件

とりあえず順列が存在する条件を考える。最頻値が $(N+1)/2 + 1$ 個以上あるとき、鳩の巣原理から確実に隣接箇所が存在する。そうでなければ、その最頻値を 0 番目から交互にやることで大丈夫。

まずは同じ値が連続するところを切る

まずは同じ値が連続するところを切ることにする。これを上手く並び替えれば条件を満たせるなら話は早くて、それが答えとなる。しかし上手くいかない場合がある。たとえば

|1 2 3 1|1 2 3 1|1 2 1|1 2 1|1 2|2 1 2|

という場合がある。これはどのように reverse / 並び替えをしても条件を満たすようにできない。でも 2 箇所分割 (2 箇所分割できることは順列の存在から保証される) すれば上手くいく。具体的には

|1 2|1 3|1 2|1 3|1 2 1|2 1 2|1 2 1|2 1|

という風にすれば OK。冷静にもとの区間分割の両端の値を整理すると

(1, 1) が 4 個
(1, 2) が 1 個
(2, 2) が 1 個

という風になっている。(1, 2) などは何個あっても問題ない。(1, 1) のように両端が同じ値となっているものが多く含まれると厳しい。具体的には (x, x) が最も多いものが $a$ 個, (y, z) の形のものが $b$ 個 (y も z も x ではない) であるとき、

$a - b - 1$ 回の分割操作

を行う必要があることが言える (上の例の場合は $a = 4$ , $b = 1$ )。十分性については無証明で出したけど、これを必要十分として AC がとれた。

十分性の証明の方針 (editorial より)

先ほどの条件を言い換えると、次のように言える。任意の値 $x$ に対して、区間の両端 ( $2K$ 箇所ある) のうち、値 $x$ が占める箇所を $f(x)$ 箇所とすると、

$f(x) \le K + 1$

が成り立つことが必要十分条件だということになる。必要性は明らか。十分性は $K$ についての帰納法から示せる。

Codeforces Global Round 12 Editorial - Codeforces

提出前にテストしたケース

ちょっとコーナーケースの怖い問題だったので、以下のようなケースをテストした。

19
1 2 3 1 1 2 3 1 1 2 1 1 2 1 1 2 2 1 2
→ 7

23
1 2 3 1 1 2 3 1 1 2 3 1 1 2 1 1 2 1 1 2 2 1 2
→ 9

7
1 1 1 1 2 2 3
→ 5

コード

#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; 
}

int solve(int N, const vector<int> &A) {
    N = A.size();

    // 頻度が (N+1)/2+1 回以上はダメ
    {
        vector<int> hist(N, 0);
        for (auto c : A) hist[c]++;
        int vmax = 0;
        for (int i = 0; i < N; ++i) chmax(vmax, hist[i]);
        if (vmax > (N+1)/2) return -1;
    }

    int num = 0;
    vector<int> hist(N, 0);
    using pint = pair<int,int>;
    vector<pint> ins;
    int prev = 0;
    for (int i = 0; i < N; ++i) {
        if (i == N-1) {
            int first = A[prev];
            int last = A[i];
            if (first == last) hist[first]++;
            ++num;
            ins.emplace_back(first, last);
        }
        else if (A[i] == A[i+1]) {
            int first = A[prev];
            int last = A[i];
            if (first == last) hist[first]++;
            ++num;
            prev = i+1;
            ins.emplace_back(first, last);
        }
    }

    int vmax = 0, val = -1;
    for (int i = 0; i < N; ++i) if (chmax(vmax, hist[i])) val = i;
    int rem = 0;
    for (auto p : ins) if (p.first != val && p.second != val) ++rem;
    int add = max(0, vmax - (rem + 1));
    return num + add - 1;
}

int main() {
    int TTT; cin >> TTT;
    while (TTT--) {
        int N; cin >> N;
        vector<int> A(N);
        for (int i = 0; i < N; ++i) cin >> A[i], --A[i];
        cout << solve(N, A) << endl;
    }
}

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

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

Codeforces Global Round 12 F. The Struggling Contestant (R2400)