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; }
このビットで管理する感じの書き方はすごいなぁ。
