※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

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

日記2013年3月~ - (2013/03/27 (水) 05:42:07) の編集履歴(バックアップ)


堀江 伸一
〒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人近辺かそれ以下の難問を自力で解いても、計算量が多くなると言ってもたかが知れているんだよな。
短時間でぱぱっと解かれることを想定してるから種一つ分かれば後は実装ゲー中心。
リンク先動画みたいに大量の砂粒のシミュレーションをする計算とか。
どこからこんな大量の物理系さんのいる問題の計算量を見つけ出してくるんだろうかと疑問になる。
こういう動画を見ると大学いっとけばよかったなと思ったり。
動画見てると表面的に浅くしか数学や物理を理解してない自分という現実が迫ってくるわけよね。
AOJの難問と言っても基本的に素朴に当たり前に言えることを探しだしてそこから処理手順の順序集合を決定してるだけだしな。
私の考えは底が浅い。
Wikiで数学の話なんか読むとどれだけ奥が深いのこの話、という気分になるし。
ロケット屋を横目に花火作ってる気分になる、、、