Codeforces Global Round 6 : E. Spaceship Solitaire

いろいろ手間取って残念な結果だった回。
https://codeforces.com/contest/1266/problem/E

問題

N種類の資源があり、初期状態でいずれも0個である。
i番目の資源をA[i]個以上そろえた状態にしたい。
その際、以下のボーナスの追加・削除クエリが与えられる。

• S番目の資源をT個そろえると、U番目の資源が1個もらえる

1つ資源を作るのに1時間がかかるとすると、条件を満たすのにかかる最短時間はいくらか。

解法

基本的に、ボーナスがないとsum(A)だけ時間がかかる。
そこからボーナス1個に対し時間が1減る。
ただし、ある資源iに対するボーナス数がA[i]を超える場合、A[i]までしか得られない点に注意。

そうでない場合、常にボーナスを全部享受できる並びがあるので、このように単純化できる。

int N;
int A[202020];
int Q;
int S[201010],T[201010],U[201010];
ll P;
int B[201010];
map<int,int> M[201010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&N);
	FOR(i,N) {
		scanf("%d",&A[i+1]);
		P+=A[i+1];
	}
	scanf("%d",&Q);
	FOR(i,Q) {
		scanf("%d%d%d",&S[i],&T[i],&U[i]);
		if(M[S[i]].count(T[i])) {
			x=M[S[i]][T[i]];
			B[x]--;
			if(B[x]<A[x]) P++;
			M[S[i]].erase(T[i]);
		}
		if(U[i]) {
			M[S[i]][T[i]]=U[i];
			B[U[i]]++;
			if(B[U[i]]<=A[U[i]]) P--;
		}
		cout<<P<<endl;
	}
	
}

まとめ

解法はともかく、自信をもってsubmitするのに戸惑うよね…。