NoiminのNoise

競技プログラミング (多め) とWeb (たまに) ,自然言語処理 (ブログではまだ)。数式の書き方を一気に KaTeX に変えようとして記事を全削除してインポートし直すなどしたので,過去にブックマークされた記事は URL が変わってしまっている可能性があります…….

AtCoder Regular Contest 104 C - Fair Elevator

問題: C - Fair Elevator

解説: 公式解説

問題概要

$1$ 以上 $2N$ 以下の整数からなる数列 $A = A_1, A_2, \dots A_N$ および $B = B_1, B_2, \dots B_N$ が与えられる。ただし $A$, $B$ は一部の値が欠損している場合がある。$A$, $B$ の欠損した値を適切に埋めて、次の条件をすべて満たすことができるかを Yes または No で答えよ。

  • $1$ 以上 $2N$ 以下の整数が1回ずつ使われる。
  • $A_i < B_i$ である。
  • 区間$\left[ A_i, B_i\right]$ と $\left[ A_j, B_j\right]$ について、区間に重なりがある場合は $B_i - A_i - 1 = B_j - A_j - 1$ である。

解法概要

まず、与えられた入力が初めから条件を満たしていない場合は明らかに No である。例えば、$A_i \gt B_i$ となるような $i$ が初めから存在していたり、入力で同じ整数が2回使われているような場合がこれにあたる。

以下、そうでない場合を考える。

ある $i$ について $A_i = x, B_i = y (\gt x+2)$ だった場合、$A_j = x+1$ であるような $j$ については問題の条件より $B_j = y+1$ である。 同様に、$A_j = x+2$ であるような $j$ については問題の条件より $B_j = y+2$ である。

したがってこの問題は、 $i$ 文字目が整数 $i$ に対応するとして

ABCABC/DEDE/FF/GHIGHI.....

というような (同じ文字を持つものがペアに分かれるイメージ) 区間に $1$ 以上 $2N$ 以下の整数を分けていくような問題になる。

$i+1$ 以上の整数について考えるとき、 $i$ 以下の整数は「矛盾なくペアに分けられる」ということさえわかっていればよく、その分け方を知っている必要はない。したがって、以下のような DP が考えられる。

$\mathit{dp}_{i} =$ ($1$ 以上 $2i$ 以下の整数を矛盾なく $i$ 組のペアに分けることができるか否か?)

更新するときは、 $\mathit{dp}_i = \mathrm{true}$ となるような $i$ からさらに $j$ 組のペアを追加することを考えれば良い。

「矛盾なくペアに分けられる」と一言で書いてしまったが、これは実際に値を埋める必要はなく、今の地点で入ってる値を検査するだけで良い。 詳しい条件はソースコード参照。

ソースコード

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n, -1), b(n, -1);
    for(int i=0;i<n;++i) {
        cin >> a[i] >> b[i];
    }

    // 使用済みの数字はチェックしておいて、
    // あとで「ペアになるべき数字が他の場所で使われていないか?」の判定に使う
    vector<bool> used(2*n+1, false);
    // 最初からすでにおかしくない? をチェック
    for(int i=0;i<n;++i) {
        if((a[i] != -1 && used[a[i]]) || (b[i] != -1 && used[b[i]])) {
            cout << "No" << endl;
            return 0;
        }
        if(a[i] != -1 && b[i] != -1 && a[i] > b[i]) {
            cout << "No" << endl;
            return 0;
        }
        if(a[i] != -1) used[a[i]] = true;
        if(b[i] != -1) used[b[i]] = true;
    }

    vector<bool> dp(n+1, false);
    dp[0] = true;
    for(int i=0;i<n;++i) { // すでに決まっているペア数
        if(!dp[i]) continue;
        for(int j=1;j<=n-i;++j) { // j ペア分追加できるか見る
            if(dp[i+j]) continue;
            // 2*i+1, 2*i+2, ..., 2*i+2*j-1, 2*i+2*j を正しく配置できる?
            bool ok = true;
            for(int k=0;k<n&&ok;++k) { // 追加して矛盾しないかどうか一通り見て回る
                // a は今注目している範囲の中か?
                bool in_a_range = (2*i+1 <= a[k]) && (a[k] <= 2*i+j);
                // b は今注目している範囲の中か?
                bool in_b_range = (2*i+j+1 <= b[k]) && (b[k] <= 2*i+2*j);
                // 両方値が設定済み
                if(a[k] != -1 && b[k] != -1) {
                    // 今注目している範囲に片方だけおさまっていたら OUT
                    if(in_a_range ^ in_b_range) ok = false;
                    // 今注目している範囲内で、かつ差が j 以外でも OUT
                    if(in_a_range && in_b_range && b[k] - a[k] != j) ok = false;
                }
                // a 設定済み (b は問わない)
                if(a[k] != -1) {
                    // a なのに b が入るべき範囲内に入っていたら OUT
                    if(2*i+j+1 <= a[k] && a[k] <= 2*i+2*j) ok = false;
                    // a が今注目している範囲の中で、かつペアになるはずのものが他の場所で使用済みだったら OUT
                    if(in_a_range && b[k] != a[k]+j && used[a[k]+j]) ok = false;
                }
                // b 設定済み (a は問わない)
                if(b[k] != -1) {
                    // b なのに a が入るべき範囲内に入っていたら OUT
                    if(2*i+1 <= b[k] && b[k] <= 2*i+j) ok = false;
                    // b が今注目している範囲の中で、かつペアになるはずのものが他の場所で使用済みだったら OUT
                    if(in_b_range && a[k] != b[k]-j && used[b[k]-j]) ok = false;
                }
            }
            dp[i+j] = ok;
        }
    }
    cout << (dp[n] ? "Yes" : "No") << endl;
}

所感

これは AC までいかなくともキーになる考え (1 から 2n までを ABCABC DEDE みたいな区間に分ける問題に言い換えられる) は気づきたかった。 解説チラ見してからも条件の考慮もれがたくさんあって、自分のこういうところが PG BATTLE で危ないんだよなあと思った。

それはそれとして問題自体は好き。最近、区間 DP 得意になりたい。