Codeforces #185 Div1. C. Fetch the Treasure

これまた自力じゃ解けなかった問題。
http://codeforces.com/contest/311/problem/C

問題

左から1列に並んだマス目のうち、いくつかのマスにそれぞれの異なる価値のある宝がある。
ここで初期状態でプレイヤーは移動パラメータをK1個だけ持つ。
プレイヤーは、1マス目から、右方向に所持する移動パラメータ分だけ移動できる。

ここで以下のクエリを処理する。

• 移動パラメータxを追加
• xマス目の宝の価値をy減らす
• 1マス目から現状の移動パラメータ群で移動可能なマス目のうち、最も価値の高い宝を回収する

解法

クエリで追加される移動パラメータxはかなり大きいが、初期パラメータkは小さ目。
よって、まず各お宝を位置をmod Kした値で分類する。

以後、mod Kした各マス目のうち、到達可能な最短マスを管理する。
新規移動パラメータxが現れたら、到達可能な最短マスを更新する。この処理はO(K)で可能。
到達可能なマス目の宝は、価値の値をキーとするsetのmapで管理すればよい。

ll H;
int N,M,K;
int V[100001];
vector<pair<ll,int> > G[10001];
vector<ll> NM;
ll D[10001];
map<int,set<int> > B;

void dij(ll h) {
	int i,j,k;
	set<ll> q;
	NM.push_back(h);
	FOR(i,K) q.insert(D[i]);
	while(!q.empty()) {
		ll ke = *q.begin();
		q.erase(ke);
		if(ke>D[ke%K]) continue;
		FOR(i,NM.size()) {
			ll k2=ke+NM[i];
			int g = k2%K;
			if(D[g] > k2) {
				for(k=G[g].size()-1;k>=0;k--) {
					if(G[g][k].first<k2) break;
					B[-V[G[g][k].second]].insert(G[g][k].second);
				}
				D[g] = k2;
				G[g].resize(k+1);
				q.insert(k2);
			}
		}
	}
}

void solve() {
	int r,i,j,k,l, x,y;
	ll h;
	
	cin>>H>>N>>M>>K;
	FOR(i,N) {
		cin>>h>>V[i];
		h--;
		if(h%K==0) B[-V[i]].insert(i);
		else G[h%K].push_back(make_pair(h,i));
	}
	NM.push_back(K);
	FOR(i,K) sort(G[i].begin(),G[i].end());
	for(i=1;i<K;i++) D[i]=1LL<<60;
	
	FOR(i,M) {
		cin>>j;
		if(j==1) {
			cin>>h;
			dij(h);
		}
		else if(j==2) {
			cin>>x>>y;
			x--;
			if(B.find(-V[x])!=B.end() && B[-V[x]].find(x) != B[-V[x]].end()) {
				B[-V[x]].erase(x);
				if(B[-V[x]].empty()) B.erase(-V[x]);
				V[x]-=y;
				B[-V[x]].insert(x);
			}
			else V[x]-=y;
		}
		else {
			map<int,set<int> >::iterator it=B.begin();
			cout << -it->first << endl;
			it->second.erase(*it->second.begin());
			if(it->second.empty()) B.erase(it->first);
		}
	}
	
	return;
}

まとめ

先にmod Kして最短マスを管理するってのがコツだね。