「AOJ1500～1509」の編集履歴（バックアップ）一覧はこちら

「AOJ1500～1509」(2013/05/01 (水) 11:51:05) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

*問い1500　ID
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1500
条件を満たすＩＤが幾通りあるか答える問題。

解法
-*の数も少なくメモ化で一発です。


 #include<stdio.h>
 #include<string.h>
 char id[100001];
 int memo[100001][10];
 int main(){
 	
 	int n,m,a;
 	int base2[10]={0,2,4,6,8,1,3,5,7,9};
 	bool oks[10]={0,0,0,0,0,0,0,0,0,0};
 	scanf("%d %s",&n,id);
 	scanf("%d",&m);
	for(int i=0;i<m;i++){
  		scanf("%d",&a);
		oks[a]=true;
  	}
 
 	memset(memo,0,sizeof(memo));
 	memo[0][0]=1;
 	for(int i=1;i<=n;i++){
 		char c=id[n-i];
 		if(c=='*'){
 			for(int j=0;j<=9;j++){
 				for(int k=0;k<=9;k++){
 					if(oks[k]==true){
 						if(i%2==0)memo[i][(j+base2[k])%10]+=memo[i-1][j];
 						else memo[i][(j+k)%10]+=memo[i-1][j];
 					}
 				}
 			}
 		}else{
 			for(int j=0;j<=9;j++){
 				if(i%2==0)memo[i][(j+base2[c-'0'])%10]+=memo[i-1][j];
 				else memo[i][(j+(c-'0'))%10]+=memo[i-1][j];
 			}
 		}
 　	}
 　	printf("%d\n",memo[n][0]);
 }








*1501 Grid
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1501
上端下端、左端右端がつながったマップで二点の間を最短距離で移動したとき何通りのルートがあるか。
解法
上下左右に斜めの８方向に向かった場合の最短距離を検討して後はメモ化計算で終わりです。

 #include<stdio.h>
 #include<algorithm>
 #include<string.h>
 #include<math.h>
  
 struct S{
 	int r,c,len;
 	bool operator<(const S& s)const{
 		return len<s.len;
 	}
 };
 int rootMemo[1002][1002];
 int mod=100000007;
 int calc(int r,int c){
 	memset(rootMemo,0,sizeof(rootMemo));
 	rootMemo[0][1]=1;
 	for(int i=1;i<=r+1;i++){
 		for(int j=1;j<=c+1;j++){
 			rootMemo[i][j]=rootMemo[i-1][j]+rootMemo[i][j-1];
 			if(rootMemo[i][j]>mod)rootMemo[i][j]-=mod;
  		}
 	}
 	return rootMemo[r+1][c+1];
 }
 
 int main(){
	S s[9];
 	int r,c,ys,xs,yg,xg,no;
 	scanf("%d %d %d %d %d %d",&r,&c,&ys,&xs,&yg,&xg);
 	xs++;
 	ys++;
 	xg++;
 	yg++;
 	for(int i=0;i<3;i++){
 		for(int j=0;j<3;j++){
 			no=i*3+j;
 			s[no].r=abs((ys+r)-(yg+r*i));
 			s[no].c=abs((xs+c)-(xg+c*j));
 			s[no].len=s[no].r+s[no].c;
 		}
 	}
 	std::sort(s,s+9);
 	int limit=s[0].len;
 	int ans=0;
 	for(int i=0;i<9;i++){
 		if(s[i].len>limit)break;
 		ans=(ans+calc(s[i].r,s[i].c))%mod;
 	}
 	printf("%d\n",ans);
 }








*1502　War
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1502
敵地へ攻め込んだ軍隊が敵地を占領するゲームの問題。

解法
遠くへいける兵士から優先して動かします。
第一陣の４人は先ず上下左右４方向へまっすぐ。
第二陣の４人は、一列ずれたところ１陣と平行にまっすぐ。
以下第ｎ陣はn列ずれたところをまっすぐ進み全部いなくなるまでこれを続けるだけです。


 #include<stdio.h>
 #include<vector>
 #include<algorithm>
 #include<iostream>
 int main(){
 	std::vector<long long int> v;
 	long long int n,a,ans=1;
 	std::cin>>n;
 	while(n--){
 		std::cin>>a;
 		v.push_back(a);
 	}
 	std::sort(v.rbegin(),v.rend());
 	for(int i=0;i<v.size();i++){
 		ans+=v[i]-i/4>0?v[i]-i/4:0;
 	}
 	std::cout<<ans<<"\n";
 }





*1505
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1505
ダンジョンをモチーフにした問題。

解法
この問題は苦労しました。
多分もっと賢い方法があると思いますが私は以下の小手先テクニックでクリアしました。
まず全ての部屋でスタート地点とゴール地点までの距離をダイクストラ法で計算、スタートからの距離をｘ軸、ゴールからの距離をｙ軸として部屋の位置を平面上にプロットしていきます。
すると、問い合わせがあったのより左上にある点の数を数える問題に問題が簡素化されます。
次に部屋をｙ軸を優先してソートしたものを用意しｙ軸優先のソートには問い合わせの点も入れておきます。
ｙ軸を優先してソートしたものを順番に空のｘ軸優先でソートして代入する集合に追加していきます。
問い合わせがあった場合ｘ軸優先のソートから何個目までが問い合わせの点より左上にあるかを数えます。
これだけではｘ軸に入れていく作業が遅くなり速度が出ません。
これを回避するために、ｘ軸の集合を細かく切り分けています。




 #include<stdio.h>
 #include<queue>
 #include<map>
 #include<vector>
 #include<list>
 #include<string.h>
 #include<iostream>
 #include<algorithm>
 long long int memo[100001];
 struct road{
  	int nextRoom;
 	long long int len;
 };
 
 struct S{
 	long long int len;
 	int roomNo;
 	bool operator<(const S& s)const{
 		if(len!=s.len)return len>s.len;
 		return roomNo<s.roomNo;
  	}
 };
 struct Room{
 	long long int sx,gy;
 	bool isRoom;
 	int no;
 	bool operator==(const Room& r)const{
 		return sx==r.sx&&gy==r.gy&&isRoom==r.isRoom&&no==r.no;
 	}
 };
 
 
 class GYSorter {
 	public:
 	//足し算用
 	bool operator()(const Room& l, const Room& r) const {
 		if(l.gy!=r.gy) return l.gy>r.gy;
 		if(l.sx!=r.sx) return l.sx<r.sx;
 		if(l.isRoom!=r.isRoom)return l.isRoom>r.isRoom;
  		return l.no<r.no;
  	}
 };
 class SXSorter {
 	public:
 	bool operator()(const Room& l, const Room& r) const {
 		if(l.sx!=r.sx) return l.sx<r.sx;
 		if(l.gy!=r.gy) return l.gy>r.gy;
 		if(l.isRoom!=r.isRoom)return l.isRoom>r.isRoom;
  		return l.no<r.no;
 	}
 };
 
 bool gyHikaku(const Room& l, const Room& r){
 		if(l.gy!=r.gy) return l.gy>r.gy;
 		if(l.sx!=r.sx) return l.sx<r.sx;
  		return false;
 } 
 
 std::map<int,std::vector<road> > G;
 Room rooms[100001];
 
 
 void D(int roomNo, int n, bool isCalcX){
 	memset(memo,-1,sizeof(memo));
 	S s,nextS;
 	s.roomNo=roomNo;
 	s.len=0;
 	std::priority_queue<S> qu;
 	qu.push(s);
 	while(qu.empty()==false){
 		s=qu.top();
 		qu.pop();
 		if(memo[s.roomNo]!=-1&&memo[s.roomNo]<=s.len)continue;
 		memo[s.roomNo]=s.len;
 		for(int i=0;i<G[s.roomNo].size();i++){
 			nextS.roomNo=G[s.roomNo][i].nextRoom;
 			nextS.len=s.len+G[s.roomNo][i].len;
 			if(memo[nextS.roomNo]!=-1&&memo[nextS.roomNo]<=nextS.len)continue;
 			qu.push(nextS);
 		}
 	}
 	for(int i=0;i<n;i++){
 		rooms[i].isRoom=true;
 		rooms[i].no=i;
 		if(isCalcX==true)	rooms[i].sx=memo[i];
 		else 			rooms[i].gy=memo[i];
 	}
 } 
 
 std::vector<Room> qs,qs2,sortSx,sortGy,sortSx2[250];
 int main(){
 	int n,m,a,b;
 	road r;
 	scanf("%d %d",&n,&m);
 	for(int i=0;i<m;i++){
 		std::cin>>a>>b>>r.len;
 		r.nextRoom=b;
 		G[a].push_back(r);
 		r.nextRoom=a;
 		G[b].push_back(r);
 	}
 	D(0,n,true);
 	D(n-1,n,false);
 
 	
 	
 	std::vector<Room>::iterator vIt;
 	std::map<Room,int,GYSorter> anser;
 	Room room,room2;
 	for(int i=0;i<n;i++){
 		sortGy.push_back(rooms[i]);
 		sortSx.push_back(rooms[i]);
 	}
 	
 	int q;
 	scanf("%d",&q);
 	for(int i=0;i<q;i++){
 		room.isRoom=false;
 		room.no=n+i;
 		std::cin>>room.sx>>room.gy;
 		sortGy.push_back(room); 
 		qs2.push_back(room);
 	}
 	std::sort(sortGy.begin(),sortGy.end(),GYSorter());
 	std::sort(sortSx.begin(),sortSx.end(),SXSorter());
 	int left=0;
 	int count=0;
 	for(int i=0;i<sortGy.size();i++,count++){
 		room=sortGy[i];
 		int no=count/1000;
 		if(room.isRoom==true){
 			vIt=std::upper_bound(sortSx2[no].begin(),sortSx2[no].end(),room,SXSorter());
 			sortSx2[no].insert(vIt,room);
 		}else{
 			int sum=0;
 			for(int i=0;i<=no;i++){
 				if(sortSx2[i].size()>0){
 					vIt=std::lower_bound(sortSx2[i].begin(),sortSx2[i].end(),room,SXSorter());
 					sum+=std::distance(sortSx2[i].begin(),vIt);
 				}
 			}
 			anser[room]=sum;
 		}
 	}
 	for(int i=0;i<q;i++){
 		std::cout<<anser[qs2[i]]<<"\n";
 	}
 }


*2013/3/21
*1507　Dungeon (II)
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1507
ダンジョンゲームをモチーフにした練習問題。
かなり前に挑戦して一度挫折。
今回は２日がかりでこの問題を解いた。

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

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

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

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

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



 #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";
 }





*AOJ1509
レンタルショップの割引システムを書く問題。
解法
私の場合抽象的な問題はある程度できるのですが。
私の場合問題が具体的になると途端に頭の働きが鈍くなるという特徴があります。
こんな簡単な問題で２連続ＷＡの後で正答となりました。


 #include<stdio.h> 
 int main(){
 	int a,b,c,d,e;
 	int na,nb,nc,ans,ans2,t;
 	while(1){
  		scanf("%d %d %d %d %d",&a,&b,&c,&d,&e);
 		if(a+b+c+d+e==0)break;
 		scanf("%d %d %d",&na,&nb,&nc);
 		ans2=a*na+b*nb+c*nc;
 		if(nc>=d){
 			ans=a*na+b*nb+e*nc;
 		}else if(nc+nb>=d){
  			t=nc+nb-d;
 			ans=a*na+b*t+d*e;
 		}else if(nc+nb+na>=d){
 			t=nc+nb+na-d;
 			ans=a*t+e*d;
 		}else if(nc*c>=d*e){
 			ans=a*na+b*nb+d*e;
  		}else if(nc*c+nb*b>=d*e){
 			ans=a*na+d*e;
 		}else if(nc*c+nb*b+na*a>=d*e){
 			ans=d*e;
 		}else{
 			ans=ans2;
 		}
 		ans=ans<ans2?ans:ans2;
 		printf("%d\n",ans);
 	}
 }

*問い1500　ID
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1500
条件を満たすＩＤが幾通りあるか答える問題。

解法
-*の数も少なくメモ化で一発です。


 #include<stdio.h>
 #include<string.h>
 char id[100001];
 int memo[100001][10];
 int main(){
 	
 	int n,m,a;
 	int base2[10]={0,2,4,6,8,1,3,5,7,9};
 	bool oks[10]={0,0,0,0,0,0,0,0,0,0};
 	scanf("%d %s",&n,id);
 	scanf("%d",&m);
	for(int i=0;i<m;i++){
  		scanf("%d",&a);
		oks[a]=true;
  	}
 
 	memset(memo,0,sizeof(memo));
 	memo[0][0]=1;
 	for(int i=1;i<=n;i++){
 		char c=id[n-i];
 		if(c=='*'){
 			for(int j=0;j<=9;j++){
 				for(int k=0;k<=9;k++){
 					if(oks[k]==true){
 						if(i%2==0)memo[i][(j+base2[k])%10]+=memo[i-1][j];
 						else memo[i][(j+k)%10]+=memo[i-1][j];
 					}
 				}
 			}
 		}else{
 			for(int j=0;j<=9;j++){
 				if(i%2==0)memo[i][(j+base2[c-'0'])%10]+=memo[i-1][j];
 				else memo[i][(j+(c-'0'))%10]+=memo[i-1][j];
 			}
 		}
 　	}
 　	printf("%d\n",memo[n][0]);
 }








*1501 Grid
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1501
上端下端、左端右端がつながったマップで二点の間を最短距離で移動したとき何通りのルートがあるか。
解法
上下左右に斜めの８方向に向かった場合の最短距離を検討して後はメモ化計算で終わりです。

 #include<stdio.h>
 #include<algorithm>
 #include<string.h>
 #include<math.h>
  
 struct S{
 	int r,c,len;
 	bool operator<(const S& s)const{
 		return len<s.len;
 	}
 };
 int rootMemo[1002][1002];
 int mod=100000007;
 int calc(int r,int c){
 	memset(rootMemo,0,sizeof(rootMemo));
 	rootMemo[0][1]=1;
 	for(int i=1;i<=r+1;i++){
 		for(int j=1;j<=c+1;j++){
 			rootMemo[i][j]=rootMemo[i-1][j]+rootMemo[i][j-1];
 			if(rootMemo[i][j]>mod)rootMemo[i][j]-=mod;
  		}
 	}
 	return rootMemo[r+1][c+1];
 }
 
 int main(){
	S s[9];
 	int r,c,ys,xs,yg,xg,no;
 	scanf("%d %d %d %d %d %d",&r,&c,&ys,&xs,&yg,&xg);
 	xs++;
 	ys++;
 	xg++;
 	yg++;
 	for(int i=0;i<3;i++){
 		for(int j=0;j<3;j++){
 			no=i*3+j;
 			s[no].r=abs((ys+r)-(yg+r*i));
 			s[no].c=abs((xs+c)-(xg+c*j));
 			s[no].len=s[no].r+s[no].c;
 		}
 	}
 	std::sort(s,s+9);
 	int limit=s[0].len;
 	int ans=0;
 	for(int i=0;i<9;i++){
 		if(s[i].len>limit)break;
 		ans=(ans+calc(s[i].r,s[i].c))%mod;
 	}
 	printf("%d\n",ans);
 }








*1502　War
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1502
敵地へ攻め込んだ軍隊が敵地を占領するゲームの問題。

解法
遠くへいける兵士から優先して動かします。
第一陣の４人は先ず上下左右４方向へまっすぐ。
第二陣の４人は、一列ずれたところ１陣と平行にまっすぐ。
以下第ｎ陣はn列ずれたところをまっすぐ進み全部いなくなるまでこれを続けるだけです。


 #include<stdio.h>
 #include<vector>
 #include<algorithm>
 #include<iostream>
 int main(){
 	std::vector<long long int> v;
 	long long int n,a,ans=1;
 	std::cin>>n;
 	while(n--){
 		std::cin>>a;
 		v.push_back(a);
 	}
 	std::sort(v.rbegin(),v.rend());
 	for(int i=0;i<v.size();i++){
 		ans+=v[i]-i/4>0?v[i]-i/4:0;
 	}
 	std::cout<<ans<<"\n";
 }





*1505
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1505
ダンジョンをモチーフにした問題。

解法
この問題は苦労しました。
多分もっと賢い方法があると思いますが私は以下の小手先テクニックでクリアしました。
まず全ての部屋でスタート地点とゴール地点までの距離をダイクストラ法で計算、スタートからの距離をｘ軸、ゴールからの距離をｙ軸として部屋の位置を平面上にプロットしていきます。
すると、問い合わせがあったのより左上にある点の数を数える問題に問題が簡素化されます。
次に部屋をｙ軸を優先してソートしたものを用意しｙ軸優先のソートには問い合わせの点も入れておきます。
ｙ軸を優先してソートしたものを順番に空のｘ軸優先でソートして代入する集合に追加していきます。
問い合わせがあった場合ｘ軸優先のソートから何個目までが問い合わせの点より左上にあるかを数えます。
これだけではｘ軸に入れていく作業が遅くなり速度が出ません。
これを回避するために、ｘ軸の集合を細かく切り分けています。




 #include<stdio.h>
 #include<queue>
 #include<map>
 #include<vector>
 #include<list>
 #include<string.h>
 #include<iostream>
 #include<algorithm>
 long long int memo[100001];
 struct road{
  	int nextRoom;
 	long long int len;
 };
 
 struct S{
 	long long int len;
 	int roomNo;
 	bool operator<(const S& s)const{
 		if(len!=s.len)return len>s.len;
 		return roomNo<s.roomNo;
  	}
 };
 struct Room{
 	long long int sx,gy;
 	bool isRoom;
 	int no;
 	bool operator==(const Room& r)const{
 		return sx==r.sx&&gy==r.gy&&isRoom==r.isRoom&&no==r.no;
 	}
 };
 
 
 class GYSorter {
 	public:
 	//足し算用
 	bool operator()(const Room& l, const Room& r) const {
 		if(l.gy!=r.gy) return l.gy>r.gy;
 		if(l.sx!=r.sx) return l.sx<r.sx;
 		if(l.isRoom!=r.isRoom)return l.isRoom>r.isRoom;
  		return l.no<r.no;
  	}
 };
 class SXSorter {
 	public:
 	bool operator()(const Room& l, const Room& r) const {
 		if(l.sx!=r.sx) return l.sx<r.sx;
 		if(l.gy!=r.gy) return l.gy>r.gy;
 		if(l.isRoom!=r.isRoom)return l.isRoom>r.isRoom;
  		return l.no<r.no;
 	}
 };
 
 bool gyHikaku(const Room& l, const Room& r){
 		if(l.gy!=r.gy) return l.gy>r.gy;
 		if(l.sx!=r.sx) return l.sx<r.sx;
  		return false;
 } 
 
 std::map<int,std::vector<road> > G;
 Room rooms[100001];
 
 
 void D(int roomNo, int n, bool isCalcX){
 	memset(memo,-1,sizeof(memo));
 	S s,nextS;
 	s.roomNo=roomNo;
 	s.len=0;
 	std::priority_queue<S> qu;
 	qu.push(s);
 	while(qu.empty()==false){
 		s=qu.top();
 		qu.pop();
 		if(memo[s.roomNo]!=-1&&memo[s.roomNo]<=s.len)continue;
 		memo[s.roomNo]=s.len;
 		for(int i=0;i<G[s.roomNo].size();i++){
 			nextS.roomNo=G[s.roomNo][i].nextRoom;
 			nextS.len=s.len+G[s.roomNo][i].len;
 			if(memo[nextS.roomNo]!=-1&&memo[nextS.roomNo]<=nextS.len)continue;
 			qu.push(nextS);
 		}
 	}
 	for(int i=0;i<n;i++){
 		rooms[i].isRoom=true;
 		rooms[i].no=i;
 		if(isCalcX==true)	rooms[i].sx=memo[i];
 		else 			rooms[i].gy=memo[i];
 	}
 } 
 
 std::vector<Room> qs,qs2,sortSx,sortGy,sortSx2[250];
 int main(){
 	int n,m,a,b;
 	road r;
 	scanf("%d %d",&n,&m);
 	for(int i=0;i<m;i++){
 		std::cin>>a>>b>>r.len;
 		r.nextRoom=b;
 		G[a].push_back(r);
 		r.nextRoom=a;
 		G[b].push_back(r);
 	}
 	D(0,n,true);
 	D(n-1,n,false);
 
 	
 	
 	std::vector<Room>::iterator vIt;
 	std::map<Room,int,GYSorter> anser;
 	Room room,room2;
 	for(int i=0;i<n;i++){
 		sortGy.push_back(rooms[i]);
 		sortSx.push_back(rooms[i]);
 	}
 	
 	int q;
 	scanf("%d",&q);
 	for(int i=0;i<q;i++){
 		room.isRoom=false;
 		room.no=n+i;
 		std::cin>>room.sx>>room.gy;
 		sortGy.push_back(room); 
 		qs2.push_back(room);
 	}
 	std::sort(sortGy.begin(),sortGy.end(),GYSorter());
 	std::sort(sortSx.begin(),sortSx.end(),SXSorter());
 	int left=0;
 	int count=0;
 	for(int i=0;i<sortGy.size();i++,count++){
 		room=sortGy[i];
 		int no=count/1000;
 		if(room.isRoom==true){
 			vIt=std::upper_bound(sortSx2[no].begin(),sortSx2[no].end(),room,SXSorter());
 			sortSx2[no].insert(vIt,room);
 		}else{
 			int sum=0;
 			for(int i=0;i<=no;i++){
 				if(sortSx2[i].size()>0){
 					vIt=std::lower_bound(sortSx2[i].begin(),sortSx2[i].end(),room,SXSorter());
 					sum+=std::distance(sortSx2[i].begin(),vIt);
 				}
 			}
 			anser[room]=sum;
 		}
 	}
 	for(int i=0;i<q;i++){
 		std::cout<<anser[qs2[i]]<<"\n";
 	}
 }


*2013/3/21
*AOJ 1507　Dungeon (II)
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1507
ダンジョンゲームをモチーフにした練習問題。
かなり前に挑戦して一度挫折。
今回は２日がかりでこの問題を解いた。

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

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

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

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

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



 #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";
 }





*AOJ 1509 Rental DVD Shop NEO
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1509
レンタルショップの割引システムを書く問題。
解法
私の場合抽象的な問題はある程度できるのですが。
私の場合問題が具体的になると途端に頭の働きが鈍くなるという特徴があります。
こんな簡単な問題で２連続ＷＡの後で正答となりました。


 #include<stdio.h> 
 int main(){
 	int a,b,c,d,e;
 	int na,nb,nc,ans,ans2,t;
 	while(1){
  		scanf("%d %d %d %d %d",&a,&b,&c,&d,&e);
 		if(a+b+c+d+e==0)break;
 		scanf("%d %d %d",&na,&nb,&nc);
 		ans2=a*na+b*nb+c*nc;
 		if(nc>=d){
 			ans=a*na+b*nb+e*nc;
 		}else if(nc+nb>=d){
  			t=nc+nb-d;
 			ans=a*na+b*t+d*e;
 		}else if(nc+nb+na>=d){
 			t=nc+nb+na-d;
 			ans=a*t+e*d;
 		}else if(nc*c>=d*e){
 			ans=a*na+b*nb+d*e;
  		}else if(nc*c+nb*b>=d*e){
 			ans=a*na+d*e;
 		}else if(nc*c+nb*b+na*a>=d*e){
 			ans=d*e;
 		}else{
 			ans=ans2;
 		}
 		ans=ans<ans2?ans:ans2;
 		printf("%d\n",ans);
 	}
 }