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

「日記2013年3月~」の編集履歴(バックアップ)一覧に戻る
日記2013年3月~」を以下のとおり復元します。
堀江 伸一
〒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
[[ビートたけしのTVタックルという番組でこの前韓国問題が取り上げられてましたが]]



*2013/4/10 
AOJ0575に挑戦。

解法
とりあえず距離はダイクストラ法で求めるところまでは簡単。
問題はその先。
問題を展開してデータ処理手順に順序集合が適用できるよう組み立ててみたら何か間違ってたらしい、、、
何故か判らないが採点データ5で答えが一つだけあわない、、、
どうなってんだろ?



 #include<stdio.h>
 #include<vector>
 #include<queue>
 #include<algorithm>
 #include<map>
 #include<string.h>
 #include<stdlib.h>
 #include<stack>
 
 struct E{
	int no,len;
 	bool operator<(const E& e)const{
 		return len<e.len;
 	}
 }; 
 struct DE{
 	int no,len;
 	bool operator<(const DE& 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;
 bool spents[100001];
 
 void d(int n){
 	//ダイクストラ
 	int lens[100001];
 	memset(lens,-1,sizeof(lens));
 	
 	std::priority_queue<DE> pQ;
 	DE e,e2;
 	for(int i=0;i<G[0].size();i++){
 		e.no=G[0][i].no;
 		e.len=0;
  		pQ.push(e);
 	}
 	lens[0]=0;
 	
 	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.no=G[e.no][i].no;
 			e2.len=G[e.no][i].len+e.len;
 			if(lens[e2.no]==-1||(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);
 	}
 	for(int i=0;i<qs.size();i++){
 		ans[qs[i]]=0;//とりあえずダミーデータを入れておく
 	}
 	std::priority_queue<E> qu;
 	E e1=memos[0],e2;
 	for(int i=1;i<=n;i++){
 		if(memos[i].len>e1.len){
 			e1=memos[i];
 		}
 	}
 	
 	if(e1.len>0){
 		qu.push(e1);
 		spents[e1.no]=true;
 	}
 	int no=0;
 	std::map<int,std::vector<int> >::iterator it;
 	std::vector<int>::iterator itV;
 	std::vector<int> v;
 	std::map<int,int>::iterator it2;
 	
 
 	memset(cityNoToOrderNo,-1,sizeof(cityNoToOrderNo));
 	memset(spents,false,sizeof(spents));
 
 	while(qu.empty()==false){
 		e1=qu.top();
 		qu.pop();
 		for(it=minLenToCityList.lower_bound(e1.len);it!=minLenToCityList.end();it++){
 			for(itV=(*it).second.begin();itV!=(*it).second.end();itV++){
 				orderNoToMinLen.erase((*itV));
 			}
 		}
 		minLenToCityList.erase(minLenToCityList.lower_bound(e1.len),minLenToCityList.end());
 		cityNoToOrderNo[e1.no]=no;
 		orderNoToMinLen[no]=e1.len;
 		minLenToCityList[e1.len].push_back(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];
 			it2=orderNoToMinLen.lower_bound(oNo);
 			int tempLen=(*it2).second;
 			q1.from=e1.no;
  			q1.to=to;
 			ans[q1]=tempLen;
 			q1.from=to;
 			q1.to=e1.no;
 			ans[q1]=tempLen;
 			/*if(q1.from==3495&&q1.to==4398){
 				printf("\nlen=%d cNo=%d to=%d no=%d oNo=%d\n",e1.len,e1.no,to,no,oNo);
 				for(it2=orderNoToMinLen.begin();it2!=orderNoToMinLen.end();it2++){
 					printf("<%d %d>",(*it2).first,(*it2).second);
				}
 				printf("\n");
 			}*/
 		}
 		for(int i=0;i<G[e1.no].size();i++){
  			e2.no=G[e1.no][i].no;
 			e2.len=memos[e2.no].len;
 			if(spents[e2.no]==true)continue;
 			spents[e2.no]=true;	
 			qu.push(e2);
 		}
 		no++;
 	}
  	for(int i=0;i<qs.size();i++){
 		printf("%d\n",ans[qs[i]]);
 	}
 
 	/*
 	FILE *fp;	//(1)ファイルポインタの宣言
  	if ((fp = fopen("smpl.txt", "w")) == NULL) {
 		printf("file open error!!\n");
 		exit(EXIT_FAILURE);	// (3)エラーの場合は通常、異常終了する
 	}
 	for(int i=0;i<qs.size();i++){
 		fprintf(fp,"%d %d %d\n",qs[i].from,qs[i].to,ans[qs[i]]);
 	}
 	fclose(fp);
 	*/
 }




*2013/5/6
http://www.nicovideo.jp/watch/sm20697318
こういう動画見るとニコニコってアウトドア派も結構いるのかなと思ったりします。
チームで楽しそうですね。
http://blogs.yahoo.co.jp/sonicthe/31272665.html
うーんこういうページを見ると創作物で金を稼ぐって方法がどんなに大変かわかります。



*2013/5/10
2チャンネルで、アンパンマンを親子で見に言ったら親の私が泣いてしまったスレが共感を呼んで盛り上がったりしてるところを考えると。
2ちゃんも結構既婚者多いのかなとか思ったりする今日この頃。



*2013/5/14
[[2ちゃんねるはニートが多いかという質問をしたところ]]

[[フランス政府のカルト教団対策と創価学会の関係]]

[[ニコニコ動画ユーザーは皆あわれ?]]

[[新ギレン一年アムロベリハ92Tクリア方法]]

[[Prolog勉強記録]]

[[どうしても解けなかった数学の練習問題]]

復元してよろしいですか?