「日記2013年3月~」の編集履歴(バックアップ)一覧に戻る

日記2013年3月~ - (2013/03/22 (金) 12:55:32) の編集履歴(バックアップ)


堀江 伸一
〒675-0033-79-16

2013/3/21

AOJ 問題No 1507
Dungeon (II)
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1507
リンク先はダンジョンゲームをモチーフにしたプログラムの練習問題。
かなり前に挑戦して一度挫折、今回は2日がかりでこの問題を解きました。

最大20万部屋(n部屋)あるダンジョンがn-1本の通路でつながっている。
どの部屋からスタートしても他の部屋を経由してすべての部屋にいくことが出来る。
部屋には番号が振られており,1,,,nまで重複なく振られている。
i<jとなる部屋i~部屋jへの移動を考える。
最短経路で移動したとき、途中で通路の長さが最大になる通路を通るが、この通路の長さを部屋i~部屋jへの移動にかかるコストと定義する。
部屋のつながりと通路の距離のデータが与えられるので全てのi~jの移動による、コストの合計を答えよ。


解法
難しい問題です。
部屋iから部屋jへ移動するときのコストを求める関数をf(i,j)とするとこの関数が計算量1だったとしても200億回の計算が必要になります。
この手法ではコード実行時間が長くなりすぎて、問題で要請されている2秒以内の計算時間で答えをだせません。
なので上手にまとめて計算する工夫が必要になります。

この問題の解法のこつは、全てのi~jへの移動を行ったときの経路を考えるとき。
ある通路がある経路の最大値であるとは何かを考えることです。

一度全ての通路を切断して短い通路から繋げなおしていきます。
ある通路を繋げた時、その時点のつながりから
繋げた通路の片方の先にある部屋の数*もう片方の先にある部屋の数*その通路の距離
という式がその通路がその経路のコストになる条件を満たす経路達のコストの合計となります。

後はユニオン木もどきで高速化して片が付きます。

もっと速度が落ちるかと思ったらコード実行速度2位でした。
AOJの難問にしては珍しく正答者のコード実行速度のばらつきが少ないです。
皆のコードが同じタイムであることを考えると皆同じような考え方で解いたと思われます。
色々なかたが自分の考えた独自解法で解いた結果コード実行速度がばらつくのがAOJの特徴ですが、この問題は色々な解法がなかったようです。



#include<stdio.h>
#include<iostream>
#include<queue>

struct Way2{
	int a,b;
	long long int cost;
	bool operator<(const Way2& w)const{
		return cost>w.cost;
	}
}; 

const int size=200*1000+1;
long long int roomCount[size]={0};
int tree[size];
std::priority_queue<Way2> qu;

int saiki(int now,int newTop){
	int re;
	if(now==tree[now]){
		re=roomCount[now];
	}else{
		re=saiki(tree[now],newTop);
	}
	tree[now]=newTop;
	return re;
} 

 
int main(){
	int n,a,b,c;
 	long long int ans=0,sum=0,t1,t2;

	Way2 w2;
	scanf("%d",&n);
	for(int i=0;i<n-1;i++){
		scanf("%d %d %d",&a,&b,&c);
		if(a<b){
			w2.a=a;
 			w2.b=b;
		}else{
			w2.a=b;
			w2.b=a;
		}
		w2.cost=c;
		qu.push(w2);
	}
	for(int i=0;i<=n;i++){
		tree[i]=i;
		roomCount[i]=1;
 	}
	while(qu.empty()==false){
		w2=qu.top();
		qu.pop();
		t1=saiki(w2.a,w2.a);
		t2=saiki(w2.b,w2.a);
		roomCount[w2.a]=t1+t2;
		ans+=t1*t2*w2.cost;
	}
	std::cout<<ans<<"\n";
}








2013/3/22


どの道を何回通ったかと今いるポイントと今のタイムを基準に点を決めてグラフに翻訳すると点の数が物凄いことになるので単純なグラフで解いてはいけない。
1→3→1→2→1→3→1→2→1は
1→2→1→2→1と1→3→1→3→1に分解できる。
ということを利用して解けばいいんだろうけど。
正答者数を考えた時世間ではそんなに難しい問題に分類されてないはずなので色々考えてみます、、、

ここで気になる点は、グラフは木構造だという点です。
ある枝先を何回も往復して散歩した時、その枝先は一度で集中的に回り、回り終えたら2度と入らないと道を削除します。
これなら枝先を何回通ったかの情報がいらずタイムと得られた価値の組み合わせだけが必要な情報として手に入ります。
これを利用して解けそうなのですが、これを綺麗に処理する処理手順の順序集合が見えません。