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

AOJ1011~1020 - (2011/11/18 (金) 16:53:46) の1つ前との変更点

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

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

+----
+*1011 Finding the Largest Carbon Compound Given Its Long
+http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1011
+CとHで出来た炭素鎖からHを省き、できた鎖のCの両端を持った時両端が最も長くなる距離をnとする。
+長さがnを超えないでCを歳代までくっつけた時数字上何個までCを接続できるか答えよという問題。
+
+解法
+この問題は英語読解が出来なかったためYahoo知恵袋で問題の題意を質問して解きました。
+題意が分かれば対称性を利用して解ける簡単な問題です。
+
+
+ #include<stdio.h>
+ void calc(int perm[31]){
+	perm[0]=0;
+	perm[1]=1;
+	perm[2]=2;
+	perm[3]=5;
+	for(int i=4;i<31;i++){
+		if(i&1==1){
+			perm[i]=4*(((perm[i-2]-1)/4)*3+1)+1;
+		}else{
+			perm[i]=6*(((perm[i-3]-1)/4)*3+1)+2;
+		}
+	}
+ }
+ int main(){
+	int perm[31],n;	
+	calc(perm);
+	while(scanf("%d",&n)!=EOF){
+		printf("%d\n",perm[n]);
+	}
+ }
+
+
+
+
 ----
 *1014 Computation of Minimum Length of Pipeline
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1014
 源泉から都市へパイプラインを引く問題。
 都市間の距離、源泉から都市への距離が与えれるので最小の距離でパイプを接続せよという問題。
 
 解法
 どの源泉も供給能力は同じで区別がつきません。
 源泉を全て丸で囲んで1点とみなし、源泉から都市への最小距離を最初に更新します。
 後は都市と源泉を点とみなしグラフの上でプリム法で接続していくだけです。
 
 
 
 
  #include<stdio.h>
  #include<queue>
  #include<string.h>
  #include <algorithm>
  int map[102][102];//0が源泉ひとまとめ、1以降が都市
  struct Edge{
 	int to,len;//エッジの接続先と繋げるパイプの長さ
 	bool operator<(const Edge& e)const{
 		return e.len<len;
 	}
  };
  const int stop=0;
  int prim(int d){
 	//プリム法でパイプラインの配置を解く。
 	//まず源泉は全て長さ0の辺でつながっているという過程で始める
 	std::priority_queue<Edge> qu;	
 	bool conOKs[101];
 	memset(conOKs,true,sizeof(conOKs));
 	Edge edge;
 	edge.len=0;
 	edge.to=0;
 	qu.push(edge);//最初長さ0で源泉に接続する
 	int nextP,sumLen=0,count=0;//
 	while(!qu.empty()){
 		edge=qu.top();//一番短いパイプラインを選んでいく
 		qu.pop();
 		nextP=edge.to;
 		if(conOKs[nextP]==false) continue;//接続済みの都市にパイプラインをつなげようとした
 		conOKs[nextP]=false;
 		count++;//つなげた都市の数
 		sumLen+=edge.len;//答えの集計
 		if(count==d+1) break;//全ての都市と源泉をつないだら終了	
 		for(int i=0;i<=d;i++){
 			if(conOKs[i]==false||map[nextP][i]==stop)continue;//もうパイプを通した都市もしくは接続不能の都市への接続は無視する
 			edge.to =i;
 			edge.len=map[nextP][i];
 			qu.push(edge);
 		}
 	}
 	return sumLen;
  }
  void setData(int s,int d){
 	int temp;
 	memset(map,stop,sizeof(map));
 	for(int i=0;i<s;i++){
 		for(int j=1;j<=d;j++){
 			scanf("%d",&temp);
 			if(map[0][j]==0 || (map[0][j]>temp&&temp!=stop)){
 				map[0][j]=temp;//全ての源泉を丸で囲んで1点とみなす
 			}
 			map[j][0]=map[0][j];
 		}
 	}	
 	for(int i=1;i<d;i++){
 		for(int j=i+1;j<=d;j++){
 			scanf("%d",&map[i][j]);//都市間の距離のセット
 			map[j][i]=map[i][j];
 		}
 	}
 	printf("%d\n",prim(d));
  }
  int main(){
 	int s,d;
 	while(1){
 		scanf("%d %d",&s,&d);
 		if(s==0 && d==0) break;
 		setData(s,d);
 	}
  }
 
 
 
 
 
 
 
 ----
 *1015 Dominating Set
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1015
 最小の頂点支配集合を求める問題。
 
 解法
 初めはBitSetで解こうかと考えたのですが、最大頂点数が分からなかった(多分書いてない?)のでvectorに頂点支配されるかの状態を保存することにしました。
 コードは深さ優先探索である点を頂点支配集合に入れる入れないを2分探索しているだけです。
 素朴な方法で速度が出なかったので小手先のテクニックを入れたらコードが膨らみました。
 深さ優先探索するまえに辺の多い点を優先して調べるよう並べ替えること。
 もう一つはある点で支配できる領域が他の点で支配できる領域のサブセットをなすならその点は探索で無視する。
 残りは探索の途中で残りの点をすべて使っても頂点支配出来ない点が判明した時探索を枝刈すること。
 ということをしています。
 小手先すぎて駄目ですね、20倍程度しか速くなりませんでした。
 頂点支配集合についてきちんと勉強することにしようと考えた問題でした。
 
 
 
 
 
  #include<stdio.h>
  #include<vector>
  #include <algorithm>
  #include <map>
  #include <set>
  struct vecSizeSorter
  {
     bool operator()( const std::vector<int>& lhs, const std::vector<int>& rhs ) const
     {
         return lhs.size() > rhs.size();//点に入る辺の本数が多い方を優先
     }
  };
  //グローバル変数まとめ
  int ans,x;
  std::vector<std::vector<int> > map;//グラフのつながり
  std::vector<bool> subSet;//ある点で支配される領域が別の点のサブセットでないかのチェック
  std::vector<std::set<int> > cut;
  //グローバル変数終わり
  void saiki(std::vector<bool> state,int p,int count,int vCount){
 	if(ans<=vCount) return;
 	//支配集合に入ってる数が全体になった
 	if(count==x){
 		ans=ans>vCount?vCount:ans;
 		return;
 	}
 	if(p>=x)return;
 	if(subSet[p]==true){
 		saiki(state,p+1,count,vCount);//この点Pは他の点のサブセットなので無視する
 		return ;
 	}
 	for(int i=0;i<x;i++){
 		if(state[i]==false && cut[p].find(i)==cut[p].end()){
 			//残りの点では被覆できないことが判明したのでリターン
 			return ;
 		}
 	}
 	int backCount=count;
 	std::vector<bool> back=state;	
 	//この点pを支配集合とする
 	for(int i=0;i<map[p].size();i++){
 		if(state[map[p][i]]==false){
 			count++;
 			state[map[p][i]]=true;
 		}
 	}
 	if(backCount!=count){
 		saiki(state,p+1,count,vCount+1);//支配集合とする
 		state=back;//変化があったので元に戻す
 		count=backCount;
 	}
 	saiki(state,p+1,count,vCount);//この点を支配集合としない
  }
  bool isSubSet(std::vector<int>& vec1,std::vector<int>& vec2){
 	//ソート済みを渡すので必ずvec1>=vec2
 	//vec2がvec1のサブセットでないかをチェックする
 	std::set<int> sets;
 	sets.insert(vec1.begin(),vec1.end());
 	int count=sets.size();
 	sets.insert(vec2.begin(),vec2.end());
 	if(count==sets.size()){
 		return true;
 	}else{
 		return false;
 	}
  }
  void search(int x,int y){	
 	std::vector<bool> state;
 	ans=x+1;
 	map.clear();
 	map.resize(x);
 	state.resize(x);
 	int from,to;
 	for(int i=0;i<y;i++){
 		scanf("%d %d",&from,&to);
 		map[from].push_back(to);
 		map[to].push_back(from);
 	}
 	for(int i=0;i<x;i++){
 		map[i].insert(map[i].begin(),i);//支配集合の中心となる点を先頭に挿入
 		state[i]=false;
 	}
 	std::sort(map.begin(),map.end(),vecSizeSorter());//小手先テク頂点集合をソートして辺の多い点から検証する
 	int p;
 	std::map<int,int> temp;
 	for(int i=0;i<x;i++){
 		temp[map[i][0]]=i;//点の位置が入れ替わったので修正
 	}
 	for(int i=0;i<x;i++){
 		for(int j=0;j<map[i].size();j++){
 			map[i][j]=temp[map[i][j]];
 		}
 		std::sort(map[i].begin(),map[i].end());
 	}	
 	subSet.clear();
 	subSet.resize(x);//ある点で頂点支配できる点が他の点の頂点支配のサブセットなら無視する
 	for(int i=0;i<x;i++)subSet[i]=false;
 	for(int i=0;i<x-1;i++){
 		for(int j=i+1;j<x;j++){
 			if(isSubSet(map[i],map[j])==true){
 				subSet[j]=true;
 			}
 		}
 	}
 	//深さ優先探索の途中残りの点で被覆が出来ないことが判明させるためのSet
 	cut.clear();
 	cut.resize(x);
 	cut[x-1].insert(map[x-1].begin(),map[x-1].end());
 	for(int i=x-2;i>=0;i--){
 		cut[i].insert(cut[i+1].begin(),cut[i+1].end());
 		cut[i].insert(map[i].begin(),map[i].end());
 	}	
 	//深さ優先探索で一つずつ点を頂点集合に含める含めないを試して最小値を求める
 	saiki(state,0,0,0);
 	printf("%d\n",ans);
  }
  int main(){
 	int y;
 	while(1){
 		scanf("%d %d",&x,&y);
 		if(x==0 && y==0) break;
 		search(x,y);
 	}
  }
 
 
 
 
 
 
 ----
 *1016 Fibonacci Sets
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1016
 フィナボッチ数を題材にしたグラフの問題。
 
 解法
 同じ番号になった点は区別がつきません。
 それを利用しt記録します。
 後は小さい数から大きい方へ線を引いていって引ける長さdまで線を引いてその範囲に別の数字があればそこを出発点にまた線を引いていきます。
 この方法で線が全体で幾つに分かれるかをカウントして終了です。
 
 
  #include<string.h>
  #include<stdio.h>
  void setData(int v,int d){
 	bool hit[1002];
 	memset(hit,false,sizeof(hit));
 	int fibo[3];
 	fibo[0]=1,fibo[1]=1;
 	for(int i=0;i<v;i++){
 		fibo[(i+2)%3]=(fibo[(i+1)%3]+fibo[i%3])%1001;
 		hit[fibo[(i+2)%3]]=true;
 	}
 	int moveCount=0,allCount=0,add=0;//下から上へ順番にクロールしていく
 	for(int i=0;i<1002;i++){
 		if(d==1 && hit[i]==true){
 			allCount++;//d=1のときだけ特別処理
 			continue;
 		}else if(d==1){
 			continue;
 		}
 		if(hit[i]==true && moveCount+1<d){
 			moveCount=0;//番号の割り振られた点が見つかったのでここから線を引きなおす
 			add=1;
 		}else{
 			moveCount+=add;
 		}
 		if(moveCount+1==d){
 			allCount++;//線を引いても届かない範囲があることが判明したので範囲をカウントする
 			moveCount=0;
 			add=hit[i]?1:0;//今の番号iが数字ならこれから再出発、0なら数字が見つかるまでiをインクリメントする
 		}
 	}
 	allCount+=add;
 	printf("%d\n",allCount);
  }
  int main(){
 	int v,d;
 	while(scanf("%d %d",&v,&d)!=EOF){
 		setData(v,d);
 	}
  }
 
 
 ----
 *1017 Riffle Shuffle
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1017
 リフルシャッフルをシミュレートしシャッフル後一番上にあるカードを答える問題。
 
 解法
 りフルシャッフルをそのまま実装します。
 
 
  #include<stdio.h>
  #include<vector>
  void shuffle(std::vector<int>& cards,int d,int n){
 	std::vector<int> deckA,deckB;
 	for(int i=0;i<n/2;i++)deckB.push_back(cards[i]);
 	for(int i=n/2;i<n;i++)deckA.push_back(cards[i]);//二つの山を作る
 	int nowP=0,up,pA=0,pB=0;
 	while(nowP<n){
 		up=pA+d>deckA.size()?deckA.size():pA+d;
 		for(int i=pA;i<up;i++){
 			cards[nowP]=deckA[i];//Aの山からCardへ戻す
 			nowP++;
 			pA++;
 		}
 		up=pB+d>deckB.size()?deckB.size():pB+d;//次に挿入するカードが山Bを超えるなら山Bの上限で切ってカードを入れる
 		for(int i=pB;i<up;i++){
 			cards[nowP]=deckB[i];//Bの山からCardへ戻す
 			nowP++;//山Cのポインタをインクリメント
 			pB++;
 		}
 	}
  }
  void setData(int n,int r){
 	std::vector<int> cards;
 	int d;
 	for(int i=0;i<n;i++)cards.push_back(i);//カードのセット
 	for(int i=0;i<r;i++){
 		scanf("%d",&d);//シャッフル間隔
 		shuffle(cards,d,n);
 	}
 	printf("%d\n",cards[n-1]);
  }
  int main(){
 	int n,r;
 	while(scanf("%d %d",&n,&r)!=EOF){
 		setData(n,r);
 	}
  }
  
 
 ----
 *1018 Cheating on ICPC
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1018
 プログラムコンテストの問題を解くのにかかる時間とペナルティ時間から最小タイムを答える問題。
 ここまでの問題を解くのにかかった時間分が、それ以後の問題を解くたびにペナルティとして加算される。
 
 解法
 ペナルティ分の加算をそのまま足しこむだけで解決います。
 
 
  #include<stdio.h>
  #include <algorithm>
  void calc(int n){
 	unsigned long long int scores[102],ans=0;
 	for(int i=0;i<n;i++){
 		scanf("%llu",&scores[i]);
 	}
 	std::sort(scores,scores+n);
 	for(int i=0;i<n;i++){
 		ans+=scores[i]*(n-i);
 	}
 	printf("%llu\n",ans);
  }
  int main(){
 	int n;
 	while(scanf("%d",&n)!=EOF){
 		calc(n);
 	}
  }
 
 
 
 
 ----
 *1019 Vampirish Night
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1019
 グルメなバンパイアの一家が要求する血液の種類と量をきちんと提供できるかを計算する問題。
 解法
 冷蔵庫にある送料から要求分を順次引いていき供給できなくなればNoを返します。
 
 
  #include<stdio.h>
  void setData(int n,int k){
 	int bloods[101],b;
 	for(int x=0;x<k;x++){
 		scanf("%d",&bloods[x]);//全血液量を配列に保存
 	}
 	bool allOK=true;
 	for(int y=0;y<n;y++){
 		for(int x=0;x<k;x++){
 			scanf("%d",&b);
 			bloods[x]-=b;//血液を引く
 			if(bloods[x]<0){
 				allOK=false;//足らない血液が判明
 			}
 		}
 	}
 	printf("%s\n",allOK?"Yes":"No");
  }
  int main(){
 	int n,k;
 	while(1){
 		scanf("%d %d",&n,&k);
 		if(n==0 && k==0)break;
 		setData(n,k);
 	}
  }
 
 
 
 
 ----
 *1020 Cleaning Robot
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1020
 升目で区切られた部屋部屋をランダム移動で掃除するロボットが充電器のある部屋でバッテリー切れになる確率を求める問題。
 
 解法
 あるターンである部屋にいるときいままでどの経路を通ってきたにせよ、バッテリー残量は同じです。
 こうなると今いる部屋を基準に経路をまとめてメモ化探索で片がつきます。
 
 
 
 
  #include<stdio.h>
  #include<string.h>
  int dxs[]={1,0,-1,0};
  int dys[]={0,1,0,-1};
  void calc(int n){
 	double memo[2][3][3];//
 	double sum;
 	memset(memo,0,sizeof(memo));
 	char sp,ep,outP;//スタート地点、ゴール地点、物置
 	scanf(" %c %c %c",&sp,&ep,&outP);
 	sp  =sp-'A';//部屋番号を数字に戻す
 	ep  =ep-'A';
 	outP=outP-'A';
 	int butX=outP%3;
 	int butY=outP/3;
 	memo[0][sp/3][sp%3]=1;	
 	int x,y,nx,ny;//今の部屋のx、y座標、次の部屋のnx、ny座標
 	int now,next;
 	for(int turn=0;turn<n;turn++){
 		now=(turn)%2;
 		next=(turn+1)%2;
 		memset(memo[next],0,sizeof(memo[next]));
 		sum=0;//メモ化探索で1ターンずつ移動をシミュレートする。
 		for(int p=0;p<9;p++){
 			x=p%3;
 			y=p/3;
 			for(int i=0;i<4;i++){
 				nx=x+dxs[i];
 				ny=y+dys[i];
 				if(nx<0 || 2<nx ||ny<0 || 2<ny||(butX==nx && butY==ny)){
 					memo[next][y][x]+=memo[now][y][x];//物置か外に出そうならとどまる
 				}else{
 					memo[next][ny][nx]+=memo[now][y][x];//物置でないので移動
 				}
 				sum+=memo[now][y][x];
 			}
 		}
 	}
 	printf("%.8lf\n",memo[n%2][ep/3][ep%3]/sum);
  }
  int main(){
 	int n;
 	while(1){
 		scanf("%d",&n);
 		if(n==0) break;
 		calc(n);
 	}
  }