CF Round #197 Div.2 D. Xenia and Bit Operations
Codeforces Round #197 Div.2 D. Xenia and Bit Operations
2のn乗個の数列に対して、
奇数番目の数とその次の数同士のorをとって数列をつくる
奇数番目の数とその次の数同士のxorをとって数列をつくる
という操作を数が1個になるまで交互に繰り返す。p番目をbに変えていく、というクエリが与えられるのでそれを順次行なったあとの、最後に残る1個の数をクエリごとに答える問題。セグメントツリーの更新部分を少しいじって実装すればよい。すなわち、2つの子ノードのorまたはxorをとったものを親ノードとして更新する、という操作を繰り返していけば良い。セグメントツリーの問題を解いたのは初めてだったので、「セグメントツリー」でググって見つけたライブラリみたいなものをコピペして、てきとーにごにょごにょ書き換えたら15分ほどであっさり通せた。使いやすい自分なりのライブラリを作りたい。
#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)) #define sz(x) (int)(x.size()) 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; scanf("%d", &_x); return _x; } long long lin() {long long _x; scanf("%lld", &_x); return _x; }; #define MAX (2 << 17) struct Segtree { int N, dat[2 * MAX]; Segtree(int n) { N = 1; while (N < n) N *= 2; for (int i = 0; i < 2 * N - 1; i++) dat[i] = INF; } void update(int k, int a) { bool f = true;//最初はorをとる k += N - 1; dat[k] = a; while (k > 0) { k = (k - 1) / 2; if (f) dat[k] = dat[k * 2 + 1] | dat[k * 2 + 2]; else dat[k] = dat[k * 2 + 1] ^ dat[k * 2 + 2]; f ^= 1;//交互に操作する } } }; signed main() { int n, q; cin >> n >> q; Segtree tree(1 << n); rep(i, 1 << n) { int a; cin >> a; tree.update(i, a); } while (q --) { int p, b; cin >> p >> b; tree.update(p - 1, b); cout << tree.dat[0] << endl; } return 0; }
セグメントツリーの問題をこれからじわじわ解いていく。
CF Round #208 Div.2 E. Dima and Kicks
Codeforces Round #208 Div.2 E. Dima and Kicks
kmjpさんの解法を丸パクリ参考にさせていただきました。ありがとうございます。
kmjp.hatenablog.jp
とはいえ、自分で理解するためにコメントを書き、少し理解しやすいように書き換えた。
解法は上記のURLに。コードについて書き換えさせてもらった点は、最初の条件判定をビット演算を使わずに単純に書き換える操作で判定するようにした点、checkはメイン関数内のみの使用としてわかりやすくした点、あとは大量にコメントを書いた点。
#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)) #define sz(x) (int)(x.size()) 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; scanf("%d", &_x); return _x; } long long lin() {long long _x; scanf("%lld", &_x); return _x; }; //固定 int constmat[1001][1001]; //mainの中のみで、最初の条件チェックに使う int check[1001][1001]; //1桁目はx方向の正の方向に辺があれば1 //2桁目はx方向の負の方向に辺があれば1 //3桁目はy方向の正の方向に辺があれば1 //4桁目はy方向の負の方向に辺があれば1 //5桁目は、特になし？ //6桁目は幅優先探索において、すでに通ったならば1 //7桁目は、ノードの役割を果たすのであれば1 int node[1001][1001]; int n, m; int ok(int k, int sx, int sy) { rep(i, 1001) rep(j, 1001) node[i][j] = 0; for (int y = sy; y < n; y += k) for (int x = sx; x < m; x += k) { if (constmat[y][x] == 0) continue; //ノードとして使っていることを明示するために7桁目を立てておく node[y][x] |= 64; //y方向 //隣り合うノードがともに1であるならば、その区間の中はすべて1またはすべて0でなければならない //すべて1のものについては、そこに無向辺を張る if (y + k < n && (constmat[y + k][x] == 1)) { int j = 0; for (int i = 1; i < k; i ++) j += constmat[y + i][x] == 1; //j == 0ですべて0、j == k - 1ですべて1である if (j != 0 && j != k - 1) return 0; if (j == k - 1) { //正の方向に移動可能 node[y][x] |= 1; //負の方向に移動可能 node[y + k][x] |= 2; } } //x方向 //隣り合うノードがともに1であるならば、その区間の中はすべて1またはすべて0でなければならない //すべて1のものについては、そこに無向辺を張る if (x + k < m && (constmat[y][x + k] == 1)) { int j = 0; for (int i = 1; i < k; i ++) j += constmat[y][x + i] == 1; //j == 0ですべて0、j == k - 1ですべて1である if (j != 0 && j != k - 1) return 0; if (j == k - 1) { //正の方向に移動可能 node[y][x] |= 4; //負の方向に移動可能 node[y][x + k] |= 8; } } } int cnt = 0; //各ノードの次数が奇数である数をカウント rep(y, n) rep(x, m) cnt += (bp(node[y][x] & 15) % 2); //オイラー路を構成できない if (cnt != 0 && cnt != 2) return 0; queue<int> q; //無向オイラー路が構成可能ならば、任意ノードからはじめてよい int y, x; for (y = 0; y < n; y ++) for (x = 0; x < m; x ++) if (node[y][x]) goto out; if (y == n) return 0; out: //辺があるか if ((node[y][x] & 15) == 0) return 0; //yとxを1万進数2桁で管理 q.push(y * 10000 + x); //6桁目を立てる(usedに相当する) node[y][x] |= 32; while (!q.empty()) { int kk = q.front(); q.pop(); int cx = kk % 10000, cy = kk / 10000; int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0}; rep(i, 4) { //(i + 1)桁目が立っているなら、その方向に辺が存在する if ((node[cy][cx] & (1 << i)) == 0) continue; int tx = cx + dx[i] * k, ty = cy + dy[i] * k; if (tx < 0 || ty < 0 || tx >= m || ty >= n) continue; if (node[ty][tx] & 32) continue; node[ty][tx] |= 32; q.push(ty * 10000 + tx); } } //ノードとして使っていて、かつ探索のときに使っていないものが存在するなら、オイラー路を構成できていない rep(y, n) rep(x, m) if ((node[y][x] & 64) && ((node[y][x] & 32) == 0)) return 0; return 1; } signed main() { cin >> n >> m; int sy, sx; rep(y, n) rep(x, m) cin >> constmat[y][x]; rep(y, n) rep(x, m) if (constmat[y][x]) sy = y, sx = x; for (int k = min(n, m); k >= 2; k --) { int f = 0; memmove(check, constmat, sizeof(check)); //通れる道すべてを0に書き換える for (int y = sy % k; y < n; y += k) for (int x = sx % k; x < m; x += k) { if (y + k < n) for (int i = 0; i <= k; i ++) check[y + i][x] = 0; if (x + k < m) for (int i = 0; i <= k; i ++) check[y][x + i] = 0; } //1が残っていたら、このkは条件を満たせない rep(y, n) if (f == 0) rep(x, n) if (check[y][x] == 1) f = 1; if (f) continue; if (ok(k, sx % k, sy % k)) { for (int i = 2; i <= k; i ++) if (k % i == 0) cout << i << ' '; cout << endl; return 0; } } cout << -1 << endl; return 0; }
このビットで管理する感じの書き方はすごいなぁ。
CF Round #375 Div.2 E. One-Way Reform
Codeforces Round #375 Div.2 E問題
与えられた単純無向グラフに対して、入次数と出次数が等しい頂点の数が最大化されるように各辺に向きをつける、という問題。連結とは限らないことに注意する。辺の追加はできないので、そもそも次数が奇数である頂点は条件を満たす頂点にはなりえない。まず例によって次数が奇数である頂点同士を無向辺でつなぐことで、すべての頂点の次数を偶数にすることを考える。このグラフは、オイラー路を構成できる。するとすべての頂点について、条件を満たすことになる。辺を加えたのは、もともと次数が奇数だった頂点同士のみだったので、もともと次数が偶数だった頂点については、このオイラー路によってできる辺の向きで条件を満たすことになる。よって求める最大値はnから次数が奇数である頂点数を引いた数になり、加えた辺以外のオイラー路のパスを出力すれば良い。グラフが非連結である場合に注意してそれぞれの連結部分でオイラー路を構成した。隣接リストで実装したが、すごく煩雑になったので、隣接行列で実装すべきだった（ n <= 200だったからそりゃそうか）。
#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)) #define sz(x) (int)(x.size()) 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[220]; vi path; //無向グラフからオイラー路を作る void visit(int s, vi& path) { while (!g[s].empty()) { int next = g[s].back(); g[s].pop_back(); rep(j, sz(g[next])) { if (g[next][j] == s) { g[next].erase(g[next].begin() + j); break; } } visit(next, path); } path.pb(s); } signed main() { int t; cin >> t; while (t --) { int n, m; cin >> n >> m; rep(i, 220) g[i].clear(); rep(i, m) { int a, b; cin >> a >> b; a --, b --; g[a].pb(b); g[b].pb(a); } vi odd; int ans = n; rep(i, n) if (sz(g[i]) & 1) { odd.pb(i); ans --;//次数が奇数でないものの数 } vi crash[220]; rep(i, sz(odd)) { g[odd[i]].pb(odd[i + 1]);//次数が奇数の頂点同士を繋ぐ g[odd[i + 1]].pb(odd[i]); crash[odd[i + 1]].pb(odd[i]);//あとで壊すため（構成したオイラー路のうち、本来無い辺） crash[odd[i]].pb(odd[i + 1]); i ++; } path.clear(); rep(i, n) { if (!g[i].empty()) { visit(i, path); path.pb(-1);//非連結な部分を-1で区別する } } reverse(all(path)); cout << ans << endl; rep(i, sz(path) - 1) { if (path[i] == -1 || path[i + 1] == -1) continue;//-1のときは連結部分の境目 bool f = true; rep(j, sz(crash[path[i]])) { if (crash[path[i]][j] == path[i + 1]) { f = false;//crashコンテナに入っている辺なら出力してはいけない crash[path[i]].erase(crash[path[i]].begin() + j); rep(k, sz(crash[path[i + 1]])) { if (crash[path[i + 1]][k] == path[i]) { crash[path[i + 1]].erase(crash[path[i + 1]].begin() + k); } } } } if (f) cout << path[i] + 1 << ' ' << path[i + 1] + 1 << endl; } } return 0; }
もうちょっときれいに書きたい。。。
追記
隣接行列による実装。めっちゃ書きやすかった。
#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)) #define sz(x) (int)(x.size()) 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; } int g[220][220]; vi path; int used[220]; void visit(int s, vi& path) { used[s] = true; rep(i, 220) if (g[s][i] > 0) { g[s][i] --; g[i][s] --; visit(i, path); } path.pb(s); } signed main() { int t; cin >> t; while (t --) { int n, m; cin >> n >> m; rep(i, 220) rep(j, 220) g[i][j] = 0; rep(i, m) { int a, b; cin >> a >> b; a --, b --; g[a][b] ++; g[b][a] ++; } vi odd; int ans = n; rep(i, n) { int cnt = 0; rep(j, n) cnt += g[i][j]; if (cnt & 1) { odd.pb(i); ans --; } } int crash[220][220] = { 0 }; rep(i, sz(odd)) { g[odd[i]][odd[i + 1]] ++; g[odd[i + 1]][odd[i]] ++; crash[odd[i]][odd[i + 1]] ++; crash[odd[i + 1]][odd[i]] ++; i ++; } rep(i, 220) used[i] = false; path.clear(); rep(i, n) { if (!used[i]) { visit(i, path); path.pb(-1); } } reverse(all(path)); cout << ans << endl; rep(i, sz(path) - 1) { if (path[i] == -1 || path[i + 1] == -1) continue; bool f = true; if (crash[path[i]][path[i + 1]] > 0) { f = false; crash[path[i]][path[i + 1]] --; crash[path[i + 1]][path[i]] --; } if (f) cout << path[i] + 1 << ' ' << path[i + 1] + 1 << endl; } } return 0; }
CF Round #296 Div.1 C. Data Center Drama
Codeforces Round #296 Div.1 C. Data Center Drama
オイラー路の問題をまとめて解いている。
Problem - C - Codeforces
n頂点、m辺の無向グラフが与えられる。各頂点について、その頂点から出ていく本数とその頂点に入ってくる本数がともに偶数になるように、辺の向きを構成し、必要に応じて最小限の数だけ有向辺を追加すると言う問題。オイラー路を使うとわかっている状況で解いたものの、自力でACまで持ち込めた。
まず、各頂点の次数をカウントし、それが奇数のものを列挙し、それらを適当に（てきとーでよいことがあとからわかる）無向辺で繋ぐ。列挙された頂点の数が奇数であることはないので、すべてうまくマッチングされる。なぜなら、グラフにおいて辺を一つ増やすとき必ず全体の次数の総和は２増えるため、ある頂点の次数が奇数であるならば、それに対応するようにまた別のある点が存在して、その次数が奇数であるからである。次数が偶数でなければ条件を満たすことはできないので、これらの辺はどれも必ず作る必要がある。
以上の操作によってできる無向グラフは、全ての頂点の次数が偶数になっているので、任意の点からオイラー閉路が構成可能である。その点を0として、そこから例のオイラー路をつくるアルゴリズムを無向グラフ用に改良して、オイラー路を一つつくる
void visit(int s, vi& path) { while (!g[s].empty()) { int next = g[s].back(); g[s].pop_back(); rep(j, sz(g[next])) { if (g[next][j] == s) { g[next].erase(g[next].begin() + j); break; } } visit(next, path); } path.pb(s); }
これで構成したオイラー路について、そのパスの偶数番目の辺は、オイラー路の向きそのままの向きの有向辺、奇数番目の辺をオイラー路の向きとは逆向きの有向辺として繋いでいく。すると、そのパスが頂点を通るたびに、出ていく辺または入っていく辺のいずれかが２本増加することになり、条件に反しないように有向辺を構成していくことができる。これはオイラー路なので、全ての辺を経由することも保証されている。次数がもともと奇数だった頂点同士をてきとーに繋いでよかったのは、結局オイラー路が構成できるような状態に持ち込んだ時点で、あと問題になるのは辺の数のみになっていたので、どれとどれを繋いでもよかったということである。以上の操作を終えたら、あとは頂点０について条件に矛盾しないようにすればよい。辺の向きは交互に変えて構成していくので、辺の数が偶数であるとき、頂点０についても条件を満たし、これで操作は終わりである。辺の数が奇数であるときは、０から出る辺と０に入る辺の数がともに奇数となっているはずなので、０に自己辺を張ることで条件を満たすようにできる。これらの操作数が最小であることは上にも述べたとおりであるから、これで終わりである。
ちなみにこの実装では、std::cinを使うとTLEとなる。
#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)) #define sz(x) (int)(x.size()) 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; scanf("%d", &_x); return _x; } vi g[101010]; void visit(int s, vi& path) { while (!g[s].empty()) { int next = g[s].back(); g[s].pop_back(); rep(j, sz(g[next])) { if (g[next][j] == s) { g[next].erase(g[next].begin() + j);//無向グラフなので、反対も壊す break; } } visit(next, path); } path.pb(s); } signed main() { int n, m; cin >> n >> m; rep(i, m) { int a = in(), b = in(); a --, b --; g[a].pb(b); g[b].pb(a); } vi odd; rep(i, n) if (sz(g[i]) & 1) odd.pb(i); int cnt = 0; rep(i, sz(odd)) { g[odd[i]].pb(odd[i + 1]); g[odd[i + 1]].pb(odd[i]); i ++; cnt ++; } vi path; visit(0, path); reverse(all(path)); vpii ans; rep(i, sz(path) - 1) { if (i & 1) ans.pb(mp(path[i], path[i + 1])); else ans.pb(mp(path[i + 1], path[i])); } if ((m + cnt) & 1) ans.pb(mp(0, 0)); cout << sz(ans) << endl; rep(i, sz(ans)) cout << ans[i].fi + 1 << ' ' << ans[i].se + 1 << endl; return 0; }
オイラー路の応用範囲は広そうだ。おもしろい問題も多い印象。
AOJ Patrol
AOJ Patrol
無向オイラー路の判定をするだけなので、スタート地点とゴール地点の字数が奇数でかつ他の点の字数がすべて偶数であるかどうかを判定するだけである。入力の受け取り方の方が面倒な問題......。
問題解いてる部分はここだけ。
bool f = true; rep(i, 110) if (i != 0 && i != 1 && sz(g[i]) & 1) f = false; puts((sz(g[0]) & 1) && (sz(g[1]) & 1) && f ? "OK" : "NG");
一応コードも。
#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)) #define sz(x) (int)(x.size()) 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 aa, bb; signed main() { int a, b; while (cin >> a >> b) { aa.pb(a); bb.pb(b); } int ap = 0; int bp = 0; while (true) { vi g[110]; while (aa[ap] != 0 && bb[bp] != 0) { int a, b; a = aa[ap]; b = bb[bp]; ap ++; bp ++; a --; b --; g[a].pb(b); g[b].pb(a); } ap ++; bp ++; bool f = true; rep(i, 110) if (i != 0 && i != 1 && sz(g[i]) & 1) f = false; puts((sz(g[0]) & 1) && (sz(g[1]) & 1) && f ? "OK" : "NG"); if (ap == sz(aa)) return 0; else continue; } }
AOJ Kobutanukitsuneko
AOJ Kobutanukitsuneko
Kobutanukitsuneko | Aizu Online Judge
n個の文字列が与えられる。それらすべてを使ってしりとりができて、さらに最後に使った文字列の最後の文字が最初に使った文字列の最初の文字を一致させることが可能かどうかを判定する問題。x......yという文字列が与えられたときに、xからyへ有向辺を張り、できたグラフがオイラー閉路をなすかどうかを判定すれば良い。単にすべてを使ってしりとりができるか、という問題ならば、オイラー路をなすかどうかをみればよい。全体が連結であることを判定する必要もある。ワーシャルフロイドで最短経路を求めて連結性を確認したが、もっと単純にかけると思う。
Problem - D - Codeforces を解いたあとにやるとすごく易しく感じられる。スタートはどこからでもよく、オイラー路を出力する必要もないため、各ノードの相対次数のみ考えれば良い。
#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)) #define sz(x) (int)(x.size()) 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; } #define N 26 signed main() { int n; while (cin >> n) { if (n == 0) break; int deg[N] = { 0 }; vi g[N]; int start; bool yet = true; int d[N][N]; rep(i, N) rep(j, N) d[i][j] = INF; rep(i, N) d[i][i] = 0; int used[N] = { 0 }; rep(i, n) { string s; cin >> s; char ss = s[0]; char tt = s.back(); g[ss - 'a'].pb(tt - 'a'); d[ss - 'a'][tt - 'a'] = d[tt - 'a'][ss - 'a'] = 1; used[ss - 'a'] = used[tt - 'a'] = true; if (yet) { yet = false; start = ss - 'a';//適当にスタート決める } } rep(k, N) rep(i, N) rep(j, N) amin(d[i][j], d[i][k] + d[k][j]);//連結性確認のため bool f = true; rep(i, N) { rep(j, N) { if (used[i] && used[j]) { if (d[i][j] >= INF) { f = false;//連結でない } } } } rep(i, N) {//ノードiからみて deg[i] += sz(g[i]);//自身の次数をカウント（自身の出次数） rep(j, sz(g[i])) { deg[g[i][j]] --;//行き先の次数をカウント（行き先の入次数） } } rep(i, N) if (deg[i] != 0) f = false;//オイラー路でない puts(f ? "OK" : "NG"); } return 0; }
CF Round #288 Div.2 D. Tanya and Password
Codeforces Round #288 Div.2 D. Tanya and Password
長さ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; }
オイラー路は奥が深そう。
