Codeforces 496D : Tennis Game

問題リンク : Problem - 496D - Codeforces

問題概要 :
2人でテニスをしたときの記録が与えられる
このテニスはsセット先取した人が勝利する
1セットはtポイント先取した人のものとなる
与えられた記録から考えられるsとtの組み合わせをすべて求めよ
記録の長さnは高々10^5

解法 :
1セットをとるために必要なポイント数tを全て試す
tが決まるとsも一意に定まる
tを決めた後は、player1とplayer2のどちらが先にt点をとるかをシュミレートしていく
愚直にやるとO(n^2)でTLEするので累積和と二分探索で高速化する
1回で記録をt進めるので、計算する回数はn + n/2 + n/3 + ...
これはO(nlogn)となるので結局, n * nlogn * logn となり間に合う

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef pair<int,int> ii;
vector<vector<int> > sum;
vector<int> arr;
int n;

bool check(int coef,int sp,int t,int player){
  int total = sum[sp+coef][player] - sum[sp-1][player];
  return total >= t;
}

int binarySearch(int sp,int t,int player){
  int L = 0, R = n-sp;
  while( L+1 < R ){
    int M = ( L + R ) / 2;
    if( check(M,sp,t,player) ) R = M;
    else                       L = M;
  }
  if( check(L,sp,t,player) ) return L;
  if( check(R,sp,t,player) ) return R;
  return -1;
}

int main(){
  vector<ii> answer;
  scanf("%d",&n);
  arr.resize(n+1,0);
  sum.resize(n+1,vector<int>(2,0));
  vector<int> next(n+1,-1);
  REP(i,1,n+1) scanf("%d",&arr[i]);
  REP(i,1,n+1) {
    --arr[i];
    sum[i][0] = sum[i-1][0] + !arr[i];
    sum[i][1] = sum[i-1][1] +  arr[i];
  }
  int winner = arr[n];
  for(int t=1;t<=n;t++){
    int win[2] = {0,0};
    int sp = 1;
    bool valid = true;
    while( sp <= n ){
      int pos[2];
      pos[0] = binarySearch(sp,t,0);
      pos[1] = binarySearch(sp,t,1);
      if( pos[0] != -1 ) pos[0] = sp + pos[0];
      if( pos[1] != -1 ) pos[1] = sp + pos[1];
      if( pos[0] == -1 || pos[1] == -1 ) {
        if( pos[0] == -1 && pos[1] == -1 ) break;
        if( pos[0] == -1 ) { ++win[1]; sp = pos[1]+1; }
        else               { ++win[0]; sp = pos[0]+1; }
      } else {
        assert( pos[0] != pos[1] );
        if( pos[0] < pos[1] ) { ++win[0]; sp = pos[0]+1; }
        else                  { ++win[1]; sp = pos[1]+1; }
      }
    }
    if( sp != n+1 ) valid = false;
    if( win[winner] <= win[!winner] ) valid = false;
    if( valid ) answer.push_back(ii(win[winner],t));
  }
  printf("%d\n",(int)answer.size());
  sort(answer.begin(),answer.end());
  answer.erase(unique(answer.begin(),answer.end()),answer.end());
  rep(i,(int)answer.size()) printf("%d %d\n",answer[i].first,answer[i].second);
  return 0;
}