質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.44%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

2回答

1116閲覧

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

kay_ventris4

総合スコア269

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

0クリップ

投稿2023/04/30 21:16

編集2023/04/30 21:17

問題

AtCoder Beginner Contest 269 E問題

アプローチ

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

該当コード

C++

1#include <bits/stdc++.h> 2#include <math.h> 3#include <algorithm> 4using namespace std; 5#define ll long long 6 7void solve() { 8 ll N; cin >> N; 9 10 ll left = 1; 11 ll right = N; 12 ll y; 13 while (true) { 14 ll mid = (left + right) / 2; 15 cout << "?" << " " << 1 << " " << N << " " << left << " " << mid << endl; 16 ll T; cin >> T; 17 if (T == 0) { 18 y = mid; 19 break; 20 } 21 else if (T == mid - left + 1) { 22 left = mid + 1; 23 } 24 else { 25 right = mid; 26 } 27 } 28 29 ll top = 1; 30 ll bottom = N; 31 ll x; 32 while (true) { 33 ll mid2 = (top + bottom) / 2; 34 cout << "?" << " " << top << " " << mid2 << " " << 1 << " " << N << endl; 35 ll T; cin >> T; 36 if (T == 0) { 37 x = mid2; 38 break; 39 } 40 else if (T == mid2 - top + 1) { 41 top = mid2 + 1; 42 } 43 else { 44 bottom = mid2; 45 } 46 } 47 48 cout << "!" << " " << x << " " << y << endl; 49} 50 51int main() { 52 solve(); 53}

質問

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

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

Zuishin

2023/04/30 22:19

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

回答2

0

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

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

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

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

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

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

投稿2023/05/01 13:18

編集2023/05/01 13:28
actorbug

総合スコア2268

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

kay_ventris4

2023/05/01 13:27

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

0

ベストアンサー

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

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

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

投稿2023/04/30 22:14

jp-seemore.com

総合スコア62

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

kay_ventris4

2023/05/01 11:40

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

2023/05/01 12:29

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

2023/05/01 13:27

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.44%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問