kmjp's blog

競技プログラミング参加記です

UTPC 2013 : H - Asteroids2

うーむ、これは自力では知識がなくて解けん…。
http://utpc2013.contest.atcoder.jp/tasks/utpc2013_08

問題

二次元グリッド上のいくつかのマスに隕石がある。
i番目の隕石は(X[i],Y[i])に配置されており、A[i]~B[i]の間のエネルギーを当てることで破壊できる。

グリッドの各列には0~P[i]、各行には0~C[i]のエネルギーのレーザーを射出できる。
全隕石を破壊することができるか。

解法

各列に流すレーザーのエネルギーをe[i]、同じく各行にf[i]のエネルギーを流すとする。
すると以下の条件を満たせるか求める問題となる。

  • 0 ≤ e[i] ≤ P[i]
  • 0 ≤ f[i] ≤ Q[i]
  • A[i] ≤ e[X[i]] + f[Y[i]] ≤ B[i]

g[i]=-f[i]と符号を反転させ、かつZ=0固定の変数を導入すると、上記不等式はすべて2変数の不等式に置くことができる。

  • Z - e[i] ≤ 0
  • e[i] - Z ≤ P[i]
  • g[i] - Z ≤ 0
  • Z - g[i] ≤ Q[i]
  • e[X[i]] - g[Y[i]] ≤ B[i]
  • g[X[i]] - e[Y[i]] ≤ -A[i]

これら2変数の不等式は蟻本第2版p105にあるとおり、最短路探索問題に変換できるので、そこに負の閉路がないかチェックすればよい。
全変数はZと有向辺をもつので、Z=0から初めてZ<0とならないことを調べる。

このテクニックは一部ネット上などで牛ゲーとよばれているが、これは蟻本にあるとおり牛の問題でこの問題が題材となったからだろうか…?

int N,M;
vector<pair<int,int> > E[2001];
int C[2001];
 
void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>x;
		E[i].push_back(make_pair(2*N,x));
		E[2*N].push_back(make_pair(i,0));
	}
	FOR(i,N) {
		cin>>x;
		E[N+i].push_back(make_pair(2*N,0));
		E[2*N].push_back(make_pair(N+i,x));
	}
	FOR(i,M) {
		cin>>x>>y>>j>>k;
		x--,y--;
		E[x].push_back(make_pair(N+y,k));
		E[N+y].push_back(make_pair(x,-j));
	}
	
	FOR(i,2001) C[i]=3000000;
	C[N*2]=0;
	bool up=true;
	while(up) {
		up=false;
		FOR(i,2*N+1) {
			FOR(j,E[i].size()) if(C[E[i][j].first] > C[i]+E[i][j].second) {
				up=true;
				C[E[i][j].first] = C[i]+E[i][j].second;
			}
		}
		if(C[2*N]<0) return _P("no\n");
	}
	_P("yes\n");
}

まとめ

不等式をグラフ最短路にするテクは知らなかった…。
おまけにゼロ変数追加なんてますます思いつかん。
蟻本はちゃんとやり直さないとダメだな…。