AtCoder ARC 176 A - 01 Matrix Again (1D, 水色, 400 点)

大敗してしまったので自戒を込めて。

• 問題へのリンク

問題概要

整数 が与えられる。 のグリッドであって、以下の条件を満たすものを構築せよ。

• 各マスの値は 0 または 1 である
• 個のマス の値はいずれも 1 である
• 行和はすべて である
• 列和はすべて である

制約

• 
• 

考えたこと

たとえば のときを考える。

以下の 5 種類の盤面は、

• いずれも「行和 = 1」「列和 = 1」である
• 盤面間で、1 であるマスが disjoint である

という性質を満たすことに着目しよう (赤マスを 1、白マスを 0 とする)。

これら 個の盤面の中から、 種類選んで結合する (各マスについて和をとる) と、「行和 = 」「列和 = 」となるのだ。

ここで、 種類の選び方を柔軟に変えれば、どんな入力 にも対応できる。

• マス が赤色になっている盤面
• マス が赤色になっている盤面
• マス が赤色になっている盤面

をそれぞれ選んでくればよいのだ。仮に被ったとしても、他のものを持ってくれば OK。

以上の方法は、一般の に対しても適用できる。なお、この解法は実は公式解説と同じである。

コード

#include <bits/stdc++.h>
using namespace std;
using pint = pair<int,int>;

int main() {
    int N, M;
    cin >> N >> M;
    
    // M 種類の盤面を選ぶ
    // 具体的にはマス (i, j) に対して、i + j mod N の値で類別する
    set<int> S;
    for (int i = 0; i < M; ++i) {
        int A, B;
        cin >> A >> B;
        --A, --B;
        S.insert((A + B) % N);
    }
    // 被った場合の処理
    for (int i = 0; i < N; ++i) {
        if (S.size() == M) break;
        if (!S.count(i)) S.insert(i);
    }
    
    // M 種類の盤面を結合する
    vector<pint> res;
    for (int i = 0; i < N; ++i) {
        for (auto r : S) {
            res.emplace_back(i, (r - i + N) % N);
        }
    }
    
    // 出力する
    cout << res.size() << endl;
    for (auto [x, y] : res) {
        cout << x+1 << " " << y+1 << endl;
    }
}