square869120Contest #3 : F - 寿司 / Sushi

これは自力で解けた。
http://s8pc-3.contest.atcoder.jp/tasks/s8pc_3_f

問題

N人の客がおり、先頭から1～Nの番号がついている。
以下の操作を計Q回行う。

各操作はA[i],B[i]の２値で表現される。
1～A[i]の番号のうち、これまで食べた寿司の数が最小で、かつそのうち番号の若い順に寿司を１つ食べさせる、という動作をB[i]回繰り返す。

全操作の終了後、各人の食べた寿司の数を求めよ。

解法

各人の食べた寿司の数をC[i]とする。
この手順では、C[i]は常に単調減少となる。

よってi回目の処理では、C[A[i]]が常に最小値と等しい。
xをC[x]=C[i]である最小値とする(Cは単調減少なのでこれは二分探索で求められる)
x～iの各人にB[i]/(i-x+1)個ずつ寿司を配り、あまりをxから順に１個ずつ配るか、もしくはその前にC[x-1]=C[x]=C[i]となるだけ配ってしまった場合、xを更新してまたその処理を繰り返せばよい。

以下のコードでは数列の向きを反転させてBITを二分探索して処理を行っている。

template<class V, int ME> class BIT {
public:
	V bit[1<<ME],val[1<<ME];
	V total(int e) {V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	V add(int e,V v) { val[e++]+=v; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
	V set(int e,V v) { add(e,v-val[e]);}
	int lower_bound(V val) {
		V tv=0; int i,ent=0;
		for(i=ME-1;i>=0;i--) if(tv+bit[ent+(1<<i)-1]<val) tv+=bit[ent+(1<<i)-1],ent+=(1<<i);
		return ent;
	}
};

int N,Q;
ll A,B;
BIT<ll,18> bit;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	bit.add(N,2LL*10000000000001LL);
	FOR(i,Q) {
		cin>>A>>B;
		x=N-A;
		while(B) {
			ll xv=bit.total(x);
			y = bit.lower_bound(xv+1);
			ll yv=bit.total(y);
			
			
			if(B>=(yv-xv)*(y-x)) {
				B -= (yv-xv)*(y-x);
				bit.add(x,yv-xv);
				bit.add(y,-(yv-xv));
			}
			else {
				bit.add(x,B/(y-x));
				bit.add(y,-B/(y-x));
				B %= (y-x);
				bit.add(y-B,1);
				bit.add(y,-1);
				break;
			}
		}
	}
	
	FOR(i,N) cout<<bit.total(N-1-i)<<endl;
}

まとめ

1200ptの問題を解けたのは初めてかも？