AtCoder が提供しているABC（AtCoder Beginner Contest）370 D問題をC++で解いてみました。ABC370は、2024年9月7日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Word Ladder（Difficulty : 1080）
問題の詳細は、リンク先をご覧ください。
壁がある場所を処理する問題ですが、データ構造を選びます。AtCoder Problems による Difficulty は 1080 でした。
解答案
壁がある場所をコンテナに格納して、以下の処理を行います。
- $(R_q, C_q)$ の場所に壁があれば、この壁を削除して次の爆弾を処理する。
- $(R_q, C_q)$ の場所に壁がなければ、四方に一番近い壁を削除する。
コンテナに求められる要件は以下です。
- 指定された場所に壁があるかないか効率的に計算できる。
- 指定された場所の上下左右にある一番近い壁の位置を効率的に計算できる。
- 指定された場所を削除することが効率的に計算できる。
C++では、平行二分探索木を使った set コンテナに、行と列毎に壁がある場所を格納すれば、上記の要件を満たします。
C++ プログラム例（ABC370D）
行毎の爆弾の位置 r_wall、列毎の爆弾の位置 c_wall を set コンテナの配列とします。配列のインデックスは、行または列の位置を表します（9、10行目）。このコンテナには、初期値として、すべてのグリッドの場所を格納します（11ー16行目）。
- find メソッドで、読み込んだ場所に壁があるか調べます（21行目）。
- 左右上下の一番近い壁を lower_bound、upper_bound メソッドを使って調べます。存在しない場合があります。例えば左の場合は、27から33行目で処理しています。
- どちらの場合も、爆破した壁を erase メソッドで削除します。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int h, w, q;
cin >> h >> w >> q;
vector<set<int>> r_wall(h + 1);
vector<set<int>> c_wall(w + 1);
for (int i = 1; i <= h; ++i) {
for (int j = 1; j <= w; ++j) {
r_wall[i].insert(j);
c_wall[j].insert(i);
}
}
for (int i = 0; i < q; ++i) {
int r, c;
cin >> r >> c;
if (r_wall[r].find(c) != r_wall[r].end()) {
r_wall[r].erase(c);
c_wall[c].erase(r);
continue;
}
// left
auto it = r_wall[r].lower_bound(c);
if (it != r_wall[r].begin()) {
--it;
int tc = *it;
r_wall[r].erase(tc);
c_wall[tc].erase(r);
}
// right
it = r_wall[r].upper_bound(c);
if (it != r_wall[r].end()) {
int tc = *it;
r_wall[r].erase(tc);
c_wall[tc].erase(r);
}
// up
it = c_wall[c].lower_bound(r);
if (it != c_wall[c].begin()) {
--it;
int tr = *it;
r_wall[tr].erase(c);
c_wall[c].erase(tr);
}
// down
it = c_wall[c].upper_bound(r);
if (it != c_wall[c].end()) {
int tr = *it;
r_wall[tr].erase(c);
c_wall[c].erase(tr);
}
}
int result = 0;
for (int i = 1; i <= h; ++i) {
result += r_wall[i].size();
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python の標準ライブラリには、C++ の set に該当する順序付き集合がありません。このため、Python 版のプログラムの紹介を見送ります。
最後に
自分にとっては難易度が高い問題でした。解くことができて良かったです。2回続けて水色パフォーマンスを出すことができました。
引き続き ABC の問題を紹介していきます。
