AtCoder が提供しているABC（AtCoder Beginner Contest）269 のE問題をC++とPythonで解いてみました。ABC269は、2022年9月17日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 Last Rook（Difficulty : 1030）
問題はリンク先をご覧ください。
二分探索を使って空きマスを調べます。AtCoder Problems による Difficulty は、1030 でした。
解答案
チェス盤の大きさについて、$2 \leqq N \leqq 10^3$ という制約があります。空きマスについて、二分探索で調べれば、$2^{10} = 1024$ であるため、10回の問い合わせで範囲を十分に狭くすることができます。縦について最大10回、横について最大10回であるため、20回の質問で空きマスが特定できます。
C++ プログラム例（ABC269E）
プログラムの補足です。半開区間で考えるとひとつ違いミスをしにくくなります。
- 関数 check は、引数の情報で質問を行い、その応答を戻り値として返します。
- 先に上下を特定します。初期値 u = 1、d = n + 1、mid = (u + d) / 2 として、半開区間 [u, mid) について、調べます。
- 空きマスが前半にあれば、d = mid とします。
- 空きマスが後半にあれば、u = mid とします。
- どちらの場合も次の探索で [u, d) の半開区間について調べます。
- 次に左右を特定します。初期値 left = 1、right = n + 1 として、上下の場合と同じ処理をします。
- 空きマスの座標は、(u, left) となります。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int check(int a, int b, int c, int d)
{
int t;
cout << "? " << a << " " << b << " " << c << " " << d << endl;
cin >> t;
return t;
}
int main()
{
int n;
cin >> n;
int u = 1;
int d = n + 1;
while (d - u > 1) {
int mid = (d + u) / 2;
int t;
t = check(u, mid - 1, 1, n);
if (t < mid - u) {
d = mid;
} else {
u = mid;
}
}
int left = 1;
int right = n + 1;
while (right - left > 1) {
int mid = (left + right) / 2;
int t;
t = check(1, n, left, mid - 1);
if (t < mid - left) {
right = mid;
} else {
left = mid;
}
}
cout << "! " << u << " " << left << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC269E）
Python 版も基本的な考え方は同じです。以下となります。
"""AtCoder Beginner Contest 269 E"""
def check(a, b, c, d):
print("?", a, b, c, d)
t = int(input())
return t
n = int(input())
u = 1
d = n + 1
while d - u > 1:
mid = (d + u) // 2
t = check(u, mid - 1, 1, n)
if t < mid - u:
d = mid
else:
u = mid
left = 1
right = n + 1
while right - left > 1:
mid = (left + right) // 2
t = check(1, n, left, mid - 1)
if t < mid - left:
right = mid
else:
left = mid
print("!", u, left)こちらも「AC」と判定されました。
最後に
二分探索の処理ですが、インタラクティブな問題は、色半分から一色分難しくなる印象です。インタラクティブな問題も処理するアルゴリズムを本質的に理解していれば解くことができると考えています。
ABC269から、約1年ぶりにABCに復帰しました。解説記事をブログに紹介していることでABC参加も続いています。当時解けなかった問題も公式解説などを参考にしながら紹介していきます。
