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

「AOJ271～280」(2013/02/25 (月) 14:40:40) の最新版変更点

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

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

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


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


 #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
架空のゲームで確実に勝利できる場合を答える問題。

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

 #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駅からｂ駅へ移動する最短経路（複数の経路が考えられる）、ｃ駅とｄ駅がこの順で含まれているならＹｅｓでないならＮｏと返せ。
駅の数は１０万、路線の数は２０万、ｃ駅とｄ駅の質問の数は４万個である。

解法
ダイクストラ法を改良して、ｂからaへ向かう最短経路のグラフを作りｂからaへ向かう経路とします。
この時駅ｂに近い駅ほど高いランクが割り当てられるようグラフの点にランクを与えておきます。
後は駅データが与えられるたびに、最短経路のグラフをｄからｃへ向かって全探索します。
探索中の駅のランクがｃよりランクが小さくなったらそれより先にｃはないので探索を打ち切ることで計算量を減らします。
色々な形のグラフを考えた時、どんなグラフでも効率的に動く手法を思いつかずこのような拙劣な方法となりました。



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

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


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


 #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
架空のゲームで確実に勝利できる場合を答える問題。

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

 #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駅からｂ駅へ移動する最短経路（複数の経路が考えられる）、ｃ駅とｄ駅がこの順で含まれているならＹｅｓでないならＮｏと返せ。
駅の数は１０万、路線の数は２０万、ｃ駅とｄ駅の質問の数は４万個である。

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



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