F - Contrast

問題

長さ $N$ の整数列 $A, B$ が与えられる。

$B$ を並び替えることで各 $i = 1, \cdots, N$ について $A_i \neq B_i$ が成り立つようにできるか判定し、できるならそのような並び替えを 1 つ求めよ。

制約

• $1 \leq N \leq 2 \cdot 10^5$
• $1 \leq A_i, B_i \leq N$
• $A, B$ は昇順にソートされている

考察

ある整数が $A, B$ 合わせて $N$ 回より多く出現していたら、鳩の巣原理より不可能。 一方これを満たしているとき、以下のように $B$ の並び替えを構成できる。

並び替えとして、 $B$ のシフトのみを考える。まず各整数 $x = 1, \cdots, n$ について「 $x$ が被らないようにするには、最低これだけ右シフトしなければならない」という値を考える。これを $x$ のシフト幅と呼ぶことにする。

例えば $N = 6$ で $A = (1, 2, 3, 3, 3, 5), B = (1, 1, 2, 3, 4, 4)$ のときは以下のようになる。 $x$ が $A, B$ いずれかに出現しない場合は $0$ とする。

そして $A, B$ が冒頭の条件を満たす場合、最大のシフト幅によって $B$ を右シフトすると、条件を満たす並び替えになっている。 上の例では $B = (4, 4, 1, 1, 2, 3)$ となり、確かに条件を満たしている。

正当性の略証

なぜこれで $B$ が条件を満たすのかを軽く説明する。 シフト幅が最大の整数を $x$ とし、被るかどうか注目している整数を $y$ とする。

まず $y$ がシフト中に $B$ の右端から左端へ移動しない場合。 この場合 $y$ が被らないのは、シフト幅の最大性から自然だろう。

そうでない場合を説明するために、「棒」というものを数列に立てる。 具体的には、 $A$ における最右 $x$ の右側と、 $B$ における最左 $x$ の左側に棒を立てる。

例えば上の例では $A = (1, 2, 3, 3, 3 \mid 5), B = (1, 1, 2 \mid 3, 4, 4)$ となる。 そしてシフト後は $B = (4, 4, 1, 1, 2 \mid 3)$ となり、 $A,B$ で棒の位置が揃うことが分かる。

$y$ が $B$ の右端から左端へ移るのは、元々 $y$ が棒の右側にいた場合に限られる。 そして $B$ の並び替え後、この $y$ は棒の左側へ移動する。 一方 $A$ 中では、全ての $y$ は変わらず棒の右側にいる。 シフト後に $A, B$ で棒の位置が揃っていることから、 $y$ が被ることは絶対にないことが分かる。

以上で簡単にだが、 $y$ が被らないことが示された。

実装例

提出 #16715392 - AtCoder Beginner Contest 178

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include <iostream>
#include <algorithm>
#include <vector>

void solve() {
    int n;
    std::cin >> n;

    std::vector<int> xs(n), ys(n);
    for (auto& x : xs) std::cin >> x;
    for (auto& y : ys) std::cin >> y;

    // A中の最右位置、B中の最左位置を求める
    std::vector<int> xr(n + 1, -1), yl(n + 1, -1);
    for (int i = 0; i < n; ++i) xr[xs[i]] = i;
    for (int i = n - 1; i >= 0; --i) yl[ys[i]] = i;

    // 最大のシフト幅を求める
    int d = 0;
    for (int i = 1; i <= n; ++i) {
        if (xr[i] == -1 || yl[i] == -1) continue;
        d = std::max(d, xr[i] - yl[i] + 1);
    }

    // シフトする
    std::rotate(ys.begin(), ys.begin() + n - d, ys.end());

    // 被り判定
    for (int i = 0; i < n; ++i) {
        if (xs[i] == ys[i]) {
            std::cout << "No\n";
            return;
        }
    }

    std::cout << "Yes\n";
    for (auto y : ys) std::cout << y << " ";
    std::cout << "\n";
}