[Codeforces] Codeforces Global Round 12 C1. Errich-Tac-Toe (Easy Version)
問題
方針
市松模様はマス \( i, j \) の色を \( (i + j) \bmod 2 \) の値で分けていますが、この問題では \( (i + j) \bmod 3 \) の値で分けるようです。整数 \( k\) を \( k = (i + j) \bmod 3 \) として、\( k = 0 \) のマスを赤、\( k = 1 \) のマスを緑、\( k = 2 \) のマスを青と塗り分けたとき、どの \( 3 \times 3 \) マスも赤、青、緑の個数は \( 3 \) マスとなります。
See the Pen Cell by ヤマカサ (@yamakasa33) on CodePen.
ある色を全て “O" に変えると、列または行に \( 3 \) つ連続して “X" が現れることはありません。\( k = (i + j) \bmod 3 \) となるマスが \( X \) である個数を \( g_k \) とし、"X" マスの数を \( m \) とすると、
\[ g_0 + g_1 + g_2 = m\]
となります。\( g_k \) の最小値の最大値は、
\[ g_0 = g_1 = g_2\]
のときなので、
\[ \min(g_k) \leq \left \lfloor \dfrac{m}{3} \right \rfloor\]
となります。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; int n; string c[300]; void solve() { int cnt[3]{}; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (c[i][j] == 'X') { cnt[(i + j) % 3]++; } } } int idx = 0; for (int i = 1; i < 3; i++) { if (cnt[idx] > cnt[i]) idx = i; } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (c[i][j] == 'X' && (i + j) % 3 == idx) { c[i][j] = 'O'; } } } for (int i = 0; i < n; i++) { cout << c[i] << "\n"; } } int main() { int t; cin >> t; while (t--) { cin >> n; for (int i = 0; i < n; i++) { cin >> c[i]; } solve(); } return 0; }
感想
こういう解き方があると学びました。
ディスカッション
コメント一覧
まだ、コメントがありません