D. AB Graph (Codeforces Round #699 Div. 2)

問題

https://codeforces.com/contest/1481/problem/D

問題概要

完全有向グラフが与えられる。各辺にはaまたはbの文字が付与されている。（辺(u, v)と辺(v, u)は独立して考えるため、同じ文字が付与されているとは限らない）

このグラフ上の長さmのパスで、辺に与えられた文字を走査順に並べると回文になるものがあるか判定せよ。またある場合は一例を示せ。

考察

mが奇数の場合は、任意の2頂点間を往復するだけで回文になります。

(u, v)と(v, u)に同じ文字が割り当てられている場合、uとvを往復するだけで回文になります。

残るはmが偶数で、全ての2頂点間の辺の文字が異なる場合のみとなります。

まず、頂点が2つしかない場合は無理です。abab...abとしかなりません。

頂点が3以上の場合、(u, v)と(v, w)の文字が同じとなるような3頂点があればu-v-w間を往復することで回文とすることが可能です。 m % 4 == 0のときはvからスタートしてvwvuvwvu...と移動するとabbaabba...となりますし、m % 4 == 2のときはuからスタートしてuvwvuv...と移動するとaabbaa...となります。

あとはそのような関係の3頂点が存在するかどうかとなりますが、これは必ず存在します。(u, v)と(v, w)の文字が同じでないとき、(u, v) = aかつ(v, w) = bとすると、(w, v) = aです。また(u, w)か(w, u)のどちらかはaなので、w-u-vかu-w-vのどちらかが必ず条件を満たします。

#include <bits/stdc++.h>
using namespace std;

#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define REP(i, n) FOR(i, 0, (n))
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;

        vector<string> s(n);
        REP(i, n) cin >> s[i];

        vector<int> ans(m + 1);
        if (m % 2 == 1) {
            REP(i, m + 1) ans[i] = i % 2 + 1;
        } else {
            bool ok = false;
            REP(i, n - 1) {
                FOR(j, i + 1, n) {
                    if (s[i][j] == s[j][i]) {
                        REP(_, m + 1) ans[_] = (_ % 2 == 0 ? i + 1 : j + 1);
                        ok = true;
                        break;
                    }
                }
                if (ok) break;
            }
            if (!ok) {
                if (n == 2) {
                    cout << "NO" << endl;
                    continue;
                }
                int u, v, w;
                if (s[0][1] == s[1][2]) {
                    u = 0;
                    v = 1;
                    w = 2;
                } else if (s[0][2] == s[2][1]) {
                    u = 0;
                    v = 2;
                    w = 1;
                } else {
                    u = 2;
                    v = 0;
                    w = 1;
                }
                if (m % 4 == 0) {
                    REP(_, m + 1) {
                        if (_ % 4 == 0 or _ % 4 == 2) ans[_] = v + 1;
                        else if (_ % 4 == 1) ans[_] = w + 1;
                        else if (_ % 4 == 3) ans[_] = u + 1;
                    }
                } else {
                    REP(_, m + 1) {
                        if (_ % 4 == 0) ans[_] = u + 1;
                        else if (_ % 4 == 1 or _ % 4 == 3) ans[_] = v + 1;
                        else if (_ % 4 == 2) ans[_] = w + 1;
                    }
                }
            }
        }

        cout << "YES" << endl;
        for (auto a : ans) cout << a << " ";
        cout << endl;
    }
}

感想

最初、DPかなんかでパスを探索しないといけないのかと途方に暮れていたのですが、まずm = 6のときのaabbaaに気づき、しばらくしてからようやくm = 8のときのabbaabbaに気づけたので事なきを得ました。

ただ、任意の3頂点で条件が満たせることには実戦では気づけず、どうせすぐ見つかるだろーの精神で条件を満たす頂点群を3重ループで全探索してました。（危ない）