「AOJ1500~1509」の編集履歴(バックアップ)一覧に戻る

AOJ1500~1509 - (2013/05/01 (水) 11:51:05) のソース

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

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


 #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
上端下端、左端右端がつながったマップで二点の間を最短距離で移動したとき何通りのルートがあるか。
解法
上下左右に斜めの8方向に向かった場合の最短距離を検討して後はメモ化計算で終わりです。

 #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
敵地へ攻め込んだ軍隊が敵地を占領するゲームの問題。

解法
遠くへいける兵士から優先して動かします。
第一陣の4人は先ず上下左右4方向へまっすぐ。
第二陣の4人は、一列ずれたところ1陣と平行にまっすぐ。
以下第n陣は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
ダンジョンをモチーフにした問題。

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




 #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
ダンジョンゲームをモチーフにした練習問題。
かなり前に挑戦して一度挫折。
今回は2日がかりでこの問題を解いた。

解法 
難しい問題です。 
部屋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";
 }





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


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