AtCoder が提供しているABC（AtCoder Beginner Contest）385 D問題をC++で解いてみました。ABC385は、2024年12月21日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Santa Claus 2（Difficulty : 1171）
問題の詳細は、リンク先をご覧ください。
特定のx座標を持つy座標の値と、特定のy座標を持つx座標の値を順序付きsetに格納して処理します。AtCoder Problems による Difficulty は 1171 でした。
解答案
サンタクロースが通過する経路上に家があるかを検索し、通過した場合は削除する必要があります。これらの操作を効率的に行うため、set コンテナを使用します。
C++ プログラム例（ABC385D）
プログラムを補足します。
- 家がある $(X_i, Y_i)$ の座標を X 座標と Y 座標で別々に格納します。具体的には、$X_i$ に対応する Y 座標を set コンテナ x[Xi] に格納します。逆に $Y_i$ に対応する X 座標を set コンテナ y[Y
i] に格納します（12ー17行目）。 - サンタクロースの位置は、(sx, sy) の値で管理します。
- 上方向に移動する場合（Di=’U’）、以下の操作をします。
- x[sx] に含まれる sy 以上の値を lower_bound を用いて探索します。
- もし、見つけた値が sy+Ci 以下であれば、その位置に家があることになります（28ー38行目）。
- 結果を格納する変数 result を増やします。
- lower_bound が返すイテレータをインクリメントして、次の値を処理します。
- 発見した家の座標を削除します。
- 最後に sy の値を更新します。
- 下方向や左右に移動する場合も、同様の処理を行います。実装はやや長くなりました。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
int n, m;
ll sx, sy;
cin >> n >> m >> sx >> sy;
map<ll, set<ll>> x, y;
for (int i = 0; i < n; ++i) {
ll xt, yt;
cin >> xt >> yt;
x[xt].insert(yt);
y[yt].insert(xt);
}
vector<char> d(m);
vector<ll> c(m);
for (int i = 0; i < m; ++i) {
cin >> d[i] >> c[i];
}
int result = 0;
for (int i = 0; i < m; ++i) {
if (d[i] == 'U') {
auto it = x[sx].lower_bound(sy);
while (it != x[sx].end()) {
if (*it <= sy + c[i]) {
++result;
int ty = *it;
++it;
x[sx].erase(ty);
y[ty].erase(sx);
} else {
break;
}
}
sy += c[i];
} else if (d[i] == 'D') {
auto it = x[sx].lower_bound(sy - c[i]);
while (it != x[sx].end()) {
if (*it <= sy) {
++result;
int ty = *it;
++it;
x[sx].erase(ty);
y[ty].erase(sx);
} else {
break;
}
}
sy -= c[i];
} else if (d[i] == 'L') {
auto it = y[sy].lower_bound(sx - c[i]);
while (it != y[sy].end()) {
if (*it <= sx) {
++result;
int tx = *it;
++it;
x[tx].erase(sy);
y[sy].erase(tx);
} else {
break;
}
}
sx -= c[i];
} else if (d[i] == 'R') {
auto it = y[sy].lower_bound(sx);
while (it != y[sy].end()) {
if (*it <= sx + c[i]) {
++result;
int tx = *it;
++it;
x[tx].erase(sy);
y[sy].erase(tx);
} else {
break;
}
}
sx += c[i];
}
}
cout << sx << " " << sy << " " << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python の ordered set について
Python の標準ライブラリには、C++ の set に相当する順序付き集合が存在しません。このため、Python 版のプログラムの紹介を見送ります。
以下のURL先に、公式解説Writerの実装が紹介されています。
最後に
当初、この問題を Vector コンテナを用いて実装したところ、TLE となりました。終了間際に set の使用を思いつき、コンテスト終了3分後に AC を得ることができました。悔しい思いをしましたが、勉強になりました。
引き続き ABC の問題を紹介していきます。
