Hatena::Grouptopcoder

cafelier@SRM

cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み

スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、

 | 

2012-07-03

二分探索

23:09 | はてなブックマーク - 二分探索 - cafelier@SRM

みなさま二分探索ってどういう風に考えながらコードを書くのでしょうか、ということがちょっと気になりました。特に実数ではなくて整数のもの。問題:

private int X = 1 以上 9_9999_9999 以下の秘密の整数;
bool query(int x) { return X <= x; }

X を直接読まずに query() 関数を何回か呼び出すことで X を求めなさい。

自分の場合、こう考えながら書いています。

int solve()
{
  int L = 0;            // 条件を満たさないとわかっている数を適当に
  int R = 10_0000_0000; // 条件を満たすとわかっている数を適当に

  // 不変条件: 「常に答えは半開区間 (L, R] の範囲にある」

以下、意地でもこの条件を崩さないことだけを念頭においてコーディング

以下、意地でもこの条件を崩さないことだけを念頭においてコーディング。(重要なので二回)

  while( R-L > 1 ) // 答えの範囲が整数一つになるまで繰り返し
  {
     int C = (L+R)/2; // 二分探索なので真ん中をとる
     (query(C) ? R : L) = C;
     // (query(C) ? L : R) = C; ではない。(L,R] が答えの範囲なので R が条件満たす方、L が満たさない方
  }
  return R; // 答えは (L,R] にあるのだから L じゃなくて R が答え
}

Topcoderにサブミットした二分探索のコード全部に半開区間の不変条件がコメントで書いてあります。これを念じていないと「ループ終了条件」「どっちの場合にLとRのどっちを更新するんだっけ?」「最後に返す値はどれ?」の3カ所で、USB端子の差し込み方向並に毎回迷ってしまうので。

チャレンジフェーズで他の人のコードを見ていると、違う考え方でコード書いている人が結構多いようなので興味が湧いています。if(query(C)) R=C; else L=C+1; みたいな形の更新式になるコードとか。気になります。

追記:反応集 http://togetter.com/li/331840

ほげほげ2012/07/04 00:51自分は while(L<R) で回して if(query(C)) R=C; else L=C+1; の更新式でした。
閉区間[L,R]で考えて、query(C) == false の時は C を閉区間から追い出して良いので次の範囲は[C+1,R]になる感じです。
ループ終了条件と返す値は分かり易いのですが、条件を満たす側が逆な場合等に丸め方向と更新式を変える必要があるのがネックでした。
半開区間の方が扱い易そうですね。

cafeliercafelier2012/07/04 02:21コメントありがとうございます。

> query(C) == false の時は C を閉区間から追い出し
こういう考え方を知りたかったのです!なるほど、閉区間で書くイメージもできてきました。

どのやり方も一長一短あるとは思うのですが、特にTopcoderで他人のコードを読むときに、自分のスタイルと違うのを見て詰まってしまう自分が勿体ないなあと思いまして。

cafeliercafelier2012/07/22 18:09「閉区間 & trueでもfalseでもmidを常に追い出す」という方針を教えていただいた。なるほど。
https://twitter.com/nabesan_tofu/status/226959241632690178
https://twitter.com/nabesan_tofu/status/226964459439136768

トラックバック - http://topcoder.g.hatena.ne.jp/cafelier/20120703
 | 

presented by cafelier/k.inaba under CC0