AOJ 0254 : Scone スコーン配達計画 - 土下座しながら探索中

問題概要:
0以上の整数からなる数列と正の整数mが与えられる
数列の連続する部分列の総和%mの最大値を求めよ

解法:
BIT + 二分探索した（一時期は全探索で通った)
数列の累積和を求め、それらをmで割った余りがそれぞれどの位存在するかを数える
例えば、
m = 10 で数列が { 2,3,7,8} なら
累積和をとると 2 5 12 20 となり、
mでmodをとると 2 5 2 0 となる
ここから
0 1 2 3 4 5 6 ... ( index )
0 0 2 2 2 3 3 ... ( value ) <= これをBITで作成
入力で与えられた数列を0番目から昇順に、そこを最も左とする部分列の総和%mの最大値を求める
これは二分探索でもとまる
普通は 0 から m-1 のなかで存在するものの最大値を求めればよいが、
今回は数列の0番からの累積和になっているので、
[0,m-1]ではなく[(ここまでの総和)%m,(m-1 + (ここまでの総和)%m ) %m] の中で存在するものの最大値を求める
modをとっているので左の値 > 右の値とある場合があるので
そのときは範囲を２つに分ければ良い

余談:
二分探索がかけるようになりました　※ while(L+1

4 10
2 3 7 8
0 0

Sample Output 01:

Sample Input 02:

151 74391
10 10 8 10 3 11 1 11 5 2 5 8 11 4 2 7 2 5 6 8 4 7 7 6 1 1 4 4 5 6 4 3 5 9 10 5 8 10 4 10 10 8 4 7 10 5 1
1 11 9 5 5 11 10 9 5 10 9 8 3 11 11 4 3 4 10 1 8 6 9 10 4 5 4 7 11 11 9 10 8 4 2 1 3 11 7 7 7 3 1 7 2 10
 8 4 2 6 3 8 11 9 4 1 2 5 5 10 3 2 8 10 6 7 9 6 6 4 11 11 6 9 6 6 7 1 7 7 6 9 1 4 4 2 2 3 6 7 1 8 6 9 7 
9 2 2 4 8 5 1 5 9 9 
0 0

Sample Output 02:

Sample Input 03:

3 5
1 2 3
0 0

Sample Output 03:

コード:

#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 long long ll;
const int MAX_N = 31000;
const int MAX_M = 100010; 
int n,m,arr[MAX_N],mod_sum[MAX_N];
int bit[MAX_M];

int sum(int i) {
  ++i;
  int s = 0;
  while( i > 0 ){
    s += bit[i];
    i -= i & -i;
  }
  return s;
}

void add(int i,int x){
  ++i;
  while( i <= m ) {
    bit[i] += x;
    i += i & -i;
  }
}

int getMax(int L,int R){
  int target = sum(R);
  rep(_,65){
    int M = ( L + R ) / 2;
    if( sum(M) >= target ) R = M;
    else                   L = M;
  }
  if( L != R ) {
    int res = -1;
    if( sum(R) >= target ) res = R;
    if( sum(L) >= target ) res = L;
    assert( res != -1 );
    R = res;
  }
  if( R == 0 && sum(R) ) return 0;
  else if( R == 0 )      return -1;
  if( sum(R) - sum(R-1) ) return R;
  return -1;
}

inline int convert(int value,int sub){ return ( value - sub + m ) % m; }

void compute(){
  int maxi = 0;

  rep(i,n) if( arr[i] ) add(mod_sum[i],1), maxi = max(maxi,arr[i]);
  if( maxi == m-1 ) { printf("%d\n",maxi); return; }
  int sub = 0;
  
  rep(i,n) if( arr[i] ) {
    int low  = sub;
    int high = ( m - 1 + sub ) % m;

    if( low < high ) {
      int temp = getMax(low,high);
      if( temp != -1 ) maxi = max(maxi,convert(temp,sub));
    } else {
      int temp = getMax(low,m-1);
      if( temp != -1 ) maxi = max(maxi,convert(temp,sub));
      temp = getMax(0,high);
      if( temp != -1 ) maxi = max(maxi,convert(temp,sub));
    }
    ( sub += arr[i] ) %= m;
    add(mod_sum[i],-1);
    if( maxi == m-1 ) break;
  }
  printf("%d\n",maxi);
}

int main(){
  while( scanf("%d %d",&n,&m), n|m ){
    memset(bit,0,sizeof(bit));
    rep(i,n) {
      scanf("%d",arr+i);
      arr[i] %= m;
      if( i ) mod_sum[i] = ( mod_sum[i-1] + arr[i] ) % m;
      else    mod_sum[i] = arr[i];
    }
    compute();
  }
  return 0;
}