面白かったけど、実際に実装するのは辛かった。

問題概要

$H \times W$ のグリッドが与えられる。各マスを 2 または 5 で埋めたい。ただし以下の条件を満たすようにしたい。

2 が書かれたマスだけに着目し、上下左右斜めに隣接するマス同士に辺を張ったグラフを考えたとき、連結成分のサイズは全て 2
5 が書かれたマスだけに着目し、上下左右に隣接するマス同士に辺を張ったグラフを考えたとき、連結成分のサイズは全て 5

これが可能かどうか判定し、可能ならば具体例を示せ。

制約

$1 \le H, W \le 2525$

考えたこと

いかにも WA を連発しそうな問題。丁寧に場合分けして考える。簡単のため、 $H \le W$ とする。

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

という場合がある。これ以外はない。ないことの証明として、そもそも $H \ge 3$ のときは「5 の連結成分」を区切る手段がないため、「5 の連結成分」はたかだか 1 個しか存在しえない。そんな中で $3 \le H \le W$ という条件を満たしながら長方形を組み立てられるパターンが上の場合しかない。

まとめ

以上を丁寧に実装すると 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();
    }
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

第6回ドワンゴからの挑戦状本選 2020 A - 2525敷き詰め (500 点)

問題概要

制約

考えたこと

H = 1 のとき

H = 2 のとき

H >= 3 のとき

まとめ