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

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

AOJ1500~1509 - (2013/03/03 (日) 01:22:21) のソース

*問い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";
 	}
 }


*1507 Dungeon (II)
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1507
ゲームのダンジョンの危険度を判定する問題。

解法
只今考え中。
いったん全部の辺を切ってコストの低い辺から繋げていきます。
繋げたことで木構造がつながっていきますが、この時つながった木の片側の木にある点から反対側の木にある点に移動するにはどの点を選んでも、繋げた辺のコストだけコストがかかります。
なのでこの繋げた時に発生したコストを足し算してやれば計算が終わるのですが、問題はどうやって繋げたを表現するかです。