https://beta.atcoder.jp/contests/arc095
こいついっつも同じような記事書いてるな。
C
はい。
D
C(a,b) < C(c,b)(a < c)です。
E
列と行の操作は入れ替えることができます。なので行を全探索した後、点対称にできるかどうか列を見ればよいです。
いえば簡単ですがめちゃくちゃバグりやすいです。罠がたくさんあって結局通せなかった…
グラフっぽく言い換えると少しはマシになるかも。
if文もなるべく使わずにしてコンパクトにしたのがこれです。
int H, W; char S[12][12]; pi P[12]; bool visited[12]; bool same[12][12]; int creek(int v) { visited[v] = true; int res = 1; rep(i, 0, W) { if(!visited[i] && same[v][i]) { res += creek(i); } } return res; } bool ok() { // debug(vector<pi>(P, P + (H + 1) / 2)); char T[12][12]; int m1 = (H - 1) / 2, m2 = H / 2; rep(i, 0, (H + 1) / 2) { int a = P[i].fst, b = P[i].sec; rep(j, 0, W) { T[m1 - i][j] = S[a][j]; T[m2 + i][j] = S[b][j]; } } bool self[12]; memset(same, 0, sizeof(same)); memset(visited, 0, sizeof(visited)); memset(self, 0, sizeof(self)); rep(i, 0, W) { rep(j, 0, W) { bool ok = true; rep(k, 0, H) { if(T[H - k - 1][i] != T[k][j]) { ok = false; break; } } same[i][j] = ok; } } // rep(i, 0, W) { // rep(j, 0, W) { // cout << same[i][j]; // } // cout << "\n"; // } rep(i, 0, W) { if(same[i][i]) self[i] = true; } rep(i, 0, W) { if(self[i] || visited[i]) continue; if(creek(i) % 2) return false; } int odd = 0; rep(i, 0, W) { if(visited[i]) continue; odd += creek(i) % 2; } return odd <= 1; } bool used[12]; bool loop(int k) { if(k == (H + 1) / 2) { if(ok()) return true; else return false; } if(H % 2 == 1 && k == 0) { bool res = false; rep(i, 0, H) { P[k] = pi(i, i); used[i] = true; res |= loop(k + 1); used[i] = false; } return res; } bool res = false; int at = -1; rep(i, 0, H) { if(used[i]) continue; at = i; break; } used[at] = true; rep(i, 0, H) { if(used[i]) continue; used[i] = true; P[k] = pi(at, i); res |= loop(k + 1); used[i] = false; } used[at] = false; return res; } void solve() { cin >> H >> W; rep(i, 0, H) { rep(j, 0, W) { cin >> S[i][j]; } } if(loop(0)) cout << "YES\n"; else cout << "NO\n"; }
