あったこといろいろ

ほぼ自分用備忘録です。

ICPC2014-A,B,D問題解いたやつ

とのことでした。
diffをとったら合ってたっぽいので、いまさらですがここに保管しておくことにします。
ちょろっと書いてある問題概要はおおまかなことしか書いてないのでここ(http://icpc.tanaka.ecc.u-tokyo.ac.jp/icpc2014/contest/all_ja.html)参照。

problemA--税率変更-- (AOJ1192)

税込み価格で全探索し、「その税込価格になりえない税込価格」の場合は除外した。
税抜で全探索した人の方が多かったようなので、方針ミスっぽい。

#include <iostream>

using namespace std;

int main(){
	while(1){
		int x,y,z;
		
		int ans;
		cin>>x>>y>>z;
		if(x==0 && y==0 && z==0)break;
		
		int maxi=-1;
		int nukia,nukib,komia,komib;
		for(int i=1;i<=z/2;i++){
			for(int j=z-1;j>=1;j--){
				if(j*(100+x)/100==i){
					nukia=j;
					break;
				}
			}
			for(int j=z-1;j>=1;j--){
				if(j*(100+x)/100==z-i){
					nukib=j;
				}
			}
			int a=nukia*(100+x)/100;
			int b=nukib*(100+x)/100;
			if(a+b!=z)goto skip;

			komia=nukia*(100+y)/100;
			komib=nukib*(100+y)/100;
			maxi=max(maxi,komia+komib);
			skip:;
		}
		cout<<maxi<<endl;
	}
	return 0;
}

problemB--連鎖消滅パズル-- (AOJ1193)

消滅は横方向のみで、フィールドの横の長さが5固定･縦の長さが1~10で可変であるパズドラ。
バグらせないようにやるだけ。

#include <iostream>
#define EMP -1000
 
using namespace std;

int stage[11][11]={};
int h;


void outStage(){
	for(int i=0;i<h;i++){
		for(int j=0;j<5;j++){
			cout<<stage[i][j];
		}
		cout<<endl;
	}
}

bool delStage(){
	bool conti=false;
	for(int i=0;i<h;i++){
		for(int j=0;j<3;j++){
			int samecount=1;
			int now=-1;
			for(int k=0;;k++){
				if(now==-1){					
					now=stage[i][j+k];
				}
				else if(now==stage[i][j+k] && now!=EMP){
					samecount++;
				}
				if( (now!=-1 && now!=stage[i][j+k]) || k==4){
					if(samecount>=3){
						conti=true;
						for(int l=0;l<samecount;l++){
							stage[i][j+l]=EMP;
						}
						samecount=1;
					}
					goto end;
				}
			}
			end:;
		}
	}
	return conti;
}


void downNum(){
	for(int t=0;t<h;t++){
		for(int i=1;i<h-t;i++){
			for(int j=0;j<5;j++){
				if( i-1>=0 && stage[i][j]==EMP){
					swap(stage[i][j],stage[i-1][j]);
				}
			}
		}
	}
}

int countScore(){
	int sum=0;
	for(int i=0;i<h;i++){
		for(int j=0;j<5;j++){
			if(stage[i][j]!=EMP)
				sum+=stage[i][j];
		}
	}
	return sum;
}

int main(){
	while(1){
		int sum=0;
		cin>>h;
		if(h==0)break;
		for(int i=0;i<h;i++){
			for(int j=0;j<5;j++){
				cin>>stage[i][j];
				sum+=stage[i][j];
			}
		}
//end input;

		while(1){
			if(delStage()==false)break;
			downNum();
		}
		cout<<sum-countScore()<<endl;
	}
	return 0;
}

problemD--暗号化システム-- (AOJ1195)

アルファベットからなる20文字以下の文字列を先頭から見ていき、そのアルファベットが1度目の出現であれば一つ小さくする(ex: b->a , z->y)というガバガバな方式で暗号化された文字列の、変換前文字列の候補を列挙する。
それぞれのアルファベットにつき最大でも2通りしか無いので、最大で2^20回試行となり間に合う。

先頭から順に確定させていき、今見ているアルファベットが「暗号化前文字列にすでに出現しているか、'a'」であればそのまま暗号化前文字列につっこみ、「暗号化前文字列にまだ出現していない、かつ'z'ではない」であれば一つ大きくしたアルファベットを暗号化前文字列につっこむ。
みたいなことを幅優先探索でやって解いた。
これでやると自然に辞書順にソートされるのでソートは不要となり、オーダーはo(2^n)となる。
ソートが必要となるとo( 2^n + (2^n)log(2^n) )となるので(ICPC以外では)ちょっとヤバそう。
よくわからないのでまたAOJに入ったら投げてみよう。

※追記:0.02sで通りました。やったぜ！

#include <vector>
#include <iostream>

using namespace std;

vector<string> ans;
bool ap[30];
string s;
int sum;

void dfs(int n,char c,string now){
//cout<<"dfs(int "<<n<<",char "<<c<<",string "<<now<<")"<<endl;
	if(n==s.size()){
		sum++;
		ans.push_back(now);
		return ;
	}
	if(ap[c-'a']==true || c=='a'){
		bool bac=ap[c-'a'];
		ap[c-'a']=true;
		dfs(n+1,s[n+1],now+c);
		ap[c-'a']=bac;
	}
	if(ap[c-'a'+1]==false && c!='z'){
		bool bac=ap[c-'a'+1];
		ap[c-'a'+1]=true;
		dfs(n+1,s[n+1],now+(char)(c+1));
		ap[c-'a'+1]=bac;
	}
}

int main(){
	while(1){
		while(!ans.empty())ans.pop_back();
		sum=0;
		cin>>s;
		if(s=="#")break;
		dfs(0,s[0],"");
		cout<<sum<<endl;

		if(sum<=10){
			for(int i=0;i<sum;i++){
				cout<<ans[i]<<endl;
			}
		}
		else{
			for(int i=0;i<5;i++){
				cout<<ans[i]<<endl;
			}
			for(int i=ans.size()-5;i<ans.size();i++){
				cout<<ans[i]<<endl;
			}
		}
	}
	return 0;
}

おしまい。