AtCoder が提供しているABC(AtCoder Beginner Contest)390 C問題をC++とPythonで解いてみました。ABC390は、2025年1月25日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Paint to make a rectangle(Difficulty : 247)
問題の詳細は、リンク先をご覧ください。
ABC390 C問題 Paint to make a rectangle
先にすべての黒マスが入る長方形を求めます。AtCoder Problems による Difficulty は 247 でした。
解答案
黒マスが存在する座標 $(i, j)$ に対して、$i$ の最小値と最大値、$j$ の最小値と最大値を求めることによって、すべての黒マスが入る長方形を求めることができます。
次に、この長方形内に白マスが存在する場合、塗り替えてもすべてを黒マスにすることはできません。
C++ プログラム例(ABC390C)
すべての黒マスが入る長方形を特定して(13ー26行目)、その長方形に白マスがあるかを確認します(28ー35行目)。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int h, w;
cin >> h >> w;
vector<string> s(h);
for (int i = 0; i < h; ++i) {
cin >> s[i];
}
int min_h = h;
int max_h = -1;
int min_w = w;
int max_w = -1;
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
if (s[i][j] == '#') {
min_h = min(min_h, i);
max_h = max(max_h, i);
min_w = min(min_w, j);
max_w = max(max_w, j);
}
}
}
bool result = true;
for (int i = min_h; i <= max_h; ++i) {
for (int j = min_w; j <= max_w; ++j) {
if (s[i][j] == '.') {
result = false;
}
}
}
if (result) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}
AC(Accepted=正しいプログラム)と判定されました。
Python プログラム例(ABC390C)
Python版も基本的な考え方は同じです。以下がプログラムです。
"""AtCoder Beginner Contest 390 C"""
h, w = map(int, input().split())
s = [input() for i in range(h)]
min_h, max_h = h, -1
min_w, max_w = w, -1
for i in range(h):
for j in range(w):
if s[i][j] == '#':
min_h = min(min_h, i)
max_h = max(max_h, i)
min_w = min(min_w, j)
max_w = max(max_w, j)
result = True
for i in range(min_h, max_h + 1):
for j in range(min_w, max_w + 1):
if s[i][j] == '.':
result = False
print("Yes" if result else "No")
こちらも「AC」と判定されました。
最後に
前処理に関しては、ABC269B問題(解説記事)でも取り上げていました。
引き続き ABC の問題を紹介していきます。