Pair of Balls(ABC216D)

本番中に解けずに泣いた。
WAを出しまくったので自戒を込めて書く。
atcoder.jp

考察

愚直に上からペアになった石を取っていけば良いか？山の数的に探索が間に合わなさそう。(解説を見ると上手くやると間に合うらしい...)
各山を見て行った時に、特定の数字の深さの大小関係が保存されていれば全部の石を取れそう->実装しよう。
深さの大小関係が保存されているというのがどういうことかというと、例えば下記のような山が3つあるとき、1個目の山の2->4->1に着目した時、それらの要素は2つ目の山中でも(5)->2->4->(3)->1となっており深さの大小関係が等しい。

2 4 1
5 2 4 3 1
5 3

逆にこれが下記のようになっている場合、2つ目の山は(5)->4->2->(3)->1となっているので、1つ目の山の要素の深さの大小関係と矛盾する。こういうときはどう頑張っても取れない。
よって、これを実装していけば良い。

2 4 1
5 4 2 3 1
5 3

実装

各玉は2個ずつしかないので、入力を取るときにhashmapで各玉の各個体の所属する深さをメモしておく。

    map<int, vector<pair<int, int>>> memo;
    rep(i, m) {
        int k;
        cin >> k;
        rep(j, k) {
            int v;
            cin >> v;
            c[i].pb(v);
            memo[v].pb({i, j + 1});
        }
    }

そして、順に山を見ていき、他方の玉の所属する山と深さをメモしつつ、深さの大小関係が崩れた場合に答えを"No"にしておけば良い。

 rep(i, m) {
        map<int, int> d;
        for (int v : c[i]) {
            if (memo[v][0].first == i) {
                int idx = memo[v][1].first;
                int depth = memo[v][1].second;
                if (d[idx] > depth) { res = "No"; }
                d[idx] = depth;
            }
        }
    }

ただ、この実装ではエッジケースが残る。（本番中にこれが解消できなかった....。）
例えば同じ山に同じ玉が所属している場合はどう足掻いても玉を取りきれない。
よって、これをチェックすればおしまい。

    for (auto v : memo) {
        if (v.second[0].first == v.second[1].first) res = "No";
    }

反省

最初に問題文を雑に読んでしまい、隣接した2つの山からのみ玉が取れると勘違いしたのが本当に良くない....。
問題文をよく読みましょう。