Codeforces ECR #099 : G. Forbidden Value

一件面倒くさそうだけど以外に素直？
https://codeforces.com/contest/1455/problem/G

問題

初期状態で変数Xの値が0である。
ここで、以下の命令からなるプログラムを考える。

• set y v : Xにyを代入する。ただし、コストvを掛けるとこの命令を無視できる。
• if y ... end : Xがyならif節内を処理する。else節はない。ifは再帰してもよい。

最終的にXがSとなることを避けたい。
必要総コストはいくつか。

解法

「Xがある値であるのにかかる最小コストはいくつか」をmapで保持して計算していこう。
if節に到達した段階でmapを分け、end節のところでそれらをマージしていく。

int N,S;
vector<ll> dif(1);
vector<multiset<ll>> ms(1);
vector<map<int,ll>> mi(1);


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	ms.back().insert(0);
	mi.back()[0]=0;
	while(N--) {
		cin>>s;
		if(s=="set") {
			cin>>x>>y;
			
			if(ms.back().empty()) continue;
			
			if(x==S) {
				dif.back()+=y;
			}
			else {
				ll cand=dif.back()+*ms.back().begin();
				if(mi.back().count(x)) {
					ms.back().erase(ms.back().find(mi.back()[x]));
				}
				dif.back()+=y;
				mi.back()[x]=cand-dif.back();
				ms.back().insert(mi.back()[x]);
			}
		}
		else if(s=="if") {
			cin>>x;
			if(mi.back().count(x)) {
				ll sc=mi.back()[x];
				ms.back().erase(ms.back().find(sc));
				mi.back().erase(x);
				mi.push_back(map<int,ll>());
				ms.push_back(multiset<ll>());
				mi.back()[x]=sc+dif.back();
				ms.back().insert(sc+dif.back());
				dif.push_back(0);
			}
			else {
				dif.push_back(0);
				mi.push_back(map<int,ll>());
				ms.push_back(multiset<ll>());
			}
		}
		else {
			x=mi.size();
			if(mi[x-1].size()>mi[x-2].size()) {
				swap(dif[x-2],dif[x-1]);
				swap(mi[x-2],mi[x-1]);
				swap(ms[x-2],ms[x-1]);
			}
			FORR2(k,v,mi[x-1]) {
				if(mi[x-2].count(k)) {
					ms[x-2].erase(ms[x-2].find(mi[x-2][k]));
					mi[x-2][k]=min(mi[x-2][k],dif[x-1]+v-dif[x-2]);
				}
				else {
					mi[x-2][k]=dif[x-1]+v-dif[x-2];
				}
				
				ms[x-2].insert(mi[x-2][k]);
			}
			dif.pop_back();
			mi.pop_back();
			ms.pop_back();
		}
	}
	ll ret=1LL<<60;
	FORR(d,mi[0]) ret=min(ret,d.second+dif[0]);
	cout<<ret<<endl;
}

まとめ

GのAC数少ないけど、Gが難しいというよりはE,Fが難しくて時間が残らなかった人が多そう。