Learning Algorithms

アルゴリズムの勉強メモ

CF Round #288 Div.2 D. Tanya and Password

Codeforces Round #288 Div.2 D. Tanya and Password

Problem - D - Codeforces

長さ3の文字列n個が与えられる。それらすべてが、長さがn + 2ある適当な文字列の3-gramとなっているならば、その文字列を出力する。解法自体は容易である。すなわち、xyzという文字列に対して、xyというノードからyzというノードに有向辺を張ってグラフを作っていき、できたグラフがオイラー路をなすかどうかを判定し、オイラー路でありかつ連結であればそのオイラー路を出力する。文字の種類は0~9,a~z,A~Zの62種類なので、2桁の62進数として区別して管理すると良い。自力で考えたアルゴリズムは嘘だったので、結局以下のサイトを参考にして通した。有向グラフG2に加えて、次数を調べるためだけの無向グラフGもつくったが、あまり適当なやり方では無い気はするので参考サイトのようにやったほうがいいと思う。
Spaghetti Source - 有向オイラー路

連結であれば、すべてのノードを通れることが保証されているのだから、あとは順番が問題である。

void visit(int s, vi &path) {
        while (!G[s].empty()) {
                int next = G[s].back();
                G[s].pop_back();
                visit(next, path);
        }
        path.pb(s);
}

ポイントは上記の再帰コードである。まず一番最初にpathにpbされるのは明らかにゴールとなるべきノードであることがわかるだろう。なぜなら、スタート直後以降、ゴール以外のノードについては入る辺と出ていく辺の数が等しいから、入る辺が存在するならば、出る辺も必ず存在するからである。そのあと一つずつノードを戻していき、まだ使っていない辺を探していく。すなわち見つからないなら、そのノードをpbして一つ戻し、見つかった場合、そのノードをXとし、Xから新しい探索をする。その探索では必ずXに戻ってくる(その部分が強連結成分となっている)ことが保証される。なぜなら、Xから新しい探索をしていくときは、(X以外で)行き止まりになるようなノード(1回目の探索のゴールに相当するノード)がX以外には存在しないので、自分自身に帰ってくるしかありえないからである(そのようなノードがあるならばそのノードは出ていく辺の数が入っていく辺の数より少なくとも1小さくなっているはずである)。そのような閉路を途中にはさみこんで、スタートのノードまでpbしたら終了とする。これでオイラー路の逆路が得られるので、それをreverseする。

#include "bits/stdc++.h"
using namespace std;
#define OUT(x)                cout << #x << " = " << x << endl; 
#define rep(i, n)             for (int (i) = 0; (i) < (int)(n); (i)++)
#define rer(i, l, r)          for (int (i) = (int)(l); (i) <= (int)(r); (i)++)
#define reu(i, l, r)          for (int (i) = (int)(l); (i) < (int)(r); (i)++)
#define each(i, v)            for (auto i : v)
#define all(x)                (x).begin(), (x).end()
#define rall(x)               (x).rbegin(), (x).rend()
#define pb(x)                 push_back(x)
#define bp(x)                 __builtin_popcount(x)
#define mp(x, y)              make_pair((x), (y))
#define fi                    first
#define se                    second
#define setp(x)               setprecision(x)
#define mset(m, v)            memset(m, v, sizeof(m))
static const int INF        = 0x3f3f3f3f;
static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
static const int MOD        = 1000000007;
static const double PI      = 3.14159265358979;

//#define int                   long long

typedef vector<double>        vd;
typedef vector<string>        vs;
typedef vector<bool>          vb;
typedef vector<int>           vi;
typedef pair<int, int>        pii;
typedef vector<pii>           vpii;

template<typename T> void pv(T a, T b) { for (T i = a; i != b; i ++) cout << *i << " "; cout << endl; }
template<typename T, typename U> inline void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if (x < y) x = y; }
int in() { int _x; cin >> _x; return _x; }

vi G[4000];
vi G2[4000];

int to62(char s) {
        if ('0' <= s && s <= '9') return s - '0';
        if ('a' <= s && s <= 'z') return s - 'a' + 10;
        else return s - 'A' + 36;
}

char tochar(int a) {
        if (0 <= a && a <= 9) return '0' + a;
        if (10 <= a && a <= 35) return 'a' + a - 10;
        else return 'A' + a - 36;
}

void visit(int s, vi &path) {
        while (!G2[s].empty()) {
                int next = G2[s].back();
                G2[s].pop_back();
                visit(next, path);
        }
        path.pb(s);
}

signed main() { 
        int n = in();
        rep(i, n) {
                char s[4];
                cin >> s;
                int a = 62 * to62(s[0]) + to62(s[1]);
                int b = 62 * to62(s[1]) + to62(s[2]);
                G[a].pb(b);
                G[b].pb(a);
                G2[a].pb(b);
        }
        int cnt = 0;
        vi ibox;
        rep(i, 4000) if (G[i].size() & 1) ibox.pb(i);
        int ss;
        if (ibox.empty()) rep(i, 4000) if (G[i].size() > 0) ss = i;
        char ans;
        bool f = false;
        vi path;
        if (ibox.size() <= 2) {
                f = true;
                int start;
                if (!ibox.empty()) {
                        if (G[ibox[0]].size() - G2[ibox[0]].size() < G2[ibox[0]].size()) start = ibox[0];
                        else start = ibox[1];
                } else {
                        start = ss;
                }
                ans = tochar(start / 62);
                visit(start, path);
                reverse(all(path));
        }

        if (!f || path.size() != n + 1) cout << "NO" << endl;
        else {
                cout << "YES" << endl;
                cout << ans;
                rep(i, path.size()) {
                        cout << tochar(path[i] % 62);
                }
                cout << endl;
        }
        return 0;
}               

オイラー路は奥が深そう。