二分探索の無限ループから抜け出せない

Question

問題

AtCoder Beginner Contest 269 E問題

アプローチ

上下それぞれ10回までなら質問が出来るので、二分探索で左の境界から真ん中までのルークの数を聞き、その数が探索区間と同じ長さならそこには候補地はない為、左の境界を真ん中に移す、そうでなければ右の境界を真ん中にうつし、返ってきた数が0のときこそがまさしく求めたい行/列であると考える。

該当コード

#include <bits/stdc++.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define ll long long

void solve() {
    ll N; cin >> N;

    ll left = 1;
    ll right = N;
    ll y;
    while (true) {
        ll mid = (left + right) / 2;
        cout << "?" << " " << 1 << " " << N << " " << left << " " << mid << endl;
        ll T; cin >> T;
        if (T == 0) {
            y = mid;
            break;
        }
        else if (T == mid - left + 1) {
            left = mid + 1;
        }
        else {
            right = mid;
        }
    }

    ll top = 1;
    ll bottom = N;
    ll x;
    while (true) {
        ll mid2 = (top + bottom) / 2;
        cout << "?" << " " << top << " " << mid2 << " " << 1 << " " << N << endl;
        ll T; cin >> T;
        if (T == 0) {
            x = mid2;
            break;
        }
        else if (T == mid2 - top + 1) {
            top = mid2 + 1;
        }
        else {
            bottom = mid2;
        }
    }

    cout << "!" << " " << x << " " << y << endl;
}

int main() {
    solve();
}

質問

上のコードを通そうとすると、大型のケースでは「正解」でかつ「不正解」は出力されないものの、10個ほどのケースで時間切れを起こします。個人的には左右の境界の設定の仕方かwhileループの抜け出し方に問題があるとは疑っているのですが、具体的にどのような例においてループから抜けられないのかがわからずにいます。どこかお力添え頂ける箇所がございましたら、ご教授のほどよろしくお願い申し上げます。

Comments

[Zuishin]

1000 の要素で二分探索を行うとき、一回目のクエリで候補は最悪 500 になります。
同様に二回目のクエリで 250、三回目で 125、四回目で 63、五回目で 32、六回目で 16、七回目で 8、八回目で 4、九回目で 2、十回のクエリが終わって候補が 1 残っています。
つまり、T が 0 になるまで続けるのであれば、最悪 11 回のクエリを投げなくてはいけません。

Answer 1

問題の中に、以下の記述があります。

「質問の回数が 20 回を超えた場合は T は -1 となります。」

質問のコメントでZuishinさんが指摘している通り、こちらのコードだと質問の回数が20回を超える場合があり、その後のジャッジが常に-1を返し続けるので、無限ループになっているのでしょう。

ルークの置かれていない列は、必ずleftとrightの間にあるため、left == rightになれば、質問するまでもなくルークの数は0となります。こちらのパターンで質問をしないようにしてあげれば、質問回数が20回に収まるはずです。

具体的にどのような例においてループから抜けられないのか

具体的には、N=1000で、1行目・1列目にルークが置かれていない場合です。
こちらで実行経路をトレースすれば、問題を再現できると思われます。

Comments

[kay_ventris4]

ありがとうございます。補足していただいた内容で完全に理解することができました。ありがとうございました。

Answer 2

ループから抜ける条件が十分でないため模索範囲が1つに絞り込まれた時でもループが続く可能性があり、タイムアウトが発生する原因となります。

1. T == 0
2. T == mid - left + 1 (探索範囲内にルークが存在しない場合)
3. それ以外の場合は、探索範囲を狭める

ループから抜ける条件として
4. left == right
を追加することでループから抜けれらる条件が増えることでタイムアウトが解消すると考えられます。

Comments

[kay_ventris4]

仰る通り4を付け加えループ内に
if (left == right) {
　　y = left;
　　break;
}
を入れたところ（縦バージョンも同様）無事通りました。
一点可能であれば伺いたいのですが、自分としましてはT == 0の部分で上記の部分は既にカバーされているものと考えていました。この時どのような場合でT == 0ではループを抜ける条件として足らずleft == rightでのみ抜け出せるようになるのでしょうか？範囲を絞り込むところでは、最終的にルークが無い行または列に照準が合うようにしたので、それが理由で無限ループに陥ることはないと考えていたのですが。。何卒よろしくお願い申し上げます。

[Zuishin]

カバーされていないのは質問のコメントを読めばわかります。

[kay_ventris4]

ありがとうございます。計算量の見積もりの中で二分探索による候補の数を切り上げではなく切り捨てで計算していました。ありがとうございました。