CODE FESTIVAL 2014 上海 : H - Dungeon

なかなか面白い問題。
http://code-festival-2014-china-open.contest.atcoder.jp/tasks/code_festival_china_h

問題

0～(N+1)番の部屋が順に並んでいる。
1～N番の各部屋には以下の何れかがある。

• プレイヤーのHPをB[i]消費し、カギを１つ手に入れられる。
• カギを1つ消費し、プレイヤーの防御力をB[i]上昇させる道具を手に入れる。
• 攻撃力B[i]のモンスターがいる。プレイヤーのHPを(モンスターの攻撃力)-(プレイヤーの防御力)分消費し、モンスターを倒すことができる。
  • なお、プレイヤーの防御力がモンスターの攻撃力を上回ることはない。

モンスターのいる部屋は、一度モンスターを倒さないと通過できない。
一度モンスターを倒した部屋やその他の部屋は自由に行き来できる。
0番の部屋から(N+1)番の部屋に移動するのに必要な最小消費HPを求めよ。

解法

最大では各モンスターの合計攻撃力分だけHPを消費する。
あとはカギと道具を適切に取ることで、消費量を減らすことを考える。

これは最小コストフローで求めることができる。
sourceから各カギ、各カギから各道具、各道具からsinkへと有向辺を張ったグラフを考える。
sourceからカギと道具からsinkは容量1、コスト0の辺を張ればよい。
(なお、カギや道具を取らなくても良いので、sourceからsinkに容量無限の辺も張っておく)

カギxから道具yへは、そのカギと道具を得ることで削減できるHP消費量をコストとした辺を張ればよい。
コストの値は、鍵を取るのに必要なHP消費量B[x]から、カギと道具両方取った後に登場するモンスターの数×B[y]を引いたものである。
このコスト値は小さいほどよく、負の値の方が良い。

template<int NV,class V> class MinCostFlow {
public:
	struct edge { int to, capacity; V cost; int reve;};
	vector<edge> E[NV]; int prev_v[NV], prev_e[NV]; V dist[NV];
	void add_edge(int x,int y, int cap, V cost) {
		E[x].push_back((edge){y,cap,cost,(int)E[y].size()});
		E[y].push_back((edge){x,0, -cost,(int)E[x].size()-1}); /* rev edge */
	}
	
	V mincost(int from, int to, int flow) {
		V res=0; int i,v;
		ZERO(prev_v); ZERO(prev_e);
		while(flow>0) {
			fill(dist, dist+NV, numeric_limits<V>::max()/2);
			dist[from]=0;
			priority_queue<pair<V,int> > Q;
			Q.push(make_pair(0,from));
			while(Q.size()) {
				V d=-Q.top().first; int cur=Q.top().second;
				Q.pop();
				if(dist[cur]!=d) continue;
				if(d==numeric_limits<V>::max()/2) break;
				FOR(i,E[cur].size()) {
					edge &e=E[cur][i];
					if(e.capacity>0 && dist[e.to]>d+e.cost) {
						dist[e.to]=d+e.cost;
						prev_v[e.to]=cur;
						prev_e[e.to]=i;
						Q.push(make_pair(-dist[e.to],e.to));
					}
				}
			}
			
			if(dist[to]==numeric_limits<V>::max()/2) return -1;
			int lc=flow;
			for(v=to;v!=from;v=prev_v[v]) lc = min(lc, E[prev_v[v]][prev_e[v]].capacity);
			flow -= lc;
			res += lc*dist[to];
			for(v=to;v!=from;v=prev_v[v]) {
				edge &e=E[prev_v[v]][prev_e[v]];
				e.capacity -= lc;
				E[v][e.reve].capacity += lc;
			}
		}
		return res;
	}
};

MinCostFlow<1002,ll> mcf;
int N;
ll A[1000],B[1000];
ll M[1000],NK;
ll ret;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i]>>B[i];
	for(i=N-1;i>=0;i--) M[i]=M[i+1]+(A[i]==2);
	
	FOR(i,N) {
		if(A[i]==0) mcf.add_edge(0,10+i,1,0), NK++;
		if(A[i]==1) mcf.add_edge(10+i,1000,1,0);
		if(A[i]==2) ret+=B[i];
	}
	FOR(x,N) if(A[x]==0) {
		FOR(y,N) if(A[y]==1 && B[x]-M[max(x,y)]*B[y]<0) mcf.add_edge(10+x,10+y,1,B[x]-M[max(x,y)]*B[y]);
	}
	mcf.add_edge(0,900,NK,0);
	cout << ret+mcf.mincost(0,1000,NK) << endl;
}

まとめ

最小コストフローということに気づいてしまえば、グラフの形もわかりやすいシンプルな問題だね。