【abc174-E】二分探索実装時のインデックス問題

※注意
いつも通り，この記事は主に自分の脳内整理および次回以降自分が使いやすいように書いているので，決して読みやすいものではないと思います．特に今日は1時間後に飲み会が控えていて，爆速一発書きのためおそらくこの傾向が顕著です．ご了承ください．

コンセプト

C++にはlower_boundやupper_boundといった魔法のような二分探索の関数があるが，これは事前にソートされた配列やvectorに対して作用させることしかできないという欠点がある．

たとえば，1以上N以下の自然数入力に対して，(特に広義)単調増加(減少)となるような関数 $f(n)$ があるとする．このとき，「この関数の出力がある値以上(以下)となるような，最小の入力値を求めよ」という問題を解きたいシーンは多い．もし全ての入力に対する関数の出力を格納した配列のようなものがあれば，それはlower_boundが突き刺さって見事に解決である．しかしそれがない場合，この魔法で二分探索を行うことはできない．N回関数を起動してlower_bound用の配列を作る，というのは明らかにナンセンスで，そもそもそんな暇があったらその過程で所望の答えが見つかっているはずである．(この配列を用意した上で，このあと多数のクエリに回答する，という状況ならこの限りではない)．

こういうときは自分で二分探索のアルゴリズムを実装してそこに関数 $f(n)$ を組み込めばいいわけだが，私はにぶたんするときいつもインデックスの細かいところが不安になって仕方がないので，ここで雛形を整理していざという時に取り出せるようにしておく．

background

これについて整理したきっかけは，abc-174-E(Log).Difficulty: 1158．
答えについて二分探索とかいう個人的にめちゃくちゃ反直感的な解法をギリギリまで出せなかった挙句，このインデックス問題にハマって時間内に通せなかったという苦い思い出．

結論

コードが全てを語ってくれることを期待してもう載せちゃいます．

abc174/e4.cpp

  int left = 1;
  int right = 1000000000;

  while(left<right) {
    int mid = (left+right)/2;
    if(f(mid) < k) {
      left = mid+1;
    }
    else if(f(mid) >= k) {
      right = mid;
    }
  }

  cout<<left<<endl;

ネット漁るといろんなバージョンが出てくるけど，個人的にはこれかなあ．関数 $f(n)$ は入力として1〜10^9 を許し，広義単調増加であるという想定(さっきのE問題は単調減少なんだけどね)．まあこれはあくまで雛形として．適当に言いたいことを箇条書きにしておくと

• whileループの終了条件は「leftとrightの一致」に等しい．
• left = mid+1; と right = mid; ．ここがメインコンテンツだと言ってもいい．こうすると，所望の値に等しい(けどインデックスは最小じゃない)位置にmidが来たとき，きちんと探索箇所は左にスライドする．leftくんは確実に正解の位置に近づいていき，leftとrightが1差のまま固まることもない(次の瞬間mid=leftとなり，このターンの値の更新で見事にleft==rightとなる)．
• あのE問題みたいにfが単調減少のときは，if，else ifの分岐の条件内の不等号の向きを入れ替えればよい．=は動かさなくていいよ．

こんな感じかなあ．どこまでいっても飲み会前なので，もう少し頭回して自分への信頼度を上げておく必要はあるけど．とりあえず現状これで不具合は確認されておりません．

ACコード

まあ貼らない理由もないので．abc174-EのACコードです．こうしてみると短いね．

abc174/e4.cpp

# include <bits/stdc++.h>
using namespace std;

int cut_times(int* logs, int n, int min_length) {
  int ans = 0;
  for(int i=0; i<n; i++) {
    ans += (logs[i]-1)/min_length;
  }

  return ans;
}

int main() {
  int n,k;
  cin>>n>>k;
  int a[n];
  for(int i=0; i<n; i++) cin>>a[i];

  int left = 1;
  int right = 1000000000;

  while(left<right) {
    int mid = (left+right)/2;
    if(cut_times(a,n,mid) > k) {
      left = mid+1;
    }
    else if(cut_times(a,n,mid) <= k) {
      right = mid;
    }
  }

  cout<<left<<endl;

  return 0;
}

おしまい

なんとか集合に間に合いそうでよかった．自分の理解はきちんと深まったので，今後もネットの海にこんな無責任な記事を投げるかもしれません．すみません．