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

「AOJ1500~1509」の編集履歴(バックアップ)一覧に戻る
AOJ1500~1509」を以下のとおり復元します。
*問い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
ダンジョンをモチーフにした問題。

解法
今のところ37個目のジャッジデータまでアセプトするコードを書いています、後はタイムリミッドしている状態です。
なのでコード自体は正しい答えを出していると考えてよいでしょう。
問題は速度アップだけです。
集合の併合で速度が出てない感じです。

乱雑な場合に対処するコードを書くと
S-G-r1-r2,,,-rn
G-S-r1-r2,,,-rn
のような特殊な場合に対処できません。
難しいところです。

 #include<stdio.h>
 #include<queue>
 #include<map>
 #include<vector>
 #include<string.h>
 #include<iostream>
 
 long long int sMemo[100001],gMemo[100001];
 
 struct road{
 	int nextRoom;
 	long long int len;
 };
 struct room{
 	int roomNo;
 	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;
 	}
 };
 class lenSorter {
 	public:
 	bool operator()(const room& l, const room& r) const {
 		if(l.len!=r.len) return l.len<r.len;
 		return l.roomNo<r.roomNo;
 	}
 }; 
 class roomSorter {
 	public:
 	bool operator()(const room& l, const room& r) const {
 		return l.roomNo<r.roomNo;
  	}
 };
 
 
 std::vector<road> G[100001];
 std::map<room,int,lenSorter> gLen,sLen;
 
 void D(int roomNo,long long int memo[100001],std::map<room,int,lenSorter>& lens,int n){
 	memset(memo,-1,sizeof(memo)*100001);
 	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;
 			memo[nextS.roomNo]=nextS.len;
 			qu.push(nextS);
 		}
 	}
 	room r;
 	for(int i=0;i<n;i++){
 		r.roomNo=i;
 		r.len=memo[i];
 		lens[r]=0;
 	}
 	int no=0;
 	for(std::map<room,int,lenSorter>::iterator it=lens.begin();it!=lens.end();it++){
 		(*it).second=no;
 		no++;
 	}
 }
 
 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,sMemo,sLen,n);
 	D(n-1,gMemo,gLen,n);
 	int q;
 	std::cin>>q;
 	room r1,r2;
 	r1.roomNo=n+1;
 	r2.roomNo=-1;
 	std::map<room,int,lenSorter>::iterator it1,it2,it;
 	for(int i=0;i<q;i++){
 		std::map<room,int,roomSorter> unions;
 		std::cin>>r1.len>>r2.len;
 		it1=sLen.lower_bound(r1);
 		it2=gLen.lower_bound(r2);
 		if(it2==gLen.end()){
 			printf("0\n");
 			continue;
 		}
 		if(it1==sLen.end())it1--;
 		int ans=(n-(*it2).second);//ゴールからの距離がfg以上の部屋の数
 		while(it1!=sLen.begin()&&(*it1).first.len>r1.len)it1--;
 		ans+=(*it1).second+1;//スタートからの距離がfs以内の部屋の数
 		while(it1!=sLen.end()&&(*it1).first.len<=r1.len)it1++;
 		unions.insert(sLen.begin(),it1);
 		unions.insert(it2,gLen.end());
 		ans-=unions.size();
 		printf("%d\n",ans);
  	}
 }


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

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

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