RUPC2018 day2 F: Ghost Legs
問題ページ
Aizu Online Judge Arena
解法
あみだくじで最終的にどこにたどりつくかのみが重要なので途中の横線の位置を気にする必要はない。縦線3本のあみだくじでは 3!=6通り の置換にまとめられる。
恒等写像にならないような置換の組み合わせを考える。(0,1,2)は存在してはいけない。(0,2,1)(1,0,2)(2,1,0)は同じものを縦につなげると恒等写像になるので2つ以上存在してはいけない。(1,2,0)(2,0,1)はこれらをつなげると恒等写像になるのでこの組が同時に存在してはいけない。したがって、(0,2,1), (1,0,2), (2,1,0), {(1,2,0)or(2,0,1)が2個}の組み合わせにこれ以上置換を増やすと必ず恒等写像が存在する。つまり n>=6 であれば必ず恒等写像が存在し答えは"yes"になる。
n<=5であれば愚直に何をしても大体通るのでO(n2nn!)の全探索をすると通る。
あみだくじを置換の形にするのはvec[i]=iとなる配列を用意しておき、縦線iとi+1の間に横線があればswap(vec[i], vec[i+1])とすると簡単に実装ができる。こうしてあみだくじを置換に変換し、置換の集合をつくる。この置換の部分集合を全列挙して、各部分集合に対してnext_permutationを用いて順列を全て試すと全探索ができる。
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define int ll using VI = vector<int>; using VVI = vector<VI>; using PII = pair<int, int>; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() #define PB push_back const ll LLINF = (1LL<<60); const int INF = (1LL<<30); const int MOD = 1000000007; template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; } template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); } template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a){ out<<'('<<a.first<<','<<a.second<<')'; return out; } template<class T> ostream &operator <<(ostream& out,const vector<T>& a){ out<<'['; REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';} out<<']'; return out; } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; signed main(void) { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; VVI vec; REP(i, n) { int w; cin >> w; VI v = {0, 1, 2}; REP(j, w) { int a; cin >> a; if(a == 0) swap(v[0], v[1]); else swap(v[1], v[2]); } vec.PB(v); } if(n >= 6) { cout << "yes" << endl; return 0; } sort(ALL(vec)); FOR(i, 1, 1<<vec.size()) { // vecの部分集合 VVI v; REP(j, vec.size()) { if(i&1<<j) v.PB(vec[j]); } // 全ての順列を試す do { VI amida = {0, 1, 2}; for(auto k: v) { amida[0] = k[amida[0]]; amida[1] = k[amida[1]]; amida[2] = k[amida[2]]; } // 恒等写像があったらyes if(amida == VI{0, 1, 2}) { cout << "yes" << endl; return 0; } } while(next_permutation(ALL(v))); } cout << "no" << endl; return 0; }