D - Max Median

• Quiz
  • https://codeforces.com/contest/1486/problem/D
• AC
  • https://codeforces.com/contest/1486/submission/107889074
• 解説
  • editorialの通りですが、なんとなくKは小さい方が大きいmedianが見つかる気がして、長さKのみ調べればいい気がしますが、間違いです
  • Kを伸ばすことでより良いmedianが得られる場合があります
  • 私がナイーブ解と突き合わせて見つけたテストケースを置いておきます

testcase

10 6
8 3 5 7 1 9 1 6 10 10

Answer : 7

• K=6で全てのmedianを調べるだけだと答えは6になりますが、K=7で後端7つのmedianをとると、より良いmedian 7が得られます
• なのでeditorialのように累積和とそれの先端からのmin配列を使う必要があります

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N,K;
    cin>>N>>K;

    VI A(N);
    rep(i, N) cin >> A[i];

    ll ma = MAX(A);

    auto f = [&](ll x){
      auto B = A;
      rep(i,N){
        if(B[i]>=x){
          B[i]=1;
        }else{
          B[i]=-1;
        }
      }

      VI Acc = {0};
      for(ll b : B)Acc.push_back(b);
      rep(i,N){
        Acc[i+1] += Acc[i];
      }

      auto AccMin = Acc;
      rep(i,N){
        AccMin[i+1] = min(AccMin[i], AccMin[i+1]);
      }

      FOR(i,K,N+1){
        ll a = Acc[i];
        ll b = AccMin[i-K];
        ll v = a-b;
        if(v>0)return true;
      }
      return false;
    };

    ll left=1;//can
    ll right=ma+1;//can't

    while(left+1!=right){
      ll center = (left+right)/2;
      if(f(center)){
        left=center;
      }else{
        right=center;
      }
    }
    p(left);
    
    return 0;
}