AtCoder が提供しているABC（AtCoder Beginner Contest）298 のB問題をC++とPythonで解いてみました。ABC298は、2023年4月15日21:00に実施されました。
この回は、外部からDDoS攻撃を受けてサーバが不安定になり unrated となりました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
B問題 Coloring Matrix
問題はリンク先をご覧ください。
与えられた行列を回転して条件を満たすか確認する問題です。AtCoder Problems による Difficulty は算出されていません。B問題としては難しい問題だと思います。
解答案
$N$ と行列 $A$、$B$ を読み込み、$A$ を回転して $A_{i, j} = 1$ であるすべての $(i, j)$ について、$B_{i, j} = 1$ であるか確認します。
$A$ を回転するとは、問題で以下と説明されています。問題と異なり添え字は 0 から始めています。
$0 \leqq i, j < N$ を満たす $(i, j)$ に対して、同時に $A_{i,j}$ を $A_{N – 1 – j, i}$ で置き換える。
C++ プログラム例（ABC298B）
行列 $A$ を回転する機能を関数 rot として分けました。関数 rot では、別の行列 $T$ を定義して、回転した $A$ を $T$ に代入して、その後で、$T$ を $A$ に代入しています（4-18行目）。
回転させながら条件を満たすか確認します。条件を満たすことが分かれば、”Yes” を出力してプログラムを終了します（47-49行目）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
void rot(vector<vector<int>>& a)
{
int n = a.size();
vector<vector<int>> t(n, vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
t[i][j] = a[n - 1 - j][i];
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
a[i][j] = t[i][j];
}
}
}
int main()
{
int n;
cin >> n;
vector<vector<int>> a(n, vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cin >> a[i][j];
}
}
vector<vector<int>> b(n, vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cin >> b[i][j];
}
}
bool result;
for (int n_rot = 0; n_rot < 4; ++n_rot) {
result = true;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if ((a[i][j] == 1)&&(b[i][j] == 0)) {
result = false;
}
}
}
if (result) {
cout << "Yes" << endl;
return 0;
}
rot(a);
}
cout << "No" << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC298B）
Python 版は、C++版を移植しました。一致した時点で、”Yes” を出力して、sys.exit しています（2、33行目）。
"""AtCoder Beginner Contest 298 B"""
import sys
def rot(a):
n = len(a)
t = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
for j in range(n):
t[i][j] = a[n - 1 - j][i]
for i in range(n):
for j in range(n):
a[i][j] = t[i][j]
n = int(input())
a = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
a[i] = list(map(int, input().split()))
b = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
b[i] = list(map(int, input().split()))
result = True
for n_rot in range(4):
result = True
for i in range(n):
for j in range(n):
if a[i][j] == 1 and b[i][j] == 0:
result = False
if result:
print("Yes")
sys.exit()
rot(a)
print("No")こちらも「AC」と判定されました。
最後に
この問題は、問題を斜め読みして難しいと考えて後回しにしていました。よく読めば回転操作も説明されていました。競技プログラミングは、時間との闘いの側面があります。問題を早く正確に読む必要があります。
引き続き ABC の問題を紹介していきます。
