これ好き！

問題へのリンク

問題概要

$N \times N$ のグリッドがあって、"." と "O" と "X" のいずれかが描かれている。"O" または "X" の描かれているマス目の個数を $K$ とする。

今、いくつかのマスに対して、"O" または "X" のマス目の "OX" を入れ替える操作を行う。それによって「どの連続する 3 マス (縦横のみ, 斜めは除く) も "O" または "X" が連続していない」という状態にしたい。

ただし、操作を行うマスの個数は $K/3$ (切り下げ) 以下でなければならない。そのような操作を実施した結果を一つ示せ。

制約

テストケース数 $\le 100$
$N \le 300$

考えたこと

たとえば次のように、マス $(i, j)$ に対して

$i + j \pmod 3$ がある値のところはすべて "O"
$i + j \pmod 3$ が他のある値のところはすべて "X"

という状態にできたならば、他のマスがどうあろうと条件を満たす。

o . x o . x o
. x o . x o .
x o . x o . x
o . x o . x o
. x o . x o .
x o . x o . x
o . x o . x o

$i + j \pmod 3$ の値が 0, 1, 2 であって、"O", "X" であるものの個数を $a_{0, o}, a_{0, x}, a_{1, o}, a_{1, x}, a_{2, o}, a_{2, x}$ とする。このとき、鳩の巣原理より、

$a_{p, o} + a_{p, x} + a_{q, o} + a_{q, x} \le 2K/3$

を満たすように $(p, q)$ を選ぶことができる。さらに、 $p, q$ を適宜入れ替えることによって、

$a_{p, o} + a_{q, x} \le K/3$

を満たすようにできる。よって、

$i + j \equiv p \pmod 3$ であるような $(i, j)$ を "X" に
$i + j \equiv q \pmod 3$ であるような $(i, j)$ を "O" に

すれば OK。

コード

実装上は、6 通りの割当パターンを順に試して、変更箇所が $K/3$ 以下になるものを探索した。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(long long i = 0; i < (long long)(n); ++i)

int main() {
    int TTT; cin >> TTT;
    while (TTT--) {
        int N;
        cin >> N;
        vector<string> fi(N);
        for (int i = 0; i < N; ++i) cin >> fi[i];

        int num = 0;
        REP(i, N) REP(j, N) if (fi[i][j] != '.') ++num;

        auto solve = [&]() -> void {
            for (int maru = 0; maru < 3; ++maru) {
                for (int batu = 0; batu < 3; ++batu) {
                    if (maru == batu) continue;
                    int num2 = 0;
                    REP(i, N) REP(j, N) {
                        if ((i+j) % 3 == maru && fi[i][j] == 'X') ++num2;
                        if ((i+j) % 3 == batu && fi[i][j] == 'O') ++num2;
                    }
                    if (num2 <= num / 3) {
                        REP(i, N) REP(j, N) {
                            if ((i+j) % 3 == maru && fi[i][j] == 'X') fi[i][j] = 'O';
                            if ((i+j) % 3 == batu && fi[i][j] == 'O') fi[i][j] = 'X';
                        }
                        for (auto str : fi) cout << str << endl;
                        return;
                    }
                }
            }
        };
        solve();
    }
}

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

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

Codeforces Global Round 12 C2. Errich-Tac-Toe (R2300)

問題概要

制約

考えたこと

コード