AtCoder ARC #082 : F - Sandglass

面倒ではあるけどこっちの方がオーソドックス。
https://beta.atcoder.jp/contests/arc082/tasks/arc082_d

問題

全体でXの砂が入っている砂時計がある。
初期状態で上側にあるパーツAにA、下側にあるパーツBをX-Aの量の砂が入っている。

この砂は1秒ごとに1だけパーツAの砂がパーツBに落ちる。
さて、砂時計をK通りひっくり返す時刻がR[i]として与えられる。
砂時計をひっくり返すと、パーツAとパーツBの砂が移動する方法が反転する。

ここでQ個のクエリが与えられる。
各クエリは初期パーツAの砂の量A[i]と時刻T[i]で構成される。
初期状態のパーツAの砂の量AがA[i]だったとすると、時刻T[i]にはパーツA側にどれだけの砂が入っているか。

解法

Aに対して、ある時刻tにおけるパーツA側の砂の量f(t,A)はAに対し以下のような関数になる。

• f(t,A) = x(t) (A≦pのとき)
• f(t,A) = x(t)+(A-p(t)) (p＜A＜qのとき)
• f(t,A) = x(t)+(q-p(t)) (A≧qのとき)

砂時計をひっくり返すタイミングにおけるx(t),p(t),q(t)の遷移を求めておこう。
後はクエリT[i]に対し最寄のtをもとにその時点のf(t,A)を求め、残り(T[i]-t)秒の分だけ砂を動かせばok。

int X;
int K;
map<ll,vector<int>> V;
map<int,int> M;
int Q,T,A;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>X>>K;
	vector<int> B={0,0,X,0};
	int pre=0;
	V[pre]=B;
	M[pre]=0;
	FOR(i,K) {
		cin>>x;
		int dif=x-pre;
		if(i%2==0) {
			
			if(B[2]<=dif) {
				B[0]=X;
				B[1]=B[2]=B[3]=0;
			}
			else {
				B[1]-=dif;
				B[2]-=dif;
				if(B[1]<0) {
					B[0]+=-B[1];
					B[1]=0;
				}
			}
		}
		else {
			if(B[1]+dif>=X) {
				B[0]=0;
				B[1]=B[2]=B[3]=X;
			}
			else {
				B[1]+=dif;
				B[2]+=dif;
				if(B[2]>X) {
					B[3]+=X-B[2];
					B[2]=X;
				}
			}
		}
		pre=x;
		V[pre]=B;
		M[pre]=(i%2)^1;
	}
	cin>>Q;
	while(Q--) {
		cin>>T>>A;
		auto it=V.lower_bound(T+1);
		it--;
		
		int p=it->first;
		vector<int> v=it->second;
		
		int cur=0;
		if(v[0]>=A) cur=v[1];
		else cur=min(v[2],v[1]+(A-v[0]));
		
		
		if(M[p]==0) cur-=T-p;
		else cur+=T-p;
		cout<<min(max(0,cur),X)<<endl;
	}
	
}

まとめ

Eは発想が要るけど、こっちは発想より実装が面倒なタイプか。
配点は一緒だけど、こっちの方が正答にたどり着きやすいよね。