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

AOJ271~280 - (2013/02/25 (月) 14:40:40) のソース

*0271 Izua Dictionary
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0271
重複のない十万文字の文字でできた文字列が最初順序よく並んでいる。
50回2か所を入れ替える操作を繰り返したとき、できた文字列が辞書順で何番目になるか答えよ。


解法
この問題のポイントは、ABCD,,から操作した結果でありその回数が少ないという点にあります。
ACDG,,という単語が何番目か調べるという問題でないのです。
一回の操作で、入れ替わった結果、辞書順で何番目かを表す計算に影響するのはs~tまでの範囲以外変更がなくその部分だけ計算します。
((何個目の文字-左からその文字まで読んでその文字より小さい文字が左に出てくる数)*その文字より右の並びの組み合わせ数)これを各文字について足し合わせると答えが出ます。
この何個目の文字かと左から読んでその文字より小さい数が何個かは一回毎の操作で綺麗に決まるのでそこに注目してい計算します。


 #include<stdio.h>
 #include<string.h>
 #include<iostream>
 long long int bs[100001],ms[100001],mod=1000000007,perm[100001];
 void calc(int n){
 	long long int ans=0,as[100001],cs[100001];
 	memcpy(as,bs,sizeof(bs));
 	memcpy(cs,ms,sizeof(ms));
 	int r,s,t;
 	scanf("%d",&r);
 	for(int i=0;i<r;i++){
 		scanf("%d %d",&s,&t);
 		s--;
 		t--;
 		long long int num=as[s];
 		as[s]=as[t];
 		as[t]=num;
 		int dell=0;
 		for(int i=0;i<s;i++){
 			if(as[i]<as[s])dell--;
 		}
 		cs[s]=dell;
 		dell=0;
 		for(int i=0;i<t;i++){
 			if(as[i]<as[t])dell--;
  		}
		cs[t]=dell;
  		for(int i=s+1;i<t;i++){
 			if(as[s]<as[i]&&as[i]<as[t]){
 				cs[i]--;
 			}
 			if(as[t]<as[i]&&as[i]<as[s]){
 				cs[i]++;
 			}
 		}
 	}
 	for(int i=n-2;i>=0;i--){
 		//std::cout<<perm[n-2-i]<<" "<<i<<" "<<cs[i]<<" "<<as[i]<<"\n";
 		ans=(ans+(perm[n-2-i]*(as[i]+cs[i]))%mod)%mod;
 	}
 	std::cout<<ans%mod<<"\n";
 }
 
 int main(){
 	int n;
 	for(int i=0;i<=100000;i++){
 		bs[i]=i;
 		ms[i]=-i;
  	}
 	perm[0]=1;
 	for(long long int i=1;i<=100000;i++)perm[i]=(perm[i-1]*(i+1))%mod;
 	while(1){
 		scanf("%d",&n);
 		if(n==0)break;
 		calc(n);
 	}
 }



*0272 The Lonely Girl's Lie
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0272
架空のゲームで確実に勝利できる場合を答える問題。

解法
どんな勝負になっても勝てるということをいいかえると相手はこちらの手を完全に読んで一番いい手で攻めてくると想定します。
こちらの取れる一番いい手は一番レベルの高いセットで挑むことであり、相手の取る手は、それにギリギリでかてるか引き分けるカードを出すか、勝てない場合は一番弱いカードを出してくるとします。
答えを思いつくまで2時間かかりました。

 #include<stdio.h>
 #include<set>
 #include<algorithm>
 struct S{
 	int no,level;
 	bool operator<(const S& s)const{
 		if(level!=s.level)return level>s.level;
 		return no<s.no;
 	}
 };
 S as[40001];
 void calc(int n){
 	S a,b;
 	std::set<S> bs;
	std::set<S>::iterator it;
 	for(int i=0;i<n;i++){
 		as[i].no=i;
 		scanf("%d",&as[i].level);
  	}
 	for(int i=0;i<n;i++){
 		b.no=i+n;
 		scanf("%d",&b.level);
 		bs.insert(b);
 	}
 	std::sort(as,as+n);
 	int lossCount=0,k=0;
 	for(int i=0;i<n;i++){
  		a=as[i];
 		it=bs.lower_bound(a);
 		if(it!=bs.begin()&&(*it).level<a.level)it--;
 		b=(*it);
 		if(a.level<=b.level){
  			bs.erase(it);
 			lossCount++;
 		}else{
 			it=bs.end();
  			it--;
 			bs.erase(it);
 		}
 		k++;
 		if(k/2<(k-lossCount))break;
  	}
 	if(k==n){
 		printf("NA\n");
 	}else{
 		printf("%d\n",k);
 	}
 }
 
 int main(){
 	int n;
 	while(1){
 		scanf("%d",&n);
 		if(n==0)break;
 		calc(n);
 	}
 }





*問い0275 Railroad
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0275
グラフとして駅とそのつながりのデータが与えられる。
a駅からb駅へ移動する最短経路(複数の経路が考えられる)、c駅とd駅がこの順で含まれているならYesでないならNoと返せ。
駅の数は10万、路線の数は20万、c駅とd駅の質問の数は4万個である。

解法
ダイクストラ法を改良して、bからaへ向かう最短経路のグラフを作りbからaへ向かう経路とします。
この時駅bに近い駅ほど高いランクが割り当てられるようグラフの点にランクを与えておきます。
後は駅データが与えられるたびに、最短経路のグラフをdからcへ向かって全探索します。
探索中の駅のランクがcよりランクが小さくなったらそれより先にcはないので探索を打ち切ることで計算量を減らします。
色々な形のグラフを考えた時、どんなグラフでも効率的に動く手法を思いつかずこのような拙劣な方法に落ち着きました。
拙劣ですが計算量が安定するという利点があります。
私が思いついた手法で他の物はどれも、いくつかのタイプのグラフでは早く動くがあるグラフでは低速かメモリを大量に消費するという問題のあるものばかりでした。



 #include<stdio.h>
 #include<set>
 #include<queue>
 #include<map>
 #include<string.h>
 struct P{
  	int to,len,rank;
	bool operator<(const P& s)const{
 		if(len!=s.len)return len>s.len;
 		return rank<s.rank;
 	}
 };
 
 struct Q{
 	int c,d;
 	bool operator<(const Q& q)const{
 		if(c!=q.c)return c<q.c;
 		return d<q.d;
 	}
 };
 
 const int size=100001;
 int lenMemo[size];
 int rankMemo[size];
 bool isFirst[size];
 std::vector<P> G[size];
 std::set<int> backs[size];
 bool isBackOKs[size];
 bool isBackOKs2[size];
 
 void D(int a,int b){
 	memset(lenMemo,-1,sizeof(lenMemo));
 	memset(isFirst,true,sizeof(isFirst));
 	memset(rankMemo,-1,sizeof(rankMemo));
 	std::priority_queue<P> qu;
 	P p,nextP;
 	p.len=0;
 	p.to=a;
 	p.rank=0;
 	qu.push(p);
 	lenMemo[a]=0;
 	while(qu.empty()==false){
 		p=qu.top();
 		qu.pop();
 		if(isFirst[p.to]==false)continue;
 		isFirst[p.to]=false;
 		rankMemo[p.to]=p.rank;
 		if(b==p.to)continue;
 		for(int i=0;i<G[p.to].size();i++){
 			nextP.to=G[p.to][i].to;
 			nextP.len=p.len+G[p.to][i].len;
 			nextP.rank=p.rank+1;
  			if(lenMemo[nextP.to]==-1 || lenMemo[nextP.to]>nextP.len){
 				lenMemo[nextP.to]=nextP.len;
 				backs[nextP.to].clear();
 				backs[nextP.to].insert(p.to);
 				qu.push(nextP);
 			}else if(lenMemo[nextP.to]==nextP.len){
 				backs[nextP.to].insert(p.to);
 				qu.push(nextP);
 			}
 		}
 	}
 }
 
 void saiki(int to){
 	if(isBackOKs[to]==false)return;
 	isBackOKs[to]=false;
 	for(std::set<int>::iterator it=backs[to].begin();it!=backs[to].end();it++){
 		saiki((*it));
 	}
 }
 
 bool search(int c,int to){
 	if(isBackOKs2[to]==false)return false;
 	isBackOKs2[to]=false;
 	if(c==to)return true;
 	if(rankMemo[c]>rankMemo[to])return false;
 	bool re=false;
 	for(std::set<int>::iterator it=backs[to].begin();it!=backs[to].end();it++){
 		re=re||search(c,(*it));
 		if(re==true) break;
 	}
 	return re;
 }
 
 int main(){
 	int s,r,u,v,w;
  	P p1;
	scanf("%d %d",&s,&r);
  	for(int i=0;i<r;i++){
 		scanf("%d %d %d",&u,&v,&w);
 		p1.len=w;
 		p1.to=v;
 		G[u].push_back(p1);
 		p1.to=u;
 		G[v].push_back(p1);
 	}
 	
 	int a,b,q,c,d;
 	scanf("%d %d %d",&a,&b,&q);
 	D(a,b);
 	memset(isBackOKs,true,sizeof(isBackOKs));
 	saiki(b);
 	for(int i=0;i<q;i++){
 		scanf("%d %d",&c,&d);
 		if(isBackOKs[c]==false&&isBackOKs[d]==false&&rankMemo[c]<rankMemo[d]){
 			memset(isBackOKs2,true,sizeof(isBackOKs2));
 			printf("%s\n",search(c,d)?"Yes":"No");
 		}else{
 			printf("No\n");
 		}
 	}
 }