Fair Elevator [AtCoder Regular Contest 104 C]

https://atcoder.jp/contests/arc104/tasks/arc104_c

解説

https://atcoder.jp/contests/arc104/submissions/17177990

条件の簡単化

まず、条件を少し簡単化していく。
エレベーターの階層を数直線上に考えて、ある人が乗り降りすることを区間として考えてみる。
すると、他の人が乗り降りした回数をC[i]としているが、これは区間の長さ-1と考えて問題ない。

自由度が高すぎる。何か固定できないか？

さて、1階で区間の長さ3で乗った場合を考えよう。
すると、x=1で乗ってx=4で降りる人がまず確定する。
次に2階では降りる人はいないので、乗ることになり、区間がかぶっている場合はC[i]=C[j]条件より、
区間の長さも一致する必要があるので、x=2で乗ってx=5で降りる人も確定する。
3階も同様に考えると、x=3で乗って、x=6で降りる。
何が言いたいかというと、1階に乗る人が区間の長さlenを決めると、x=1～len2の区間の組み合わせが確定する。
そして、len2+1以降も同様に先頭が区間の長さを決めることでそれ以降が確定する。
これを繰り返していく方針で解こう。

メモ化再帰、もしくは、動的計画法

check(st) := st階以降の乗り降りの有効な組み合わせを作成できるか
これを作っていくことにしよう（メモ化もしておくこと）
前のセクションの方針通り先頭の区間を全探索する。
その区間内部で、条件を満たす組み合わせが作れるかを確かめていこう。

• 区間の先頭末尾がおかしくないか
• その区間を使用している人が他の場所で出入りしていないか

別に区間に人を確定させる必要はなく、おかしな条件にならないかだけを確認すればいい。
おかしな条件が無ければ、適当に配置すれば条件を満たすことができると考えればいい。
確かめてないけど、実際の組み合わせを要求されてないから、いらないだろうと推測。

WA

1回WAで引っかかったので、引っかかったサンプルを一応上げておく。
自分の場合は単なるコーディングミスだった。

3  
1 3  
4 -1  
5 -1  

int N, A[101], B[101];
int v[201];
int cnt[201];
//---------------------------------------------------------------------------------------------------
bool vis[201];
bool memo[201];
bool check(int st) {
    if (st == 2 * N) return true;
    if (vis[st]) return memo[st];
    vis[st] = true;

    rep(len, 1, N + 1) if(st + len * 2 <= 2 * N) {
        bool ok = check(st + len * 2);
        
        rep(i, 0, len) {
            if (v[st + i] < 0) ok = false;
            if (0 < v[st + i + len]) ok = false;

            if (v[st + i] == 0 && v[st + i + len] == 0) continue;
            else if (v[st + i] == 0) {
                int id = -v[st + i + len];
                if (cnt[id] != 1) ok = false;
            }
            else if (v[st + i + len] == 0) {
                int id = v[st + i];
                if (cnt[id] != 1) ok = false;
            }
            else {
                int id = v[st + i];
                int id2 = -v[st + i + len];
                if (id != id2) ok = false;
                if (cnt[id] != 2) ok = false;
            }
        }

        if (ok) {
            memo[st] = true;
            return true;
        }
    }

    memo[st] = false;
    return false;
}
//---------------------------------------------------------------------------------------------------
#define yes "Yes"
#define no "No"
string solve() {
    rep(i, 0, N) {
        if (0 < A[i]) {
            if (v[A[i] - 1] != 0) return no;
            v[A[i] - 1] = i + 1;
            cnt[i + 1]++;
        }
        if (0 < B[i]) {
            if (v[B[i] - 1] != 0) return no;
            v[B[i] - 1] = -(i + 1);
            cnt[i + 1]++;
        }
    }

    if (check(0)) return yes;
    else return no;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i] >> B[i];
    cout << solve() << endl;
}