AtCoder が提供しているABC（AtCoder Beginner Contest）386 D問題をC++とPythonで解いてみました。ABC386は、2024年12月28日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Diagonal Separation（Difficulty : 996）
問題の詳細は、リンク先をご覧ください。
ABC386 D問題 Diagonal Separation
黒マスが占める最小の領域を特定します。AtCoder Problems による Difficulty は 996 でした。
解答案
C++ プログラム例（ABC386D）
プログラムの補足です。
- $x$ の範囲が $1 \leqq x \leqq 10^9$ と広いため、座標圧縮を行います（15ー20行目）。
- 黒マスについて、同じ $x_i$ に対して最大の $y_i$ を求めます。これより $y$ が大きいマスは白マスと見なします（22ー27行目）。
- 次に、$x$ の値が大きい順に最大の $y$ の値を更新していきます。この操作により、ある $y_i$ に対して、これより $x_i$ が大きいマスは白マスと見なします。具体的な処理は、28行目から35行目のコードを参照してください。
- 最後に、白マスが黒マスの位置にないかを確認します（37ー44行目）。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
vector<int> x(m), y(m);
vector<char> c(m);
for (int i = 0; i < m; ++i) {
cin >> x[i] >> y[i] >> c[i];
}
// 座標圧縮
vector<int> nx = x;
sort(nx.begin(), nx.end());
nx.erase(unique(nx.begin(), nx.end()), nx.end());
for (int i = 0; i < m; ++i) {
x[i] = lower_bound(nx.begin(), nx.end(), x[i]) - nx.begin();
}
vector<int> right_b(nx.size(), -1);
for (int i = 0; i < m; ++i) {
if (c[i] == 'B') {
right_b[x[i]] = max(right_b[x[i]], y[i]);
}
}
int right_max = -1;
for (int i = (int)nx.size() - 1; i >= 0; --i) {
if (right_b[i] >= right_max) {
right_max = right_b[i];
} else {
right_b[i] = right_max;
}
}
bool result = true;
for (int i = 0; i < m; ++i) {
if (c[i] == 'W') {
if (y[i] <= right_b[x[i]]) {
result = false;
}
}
}
if (result) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC386D）
Python版も基本的な考え方は同じです。座標圧縮の操作はC++版を移植しました（13－15行目）。以下がプログラムです。
"""AtCoder Beginner Contest 386 D"""
import bisect
n, m = map(int, input().split())
x = [0] * m
y = [0] * m
c = [''] * m
for i in range(m):
tx, ty, c[i] = input().split()
x[i] = int(tx)
y[i] = int(ty)
nx = sorted(set(x))
for i in range(m):
x[i] = bisect.bisect_left(nx, x[i])
right_b = [-1] * len(nx)
for i in range(m):
if c[i] == 'B':
right_b[x[i]] = max(right_b[x[i]], y[i])
right_max = -1
for i in range(len(nx) - 1, -1, -1):
if right_b[i] >= right_max:
right_max = right_b[i]
else:
right_b[i] = right_max
result = True
for i in range(m):
if c[i] == 'W':
if x[i] <= y[i] <= right_b[x[i]]:
result = False
print("Yes" if result else "No")こちらも「AC」と判定されました。
最後に
このコンテストは私用で参加できませんでした。バーチャル参加しましたが、この問題は1行のコーディングミスにより解けませんでした。惜しい結果でした。
引き続き ABC の問題を紹介していきます。
