AtCoder

ABC298 B問題(Coloring Matrix)を解く

AtCoder_ABC298_B

AtCoder が提供しているABC(AtCoder Beginner Contest)298 のB問題をC++とPythonで解いてみました。ABC298は、2023年4月15日21:00に実施されました。

この回は、外部からDDoS攻撃を受けてサーバが不安定になり unrated となりました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

B問題 Coloring Matrix

問題はリンク先をご覧ください。

ABC298 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」と判定されました。

最後に

この問題は、問題を斜め読みして難しいと考えて後回しにしていました。よく読めば回転操作も説明されていました。競技プログラミングは、時間との闘いの側面があります。問題を早く正確に読む必要があります。

ABC298 について、引き続き問題を紹介していきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA