AtCoder が提供しているABC（AtCoder Beginner Contest）299 のD問題をC++とPythonで解いてみました。ABC299は、2023年4月22日21:00に実施されました。
この回は、外部からDDoS攻撃を受けてサーバが不安定になり unrated となりました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Find by Query（Difficulty : 763）
問題はリンク先をご覧ください。
二分探索を使ってインタラクティブな問題を解きます。AtCoder Problems による Difficulty は 763 でした。
解答案
インタラクティブな問題です。今回の記事は二分探索の基本が理解できていることを前提にしました。プログラムは、めぐる式と呼ばれる二分探索の実装を参考にしました。
次のコードパターンを使います。
- 関数 is_OK: 正しい条件を判定するように実装します。
- 関数 my_search: 二分探索を行います。
関数 my_search 内の変数 ng と ok は、半開区間 [ok, ng) を表しています。この区間の長さが1回の繰り返しで半分になり、ok と ng の差が 1 になれば終了となります。ok が調べたい値となります。
bool is_OK(int mid, int key)
{
return true;
}
int my_search(int key)
{
int ng = 0;
int ok = 1000000000;
while (abs(ok - ng) > 1) {
int mid = (ok + ng) / 2;
if (is_OK(mid, key)) {
ok = mid;
} else {
ng = mid;
}
}
return ok;
}C++ プログラム例（ABC299D）
今回は、二分探索で 0 → 1 と連続する場所を探します。制約から文字列の最初が 0 で、最後が 1 となります。このため、中間のどこかに少なくとも1か所、0 → 1 となる場所が存在します。
求める対象が簡単であるため、上記のコードパターンの引数 key は不要になりました。関数 my_search は、替わりに長さ N を渡すことにしました。結果的に、二分探索を使って 0 → 1 となる 0 の場所（関数 my_search で見つけた ok）を出力しています。
コードパターンの変化点の背景色を変更しました（引数の違いは無視します）。少ないコード量で、目的の二分探索が実装できています。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
bool is_OK(int mid)
{
int temp_s;
cout << "? " << mid << endl;
cin >> temp_s;
return temp_s == 0;
}
int my_search(int n)
{
int ng = n;
int ok = 1;
while (abs(ok - ng) > 1) {
int mid = (ok + ng) / 2;
if (is_OK(mid)) {
ok = mid;
} else {
ng = mid;
}
}
return ok;
}
int main()
{
int n;
cin >> n;
int result = my_search(n);
cout << "! " << result << endl;
return 0;
}めぐる式二分探索が優れているところは、条件の入れ替えが柔軟にできるところです。紹介したプログラムは、0 を正しいとしましたが、逆に 1 を正しいとしましょう。
変化点は以下となります。
- is_OK は、1 のときに true を返すように変更（10行目）
- my_search の ng と ok の値を入れ替える（15、16行目）。
- 0 → 1 となる 1 の場所を ok として返すため、解答で 1 を引いている（36行目）。
以下が、条件を入れ替えたプログラムとなります。
#include <bits/stdc++.h>
using namespace std;
bool is_OK(int mid)
{
int temp_s;
cout << "? " << mid << endl;
cin >> temp_s;
return temp_s == 1;
}
int my_search(int n)
{
int ng = 1;
int ok = n;
while (abs(ok - ng) > 1) {
int mid = (ok + ng) / 2;
if (is_OK(mid)) {
ok = mid;
} else {
ng = mid;
}
}
return ok;
}
int main()
{
int n;
cin >> n;
int result = my_search(n);
cout << "! " << result - 1 << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC299D）
C++のロジックをそのまま Python に書き直しました。
"""AtCoder Beginner Contest 299 D"""
def is_OK(mid):
print("?", mid)
temp_s = int(input())
return temp_s == 0
def my_search(n):
ng = n
ok = 1
while abs(ok - ng) > 1:
mid = (ok + ng) // 2
if is_OK(mid):
ok = mid
else:
ng = mid
return ok
n = int(input())
print("!", my_search(n))こちらも「AC」と判定されました。
最後に
初めて、インタラクティブな問題を解くことができました。不具合を起こしにくいコードパターンを再利用することもできました。新しいことができると楽しくなります。
引き続き ABC の問題を紹介していきます。
