Codeforces 1370 D. Odd-Even Subsequence

こどふぉでした。

3完でした。

（二分探索といえばlower_boundや！って思ってたので）↓

二分探索とは

なるほど〜〜〜

探索条件について ok な範囲と ng の範囲を左右から伸ばしていくという感じですね

f:id:o-treetree:20200621200032p:plain

AtCoder灰・茶・緑色の方必見！二分探索を絶対にバグらせないで書く方法│FORCIA CUBE│フォルシア株式会社よりお借りしました

今回の「条件」

配列を端から見て、$s$ を作ってみる。

奇数番目(0-index)を $c$ 以下で構成できるかどうか偶数番目(0-index)を $c$ 以下で構成できるかどうか

奇数番目を $c$ 以下に抑えられるか判定するために

bool check(int c, int flag){
  int r=0; //作れる配列のサイズ
  for(int i=0; i<n; i++){
    if(r%2==flag || a[i]<=c){
      r++;
    }
  }
  return r>=k;
}

flag=0とする

r=偶数のときa[i]に関わらずrを増やす
a[i]が $c$ 以下のときrを増やす
それ以外はスルー

rをk以上にできるかどうかが判定条件

二分探索

めぐる式二分探索とかいうやつ

  int ok = 1e9;
  int ng = 0;

  while(abs(ok-ng)>1){
    int mid = (ok+ng)/2;
    if(check(mid,0) || check(mid,1)){
      ok = mid;
    }else{
      ng = mid;
    }
  }
  cout<<ok<<endl;

初期値について、$1\le a_i \le 10^{9}$ より

$s$ の偶数/奇数番目を $10^{9}$ 以下に抑えるのは常に可能
$s$ の偶数/奇数番目を $0$ 以下に抑えるのは常に不可能

というお気持ち。

完成

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

int n,k;
vector<int> a;
/* flag 通過 */
bool check(int c, int flag){
  int r=0; //作れる配列のサイズ
  for(int i=0; i<n; i++){
    if(r%2==flag || a[i]<=c){
      r++;
    }
  }
  return r>=k;
}

void solve(){
  cin>>n>>k;
  a.resize(n);
  rep(i,n)cin>>a[i];

  int ok = 1e9;
  int ng = 0;

  while(abs(ok-ng)>1){
    int mid = (ok+ng)/2;
    if(check(mid,0) || check(mid,1)){
      ok = mid;
    }else{
      ng = mid;
    }
  }
  cout<<ok<<endl;
}

int main(){
  int t = 1;
  //cin>>t;
  while(t--)solve();
}