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

日記2013年3月~ - (2013/04/10 (水) 14:59:21) の編集履歴(バックアップ)


堀江 伸一
〒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

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2491
猫のそらの散歩を題材にしたグラフ理論の問題。

これ難しいなあ。

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

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

一応上記考えでコードを書いてみましたが。
駄目でした。
18個目あたりのジャッジデータでタイムリミッドくらいます。
そらまあ最悪の計算量が2500万*300=75億回.
普通のコードならちょっと遅いねで済みますが、競技プログラムでは遅いではすみません。
通るわけがないのですが今のところこれより賢い方法を思いつかない状態です。
これはいい考えを思いつくまで一度諦めた方がいいかも。

この問題は1から出発して木を精査していくことで解けました。
親猫を1に置き探索猫をどれかの道に向かわせます。
探索猫は辿りついた場所が枝先でないなら親猫となってこの広場に居座ります。
親猫は探索猫を一匹作り、道の先に向かわせこれを連鎖させます。
枝先にたどり着いたらその広場に入る道を往復した結果得られる価値と距離の対応表を親猫に返します。
親猫は探索猫が持ち帰った対応表を使って自分の持ってる価値と距離の対応表をより良い結果に更新します。
調べてない道がまだ残ってるなら、親猫は自分の対応表を持たせて探索猫をその道に向かわせ上記と同じ作業を繰り返します。
親猫は全ての道を探索猫に探索させ終わったら自分の得た対応表を親猫に返します。
この時、自分の通った道を何度か往復した場合を考慮に入れた対応表を返せば答えとなります。





2013/3/27

https://www.youtube.com/watch?v=ZoZ0ZAzr6eg
こういう動画を見ると恥ずかしくて死にたくなるな。
自分がやってるAOJの問題は、種が分かれば後は簡単に解けることが多い問題が多い。
正答者数20人近辺かそれ以下の難問を自力で解いても、計算量が多くなると言ってもたかが知れているんだよな。
短時間でぱぱっと解かれることを想定してるから種一つ分かれば後は実装ゲー中心。
リンク先動画みたいに大量の砂粒のシミュレーションをする計算とか。
どこからこんな大量の計算量をCPUから見つけ出してくるんだろうかと疑問になる。
こういう動画を見ると大学いっとけばよかったなと思ったり。
動画見てると表面的に浅くしか数学や物理を理解してない自分という現実が迫ってくるわけだ。
AOJの難問と言っても基本的に素朴に当たり前に言えることを探しだして、それを基底に処理手順の順序集合を決定してるだけだしな。
基本私の考えは底が浅い。
Wikiで数学の話なんか読むとどれだけ奥が深いのこの話、という気分になるし。
世間がロケット作ってるのを横目に私はおもちゃの花火作ってる気分になる、、、



2013/4/2




2013/4/10

AOJ0575に挑戦。

解法
とりあえず距離はダイクストラ法で求めるところまでは簡単。
問題はその先。
問題を展開して順序集合をつけてnlognで計算できるようにしてみたら処理手順の構造が複雑になった。
そのうえ変数の使用量が増えてきたので、メモリが足りるかどうか難しいところ。
これは多分どこかで処理を書き間違えてる可能性大だから今日中の提出は無理だな。
メモリ21万キロバイト使えたら安心して処理を掛けるのだが。

#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>

struct E{
	int no,len;
	bool operator<(const E& e)const{
		return len<e.len;
	}
};

struct Q{
	int from,to;
	bool operator<(const Q& q)const{
		if(from!=q.from)return from<q.from;
		return to<q.to;
	}
}; 

std::vector<E> G[100001];
E memos[100001];
std::vector<int> qsList[100001],nowQs[100001];
std::vector<Q> qs;
std::map<Q,int> ans;
int cityNoToOrderNo[100001];
std::map<int,int> orderNoToMinLen;
std::map<int,std::vector<int> > minLenToCityList;


void d(int n){
	//ダイクストラ
	int lens[100001];
	memset(lens,-1,sizeof(lens));
	memset(cityNoToOrderNo,-1,sizeof(cityNoToOrderNo));
	std::priority_queue<E> pQ;
	for(int i=0;i<G[0].size();i++)pQ.push(G[0][i]);
	lens[0]=0;
	E e,e2;
	while(!pQ.empty()){
		e=pQ.top();
		pQ.pop();
		if(lens[e.no]!=-1&&e.len>lens[e.no])continue;
		lens[e.no]=e.len;
		for(int i=0;i<G[e.no].size();i++){
			e2=G[e.no][i];
			e2.len+=e.len;
			if(lens[e2.no]==-1||(lens[e2.no]>e2.len)){
				lens[e2.no]=e2.len;
				pQ.push(e2);
			}
		}
	}
	//for(int i=0;i<=n;i++)printf("%d , ",lens[i]);
	for(int i=1;i<=n;i++){
 		memos[i].no=i;
		memos[i].len=lens[i];
 	}
} 


int main(){
	int n,m,k,q,a,b;

	scanf("%d %d %d %d",&n,&m,&k,&q);
	E e;
	for(int i=0;i<m;i++){
		scanf("%d %d %d",&a,&b,&e.len);
		e.no=b;
		G[a].push_back(e);
		e.no=a;
 		G[b].push_back(e);
}
 	//街0という架空の町を作り祭りがおこなわれているのは全部この町と距離0でつながってるとする
//これにより祭りの距離は街0からの距離という問題に置き換えることが出来る
	for(int i=0;i<k;i++){
		scanf("%d",&a);
		e.no=a;
		e.len=0;
		G[0].push_back(e);
	}
	d(n);
	int from,to;
	Q q1;
	for(int i=0;i<q;i++){
		scanf("%d %d",&from,&to);
		q1.from=from;
		q1.to=to;
		qs.push_back(q1);
 		qsList[from].push_back(to);
		qsList[to].push_back(from);
	}
	std::priority_queue<E> qu;
	E e1=memos[0];
	E e2;
	for(int i=1;i<=n;i++){
		if(memos[i].len>e1.len){
			e1=memos[i];
		}
	}
	if(e1.len>0){
		qu.push(e1);
	}else{
		for(int i=0;i<qs.size();i++){
			ans[qs[i]]=0;
		}
 	}
int no=0;
 	std::map<int,int>::iterator it;
	while(qu.empty()==false){
		e1=qu.top();
		qu.pop();
		std::map<int,std::vector<int> >::iterator it;
		for(it=minLenToCityList.lower_bound(e1.len);it!=minLenToCityList.end();it++){
			for(std::vector<int>::iterator itV=(*it).second.begin();itV!=(*it).second.end();itV++){
				orderNoToMinLen.erase(*itV);
			}
		}
		
		cityNoToOrderNo[e1.no]=no;
		orderNoToMinLen[no]=e1.len;
 		minLenToCityList[e1.len].push_back(e1.no);
		
		for(int i=0;i<qsList[e1.no].size();i++){
			int to=qsList[e1.no][i];
			nowQs[to].push_back(e1.no);
		}
		for(int i=0;i<nowQs[e1.no].size();i++){
			int to=nowQs[e1.no][i];
			int oNo=cityNoToOrderNo[to];
			std::map<int,int>::iterator it=orderNoToMinLen.lower_bound(oNo);
			q1.from=e1.no;
			q1.to=to;
			ans[q1]=(*it).second;
 			q1.from=to;
			q1.to=e1.no;
			ans[q1]=(*it).second;
		}
		for(int i=0;i<G[e1.no].size();i++){
			e2.no=G[e1.no][i].no;
 			e2.len=memos[e2.no].len;
			qu.push(e2);
		}
		no++;
	}
}