Construct Good Path [AtCoder Beginner Contest 244 G]

https://atcoder.jp/contests/abc244/tasks/abc244_g

解説

https://atcoder.jp/contests/abc244/submissions/30323833

何から始めればいいか困る問題。
構築問題で重要なのはなるべくシンプルなルールで構築を考えていくことである。
今回は特に最適なパス長である必要はないので、若干非効率な方法でも許される。
効率よりも分かりやすさというかシンプルな方法を模索しよう。

どんな条件でも作れる

今回の問題設定では、条件を満たすどんなグラフとSの組であっても良いパスを作ることができるらしい。
ということは与えられたグラフから辺をいくつか削除して、木にしたとしても答えが得られることになる。
この工夫は試行錯誤の結果ではあるのだが、グラフを木にすることでちょっとだけ問題をシンプルにしておこう。

根付き木として考えてみる

スタート地点を1つ決めてそこを根として木を見てみよう。
移動していくと、葉まで行って偶奇が異なる場合はその親に一回戻って葉に再度移れば、偶奇を変更することができる。
これは葉に限らず、他の頂点でも同様である。
つまり、何が言いたいかというと

「現在いる頂点の偶奇を変えたい場合は、親に移動してから自分に戻ってくれば、
　『自分の子孫の偶奇を変更することなく』自分の偶奇を変更可能」

ということである。これは非常に都合がいい。
よって、木をdfsで探索しながら子供の偶奇を全部一致させた後、自分の偶奇を以上のテクで一致させれば、
自分を含めた部分木の偶奇を全部一致させた上で親に戻ることができる。

ここら辺の認識が一番難しい。
実装に落とし込むと割と完結になっているので、実装から思想を吸い上げてもいいかもしれない。

つまり、実装は？

適当に頂点0を始点としてdfsを行う。
訪れた頂点をメモして再度訪れないようにしておけば、無向グラフであっても木上でdfsをしているようなコードが書ける。
各頂点でやることとしては、

1. 子頂点についてdfsを再度行って、子頂点について偶奇が一致するようにする
2. 子頂点について偶奇が一致したら、親を使って自分の偶奇を一致させる

を繰り返す。
注意点として頂点0は親を持っていないので偶奇が調整できない。
これは、数列として0→1→2→1→0みたいな数列を作っていると思うが、
最初の0を取り除けばこれまでの偶奇は変わらずに頂点0の偶奇だけを変更できる。

4Nにおさまってる？

正直、未証明ACだが、調整は各頂点で1回ずつしか発生しないし、普通に回るのに2Nかかって調整で2Nかかってで
間に合いそうな雰囲気はある。
（コンテスト中に必ず通すという思想では、始点を0ではなくランダムに設定すると嫌味なケースを回避できるかも）

自分の実装では行ってみて偶奇が合わないなら調整する形をとっているが、そもそも行かなくていいという
ケースを処理すればもっと改善できそう。

int N, M;
vector<int> E[101010];
string S;
//---------------------------------------------------------------------------------------------------
deque<int> ans;
int parity[101010];
void add(int cu) {
    parity[cu] ^= 1;
    ans.push_back(cu);
}
//---------------------------------------------------------------------------------------------------
bool vis[101010];
void dfs(int cu, int pa = -1) {
    vis[cu] = true;

    add(cu);
    fore(to, E[cu]) if(!vis[to]) {
        dfs(to, cu);
        add(cu);
    }

    if (0 <= pa && parity[cu] != S[cu]) {
        add(pa);
        add(cu);
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, M) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        E[u].push_back(v);
        E[v].push_back(u);
    }
    cin >> S;

    fore(c, S) c -= '0';

    dfs(0);
    if (parity[0] != S[0]) ans.pop_front();

    int K = ans.size();
    printf("%d\n", K);
    while (!ans.empty()) {
        if (ans.size() != K) printf(" ");
        printf("%d", ans.front() + 1);
        ans.pop_front();
    }
    printf("\n");
}