はまやんはまやんはまやん

hamayanhamayan's blog

Tiling [AtCoder Grand Contest 021 C]

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());
    }
}