AtCoder AGC 038 A - 01 Matrix (緑色, 300 点)

これは天才パズル！！！

• 問題へのリンク

問題概要

のグリッドに 0, 1 の数値を書き込む方法であって、

• どの行をみても、それに含まれる 0 の個数と 1 の個数のうちの小さい方の個数が
• どの列をみても、それに含まれる 0 の個数と 1 の個数のうちの小さい方の個数が

を満たすものを構築せよ。不可能な場合はその旨を報告せよ。

制約

• 

考えたこと

とりあえず、「どの行をみても、0 と 1 の少ない方が 個」という状況は、下図のようにすれば実現できる。

つまり、どの行に対しても、以下のいずれかになるようにすれば、行に関する条件をクリアできる。

• 左 個が 0 で、右 個が 1
• 左 個が 1 で、右 個が 0

この段階ではまだ列に関する条件を考慮していないことに注意。しかし列に関しても、行と同様に、上から 個のところでラインを引けばよさそう。そうすると、次のような解が得られる。

いい感じにすべての条件を満たす解になっている！

#include <bits/stdc++.h>
using namespace std;

int main() {
    int H, W, A, B;
    cin >> H >> W >> A >> B;
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            if (i < B && j < A) cout << 0;
            else if (i >= B && j >= A) cout << 0;
            else cout << 1;
        }
        cout << endl;
    }
}