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

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

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

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

問題概要

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

  • 各マスの値は 0 または 1 である
  •  M 個のマス  (A_{0}, B_{0}), \dots, (A_{M-1}, B_{M-1}) の値はいずれも 1 である
  • 行和はすべて  M である
  • 列和はすべて  M である

制約

  •  N \le 10^{5}
  •  M \le \min(N, 10)

考えたこと

たとえば  N = 5, M = 3 のときを考える。

以下の 5 種類の盤面は、

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

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

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

ここで、 5 種類の選び方を柔軟に変えれば、どんな入力  (A_{0}, B_{0}), (A_{1}, B_{1}), (A_{2}, B_{2}) にも対応できる。

  • マス  (A_{0}, B_{0}) が赤色になっている盤面
  • マス  (A_{1}, B_{1}) が赤色になっている盤面
  • マス  (A_{2}, B_{2}) が赤色になっている盤面

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

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

コード

#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;
    }
}