https://agc021.contest.atcoder.jp/tasks/agc021_c
解法
https://agc021.contest.atcoder.jp/submissions/2134894
場合分けをして構築していく。
このような構築問題の戦略として「縦横の偶奇によって処理を分ける」という場合分け方針がある。
((解法が未証明だが)類題)
どのように場合分けするかは公式解説に書いてある。
公式解説通りに以下では置いてある(余分なタイルを取り除くのではなく、置けない場合は置いてない)
以下の実装はpastaさんのコードを参考にした。
本家は無茶苦茶短くてびっくりする。センスが光る。
int H, W, yoko, tate; string ans[2020]; //--------------------------------------------------------------------------------------------------- void yokooki(int y, int x) { if (yoko and ans[y][x] == '.' and ans[y][x + 1] == '.') { ans[y][x] = '<'; ans[y][x + 1] = '>'; yoko--; } } void tateoki(int y, int x) { if (tate and ans[y][x] == '.' and ans[y + 1][x] == '.') { ans[y][x] = '^'; ans[y + 1][x] = 'v'; tate--; } } //--------------------------------------------------------------------------------------------------- void _main() { cin >> H >> W >> yoko >> tate; rep(y, 0, H) rep(x, 0, W) ans[y] += "."; if (H % 2 == 1) { // y=0の上一列に「<>」を敷き詰める rep(x, 0, W / 2) yokooki(0, (W % 2) + x * 2); } if (W % 2 == 1) { // x=0の縦一列に「^v」を敷き詰める rep(y, 0, H / 2) tateoki((H % 2) + y * 2, 0); } if (2 < H and 2 < W and H % 2 == 1 and W % 2 == 1 and yoko % 2 == 1 and tate % 2 == 1) { // 左上を3*3をうまく配置する rep(x, 0, 3) rep(y, 0, 3) ans[y][x] = '.'; yoko++; tate++; yokooki(0, 0); yokooki(2, 1); tateoki(0, 2); tateoki(1, 0); } // 残りの部分は貪欲に縦縦か横横で2*2を埋めていく rep(x, 0, W / 2) rep(y, 0, H / 2) { if (yoko) { yokooki(y * 2 + (H % 2), x * 2 + (W % 2)); yokooki(y * 2 + (H % 2) + 1, x * 2 + (W % 2)); } else if (tate) { tateoki(y * 2 + (H % 2), x * 2 + (W % 2)); tateoki(y * 2 + (H % 2), x * 2 + (W % 2) + 1); } } if (yoko or tate) printf("NO\n"); else { printf("YES\n"); rep(y, 0, H) printf("%s\n", ans[y].c_str()); } }