AtCoder が提供しているABC（AtCoder Beginner Contest）273 のD問題をC++とPythonで解いてみました。ABC273は、2022年10月15日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 LRUD Instructions（Difficulty : 1119）
問題はリンク先をご覧ください。
壁の場所を二分探索して、指示を処理していきます。AtCoder Problems による Difficulty は、1119 でした。
解答案
壁の情報を行と列に分けて格納する必要があります。$2 \leqq H, W \leqq 10^9$ であるため、配列では、メモリが足りなくなります。連想配列（map）を使って、行または列の番号と vector コンテナを組で格納します。
二分探索により壁を探して、左右上下の指示を処理します。また、行の情報には、0 と $W+1$ を、列の情報には、0 と $H+1$ を番兵として格納します。この工夫により範囲外アクセスの確認を減らすことができています。
C++ プログラム例（ABC273D）
上記で考察した手順をプログラムにしました。左右上下の操作をそれぞれ記述しているため、プログラムは少し長くなりました。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int h, w, rs, cs;
cin >> h >> w >> rs >> cs;
int n;
cin >> n;
set<int> in_r;
set<int> in_c;
map<int, set<int>> r;
map<int, set<int>> c;
for (int i = 0; i < n; ++i) {
int rt, ct;
cin >> rt >> ct;
in_r.insert(rt);
r[rt].insert(ct);
r[rt].insert(0);
r[rt].insert(w + 1);
in_c.insert(ct);
c[ct].insert(rt);
c[ct].insert(0);
c[ct].insert(h + 1);
}
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
char d;
int L;
cin >> d >> L;
switch (d) {
case 'L':
if (in_r.find(rs) != in_r.end()) {
auto it = r[rs].lower_bound(cs);
--it;
if (*it < cs - L) {
cs = cs - L;
} else {
cs = *it + 1;
}
} else {
cs = max(cs - L, 1);
}
break;
case 'R':
if (in_r.find(rs) != in_r.end()) {
auto it = r[rs].upper_bound(cs);
if (cs + L < *it) {
cs = cs + L;
} else {
cs = *it - 1;
}
} else {
cs = min(cs + L, w);
}
break;
case 'U':
if (in_c.find(cs) != in_c.end()) {
auto it = c[cs].lower_bound(rs);
--it;
if (*it < rs - L) {
rs = rs - L;
} else {
rs = *it + 1;
}
} else {
rs = max(rs - L, 1);
}
break;
case 'D':
if (in_c.find(cs) != in_c.end()) {
auto it = c[cs].upper_bound(rs);
if (rs + L < *it) {
rs = rs + L;
} else {
rs = *it - 1;
}
} else {
rs = min(rs + L, h);
}
break;
}
cout << rs << " " << cs << endl;
}
return 0;
}上記のプログラムでは、set コンテナを使いましたが、vector コンテナを使って要素をソートすることによっても、実現できます。
主な差分コードの背景色を変更しています。以下が vector コンテナを使ったプログラムです。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int h, w, rs, cs;
cin >> h >> w >> rs >> cs;
int n;
cin >> n;
set<int> in_r;
set<int> in_c;
map<int, vector<int>> r;
map<int, vector<int>> c;
for (int i = 0; i < n; ++i) {
int rt, ct;
cin >> rt >> ct;
in_r.insert(rt);
r[rt].push_back(ct);
in_c.insert(ct);
c[ct].push_back(rt);
}
for (auto e : in_r) {
r[e].push_back(0);
r[e].push_back(w + 1);
sort(r[e].begin(), r[e].end());
}
for (auto e : in_c) {
c[e].push_back(0);
c[e].push_back(h + 1);
sort(c[e].begin(), c[e].end());
}
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
char d;
int L;
cin >> d >> L;
switch (d) {
case 'L':
if (in_r.find(rs) != in_r.end()) {
auto it = lower_bound(r[rs].begin(), r[rs].end(), cs);
--it;
if (*it < cs - L) {
cs = cs - L;
} else {
cs = *it + 1;
}
} else {
cs = max(cs - L, 1);
}
break;
case 'R':
if (in_r.find(rs) != in_r.end()) {
auto it = upper_bound(r[rs].begin(), r[rs].end(), cs);
if (cs + L < *it) {
cs = cs + L;
} else {
cs = *it - 1;
}
} else {
cs = min(cs + L, w);
}
break;
case 'U':
if (in_c.find(cs) != in_c.end()) {
auto it = lower_bound(c[cs].begin(), c[cs].end(), rs);
--it;
if (*it < rs - L) {
rs = rs - L;
} else {
rs = *it + 1;
}
} else {
rs = max(rs - L, 1);
}
break;
case 'D':
if (in_c.find(cs) != in_c.end()) {
auto it = upper_bound(c[cs].begin(), c[cs].end(), rs);
if (rs + L < *it) {
rs = rs + L;
} else {
rs = *it - 1;
}
} else {
rs = min(rs + L, h);
}
break;
}
cout << rs << " " << cs << endl;
}
return 0;
}どちらも AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC273D）
Python 版では、map に相当する機能として defaultdict を、二分探索に相当する機能として、bisect モジュールを使いました。
基本的な考え方は、C++ と同じです。以下が Python プログラムとなります。
"""AtCoder Beginner Contest 273 D"""
from collections import defaultdict
import bisect
h, w, rs, cs = map(int, input().split())
n = int(input())
in_r = set()
in_c = set()
r = defaultdict(list)
c = defaultdict(list)
for i in range(n):
rt, ct = map(int, input().split())
in_r.add(rt)
r[rt].append(ct)
in_c.add(ct)
c[ct].append(rt)
for e in in_r:
r[e].append(0)
r[e].append(w + 1)
r[e].sort()
for e in in_c:
c[e].append(0)
c[e].append(h + 1)
c[e].sort()
q = int(input())
for i in range(q):
d, L = input().split()
L = int(L)
if d == 'L':
if rs in in_r:
t = bisect.bisect_left(r[rs], cs)
t -= 1
if r[rs][t] < cs - L:
cs = cs - L
else:
cs = r[rs][t] + 1
else:
cs = max(cs - L, 1)
elif d == 'R':
if rs in in_r:
t = bisect.bisect_right(r[rs], cs)
if cs + L < r[rs][t]:
cs = cs + L
else:
cs = r[rs][t] - 1
else:
cs = min(cs + L, w)
elif d == 'U':
if cs in in_c:
t = bisect.bisect_left(c[cs], rs)
t -= 1
if c[cs][t] < rs - L:
rs = rs - L
else:
rs = c[cs][t] + 1
else:
rs = max(rs - L, 1)
elif d == 'D':
if cs in in_c:
t = bisect.bisect_right(c[cs], rs)
if rs + L < c[cs][t]:
rs = rs + L
else:
rs = c[cs][t] - 1
else:
rs = min(rs + L, h)
print(rs, cs)Python 版も「AC」と判定されました。
最後に
1年前のコンテストでは、この問題は解けそうにありませんでした。
今回、問題を読み直したところ、二分探索を使って解けることが分かりました。実装は重めで、プログラムを書くためには時間がかかりましたが、AC 判定を得ることができました。
引き続き ABC の問題を紹介していきます。
