面白かったけど、実際に実装するのは辛かった。
問題概要
のグリッドが与えられる。各マスを 2 または 5 で埋めたい。ただし以下の条件を満たすようにしたい。
- 2 が書かれたマスだけに着目し、上下左右斜め に隣接するマス同士に辺を張ったグラフを考えたとき、連結成分のサイズは全て 2
- 5 が書かれたマスだけに着目し、上下左右 に隣接するマス同士に辺を張ったグラフを考えたとき、連結成分のサイズは全て 5
これが可能かどうか判定し、可能ならば具体例を示せ。
制約
考えたこと
いかにも WA を連発しそうな問題。丁寧に場合分けして考える。簡単のため、 とする。
H = 1 のとき
- W = 2 であれば "22"
- W = 5 であれば "55555"
- W = 7 であれば "2255555"
などができる。より具体的には
- 2 スタートのとき W = 7k, 7k+2
- 5 スタートのとき W = 7k, 7k+5
ができることになる。
H = 2 のとき
5 5 2 5 5 5 5 5 5 2 5 5
みたいなパターンに注意する。しかしいずれにしても長方形全体でみると、
- 2, 5, 2, 5, ... と続く場合
- 5, 2, 5, 2, ... と続く場合
のいずれかしかない。しかし (2, 5, 2) とかは作れない。そもそも 2 + 5 + 2 = 9 は奇数だからだ。なので偶数のパターンを抜き出すと
- (2, 5, 2, 5), (2, 5, 2, 5), ...
- 2, (2, 5, 2, 5), (2, 5, 2, 5), ...
- 5, 2, 5, (2, 5, 2, 5), (2, 5, 2, 5), ...
の 3 パターンに絞られることがわかる。これらはいずれも実現できる。1 個目の場合は
5 5 2 5 5 5 2 | 5 5 2 5 5 5 2 | ... 5 5 5 2 5 5 2 | 5 5 5 2 5 5 2 | ...
という感じ。2 個目の場合は
2 | 5 5 2 5 5 5 2 | 5 5 2 5 5 5 2 | ... 2 | 5 5 5 2 5 5 2 | 5 5 5 2 5 5 2 | ...
という感じ。3 個目の場合は
5 5 2 5 5 5 | 2 5 5 2 5 5 5 | 2 5 5 2 5 5 5 | ... 5 5 5 2 5 5 | 2 5 5 5 2 5 5 | 2 5 5 5 2 5 5 | ...
という感じ。
H >= 3 のとき
あるの!?という感じだけど
5 5 2 2 5 2 2 5 5
という場合がある。これ以外はない。ないことの証明として、そもそも のときは「5 の連結成分」を区切る手段がないため、「5 の連結成分」はたかだか 1 個しか存在しえない。そんな中で という条件を満たしながら長方形を組み立てられるパターンが上の場合しかない。
まとめ
以上を丁寧に実装すると AC がもらえたのだけど、すごくゴチャゴチャしてしまい、さらには実装ミスで 2 WA してしまった。
#include <bits/stdc++.h> using namespace std; int H, W; vector<string> trans(vector<string> fi) { int N = fi.size(), M = fi[0].size(); vector<string> res(M, string(N, 'U')); for (int j = 0; j < M; ++j) for (int i = 0; i < N; ++i) res[j][i] = fi[i][j]; return res; } void solve() { bool tr = false; if (H > W) tr = true, swap(H, W); vector<string> res(H, string(W, 'U')); if (H == 1) { if (W % 7 == 0 || W % 7 == 5) { for (int w = 0; w < W; ++w) res[0][w] = "5555522"[w%7]; } else if (W % 7 == 2) { for (int w = 0; w < W; ++w) res[0][w] = "2255555"[w%7]; } } else if (H == 2) { if (W % 7 == 0 || W % 7 == 6) { for (int w = 0; w < W; ++w) res[0][w] = "5525552"[w % 7]; for (int w = 0; w < W; ++w) res[1][w] = "5552552"[w % 7]; } else if (W % 7 == 1) { for (int w = 0; w < W; ++w) res[0][w] = "2552555"[w % 7]; for (int w = 0; w < W; ++w) res[1][w] = "2555255"[w % 7]; } } else if (H == 3 && W == 3) res = {"255", "252", "552"}; if (res[0][0] == 'U') cout << "No" << endl; else { cout << "Yes" << endl; if (tr) res = trans(res); for (int i = 0; i < res.size(); ++i) cout << res[i] << endl; } } int main() { while (cin >> H >> W) { solve(); } }