kmjp's blog

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

TopCoder SRM 638 Div1 Hard CandleTimer、Div2 Hard CandleTimerEasy

SRM

１発正答ではないけど、なんとか自力で解けた。
http://community.topcoder.com/stat?c=problem_statement&pm=13356
http://community.topcoder.com/stat?c=problem_statement&pm=13519

問題

ある棒状の蝋燭がある。
この蝋燭は火をつけると時間１あたり長さ１燃える。
また、この蝋燭は両端から火をつけることもできる。

ここで、N本の蝋燭の端を連結し、木のグラフを成すようにした。

この木状の蝋燭群を使って、時間を測りたい。
そのため、任意の数の蝋燭の端点に同時に火を点け、蝋燭がすべて燃え尽きるまでの時間を測ることにした。

木を成した蝋燭群の連結状況と、各蝋燭の長さが与えられる。
この蝋燭群で測定可能な長さは何通りあるか。

解法

蝋燭が最後に燃え尽きるのは以下の２通りがある。

  • ある端点に火をつけた結果、別の(火をつけていない)端点が最後に燃え尽きる。
  • ある２つの端点に火をつけた結果、その中点が最後に燃え尽きる。

上記それぞれのケースを考え、そのような燃え方が可能か判定していけば良い。
なお、上記手順で中点を求める処理があるので、長さを倍にして偶数にそろえておくと良い。
また、最初にWarshall-Floyd方で全頂点間の距離D[x][y]を求めておく。

  • ある端点に火をつけた結果、別の(火をつけていない)端点が最後に燃え尽きる。
    • 端点Xにつけた火が最後に端点Yで燃え尽きるとする。その場合、端点Yが燃える時間はD[X][Y]である。よって他の領域はすべてD[X][Y]以下の時間で燃え尽きなければならない。
    • そのため、端点YがD[X][Y]未満の時間で燃えない場所、すなわちD[i][Y]≧D[X][Y]となる頂点iはすべて火をつけるものとする。
    • 頂点X及び上記頂点群iに火をつけると仮定し、ダイクストラなどで各頂点が燃える最短時刻を求める。
    • 各頂点群が燃える最短時刻から、各蝋燭が燃え尽きる時刻を同様に求める。
    • 各頂点群および蝋燭が燃える時刻がD[X][Y]以下であれば、D[X][Y]は測定可能である。
  • ある２つの端点に火をつけた結果、その中点が最後に燃え尽きる。
    • 端点XとYにつけた火がその中点で燃え尽きるとする。その場合、中点が燃える時間はD[X][Y]/2である。よって他の領域はすべてD[X][Y]/2以下の時間で燃え尽きなければならない。
    • まず、XとYの中点を含む蝋燭を求める。これはXとYの最短経路上であり、かつ両端からX,Yの近い方への距離がD[X][Y]/2以下である辺を求めればよい。この辺でXに近い方をP、Yに近い方をQとする。
    • あとは上記処理と似ている。QよりPに近い側の端点iについては、D[i][P]≧D[X][P]なら火をつける。Qに近い側の端点jについてはD[j][D]≧D[Y][Q]なら火をつける。
    • 上記同様にダイクストラ法を実行後、各頂点・蝋燭が燃え尽きる時刻がD[X][Y]/2以下であることをチェックすればよい。
set<int> S;
int dist[202][202];
vector<int> E[202];
int dist3[202];

class CandleTimer {
	public:
	int N;
	vector <int> A,B,len;
	
	int maxdist() {
		int i,x,y,j;
		int ma=0;
		
		priority_queue<pair<int,int> > P;
		FOR(i,N) if(dist3[i]==0) P.push(make_pair(0,i));
		
		while(P.size()) {
			pair<int,int> p=P.top();
			P.pop();
			int cur=p.second;
			if(p.first!=-dist3[p.second]) continue;
			FOR(i,E[cur].size()) if(dist3[E[cur][i]]>dist3[cur]+dist[cur][E[cur][i]]) {
				dist3[E[cur][i]] = dist3[cur]+dist[cur][E[cur][i]];
				P.push(make_pair(-dist3[E[cur][i]],E[cur][i]));
			}
		}
		
		FOR(i,N-1) {
			if(max(dist3[A[i]],dist3[B[i]])-min(dist3[A[i]],dist3[B[i]])>=len[i]){
				ma=max(ma,min(dist3[A[i]],dist3[B[i]])+len[i]);
			}
			else {
				ma=max(ma,(dist3[A[i]]+dist3[B[i]]+len[i])/2);
			}
		}
		return ma;
	}
	
	int differentTime(vector <int> A, vector <int> B, vector <int> len) {
		int i,x,y,z,j;
		
		N=A.size();
		FOR(i,N) len[i]*=2;
		
		this->A=A;
		this->B=B;
		this->len=len;
		
		
		S.clear();
		
		FOR(x,N+1) FOR(y,N+1) dist[x][y]=1<<29;
		FOR(i,N+1) E[i].clear();
		FOR(i,N) dist[A[i]][B[i]]=dist[B[i]][A[i]]=len[i];
		FOR(i,N) E[A[i]].push_back(B[i]),E[B[i]].push_back(A[i]);
		
		N++;
		
		FOR(i,N) dist[i][i]=0;
		FOR(i,N) FOR(x,N) FOR(y,N) dist[x][y]=min(dist[x][y],dist[x][i]+dist[i][y]);
		
		FOR(x,N) FOR(y,N) if(E[x].size()==1 && E[y].size()==1 && x!=y) {
			ll ma=dist[x][y];
			if(S.count(ma)) continue;
			
			FOR(i,N) dist3[i]=1<<29;
			FOR(i,N) if(E[i].size()==1 && dist[x][y]<=dist[i][y]) dist3[i]=0;
			
			if(maxdist()==ma) S.insert(ma);
		}
		
		FOR(x,N) for(y=x+1;y<N;y++) if(E[x].size()==1 && E[y].size()==1) {
			ll ma=dist[x][y]/2;
			if(S.count(ma)) continue;
			FOR(i,N-1) if(min(dist[x][A[i]],dist[x][B[i]])+len[i]+min(dist[y][A[i]],dist[y][B[i]])==dist[x][y]) {
				if(min(dist[x][A[i]],dist[x][B[i]])<=ma && min(dist[y][A[i]],dist[y][B[i]])<=ma) break;
			}
			int h1=A[i],h2=B[i];
			FOR(i,N) dist3[i]=1<<29;
			FOR(i,N) if(E[i].size()==1) {
				if(dist[i][h1]<dist[i][h2] && min(dist[x][h1],dist[y][h1])<=dist[i][h1]) dist3[i]=0;
				if(dist[i][h1]>dist[i][h2] && min(dist[x][h2],dist[y][h2])<=dist[i][h2]) dist3[i]=0;
			}
			if(maxdist()==ma) S.insert(ma);
		}
		
		
		return S.size();
	}
}

まとめ

最後に燃え尽きる場所が、どこかの端点か２端点の中間であることまでは推測できるが、そこからの実装が地味にめんどい。
とはいえ面白い発想の問題で良かった。