Codeforces #218 Div2. D. Vessels

ここらへんがすらっと解けるようになった当たりは成長と言ってよいのか。
http://codeforces.com/contest/371/problem/D

問題

A[i]リットル入る器が縦に重なっている。
器に水を注いでいき、A[i]リットルからあふれた水は下のA[i+1]入る容器に行く。

A[i]が与えられた状態で、下記クエリを適宜対処せよ。

• i番目の器にP[i]リットル水を追加する
• i番目の容器に入っている水の容量を答える

解法

一度満タンになった器にはそれ以上水は追加できず、以降の水は次の器に注がれる。
よって、各器について「次に(恐らく)満タンになっていない器の番号」を覚えておくことで、すでに満タンになった器を繰り返し処理することを防ぐことができる。

たとえばA[i]に大量に水を注いでA[i]～A[j-1]までの器がいっぱいになり、A[j]に余裕があるなら、A[i]～A[j-1]は次の器はA[j]である、と覚えておく。
次にA[i]～A[j-1]に水を灌ぐ場合は、途中を飛ばしてA[j]から処理をすればよい。

一度いっぱいになった器は以降の処理でスキップできるので、全体の処理のオーダーはO(器数+クエリ数)で済む。

int N,M;
ll A[200001];
ll C[200001];
int ne[200001];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	FOR(i,N) C[i]=A[i],ne[i]=i+1;
	
	cin>>M;
	FOR(f,M) {
		cin>>x;
		if(x==1) {
			cin>>x>>y;
			vector<int> S;
			for(i=x-1;i<N;) {
				if(y<C[i]) {
					C[i]-=y;
					break;
				}
				else {
					S.push_back(i);
					y-=C[i];
					C[i]=0;
					i=ne[i];
				}
			}
			ITR(it,S) ne[*it]=i;
		}
		else {
			cin>>x;
			_P("%d\n",A[x-1]-C[x-1]);
		}
	}
	
}

まとめ

今回A～Dは1問10分ぐらいで解けてる。なかなか良いペースだ。