AtCoder Grand Contest 013 B - Hamiltonish Path

問題

　 $N$ 頂点 $M$ 辺の連結な単純無向グラフについて、

2個以上の頂点を通る
同じ頂点を2度以上通らない
パスの少なくとも一方の端点と直接辺で結ばれている頂点は必ずパスに含まれる

　という条件を満たすパスを1つ見つけて出力せよ。

解法

　1時間半ほど考えてもさっぱりわからなかったので解説PDFを読んだ。

　適当なパスを作り条件を満たしていなかったら伸ばすことを繰り返していくと、最終的には $N$ 頂点を覆うパスができるのでいつかは条件が満たされる。条件を満たしているかの判定にかかる計算量も高々 $O(M)$ なのでこれで間に合う。

　解説PDFの手法をかなり愚直めに実装したら1515msecで結構危なかった。

#include"bits/stdc++.h"
using namespace std;
using ll = long long;

int main() {
    ll N, M;
    cin >> N >> M;
    vector<vector<ll>> connect(N);
    vector<ll> ans;

    for (ll i = 0; i < M; i++) {
        ll A, B;
        cin >> A >> B;
        A--; B--;
        connect[A].push_back(B);
        connect[B].push_back(A);

        if (i == 0) {
            ans.push_back(A);
            ans.push_back(B);
        }
    }

    vector<bool> visit(N, false);
    visit[ans[0]] = true;
    visit[ans[1]] = true;

    auto isOK = [&]() {
        for (auto n : connect[ans.front()]) {
            if (!visit[n]) {
                return false;
            }
        }
        for (auto n : connect[ans.back()]) {
            if (!visit[n]) {
                return false;
            }
        }
        return true;
    };

    while (!isOK()) {
        bool add = false;
        for (auto n : connect[ans.back()]) {
            if (!visit[n]) {
                ans.push_back(n);
                visit[n] = true;
                add = true;
                break;
            }
        }
        if (add) {
            continue;
        }
        for (auto n : connect[ans.front()]) {
            if (!visit[n]) {
                ans.insert(ans.begin(), n);
                visit[n] = true;
                break;
            }
        }
    }

    cout << ans.size() << endl;
    for (ll i = 0; i < ans.size(); i++) {
        cout << ans[i] + 1 << " \n"[i == ans.size() - 1];
    }
}

反省

　見当違いの考察しかできていなかった。基本的に考えていたのはもとのグラフの次数に注目したことで、次数1のノードが2つあればそれらを繋いでいけばいいし、1つでもそれを片方の端点には使っていいだろうという感じ。次数2以上のノードしかないときは、サイクルができるはずなのでそれを上手く加工すれば条件が満たされるのではないか……と思っていたが、その先がさっぱりわからなかった。

　解説の方法は、貪欲法と言われればそうなのかもしれないけどなかなかこれを上手く思いつける気がしない。しかし具体例を構成するタイプの問題ではこの手の解法は定跡だったりするのかもしれない。ダメなものをどう加工すれば良くなるか、という視点が重要だったのだろうか。しかし1回増やしただけで条件を満たすわけではなく、最終的には満たす状態になりうる～という感じの解法はなかなか難しいように思える。