東京工業大学プログラミングコンテスト2015 : C - おおおかやま、D - 文字列と素数

50ptといいつつA,Bとだいぶ難易度差がある。
http://ttpc2015.contest.atcoder.jp/tasks/ttpc2015_c
http://ttpc2015.contest.atcoder.jp/tasks/ttpc2015_d

C - おおおかやま

文字列Sに"ookayama"という文字列の前に"o"が１個以上ある部分文字列がある場合、以下の処理を行え。

• 上記部分文字列のうち最長のものをTとする。
• T中"OO"という文字の並びがあれば、最も左のものを"o"に置換する。
• 上記条件を満たすものがなく、T中"oo"という文字の並びがあれば、最も左のものを"O"に置換する。

最終的なSの値を求めよ。

変換対象の部分文字列の範囲は交差しないので、各条件を満たす部分文字列について愚直に処理を繰り返せばよい。
以下のコードは愚直に処理を繰り返しているが、prefixは"o"の文字が３文字ごとに変換後結果が周期性を持つことを用いるともっと簡単に書ける。

string hoge(string s) {
	int dodo=1;
	int i;
	while(dodo) {
		dodo=0;
		FOR(i,s.size()-1) if(s[i]=='O' && s[i+1]=='O') {
			dodo=1;
			s=s.substr(0,i)+"o"+s.substr(i+2);
			goto out;
		}
		FOR(i,s.size()-1) if(s[i]=='o' && s[i+1]=='o') {
			dodo=1;
			s=s.substr(0,i)+"O"+s.substr(i+2);
			goto out;
		}
		
		out:
		;
	}
	return s;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>s;
	
	for(i=s.size()-8;i>=0;i--) {
		if(s.substr(i,8)=="ookayama"&& i && s[i-1]=='o') {
			int len=8;
			while(i&&s[i-1]=='o') i--,len++;
			s=s.substr(0,i)+hoge(s.substr(i,len))+s.substr(i+len);
		}
	}
	cout<<s<<endl;
}

D - 文字列と素数

アルファベット小文字で構成された文字列Sがある。
各小文字を1,3,5,7,9のいずれかに対応付けたとき、Sが素数になることはあるか。
あるならその一例を示せ。
なお、異なる小文字を同じ整数に対応付けることはできない。

アルファベットは最大５種類しか登場しないはずなので、5!通り数字とアルファベットの対応を愚直に総当たりすればよい。

bool isprime(ll v) {
	if(v==1) return false;
	for(ll i=2;i*i<=v;i++) if(v%i==0) return false;
	return true;
}

void dfs(string s,int mask) {
	int i;
	char a='0';
	FORR(r,s) {
		if(r>='a' && r<='z') {
			a=r;
			break;
		}
	}
	
	if(a=='0') {
		ll b=atoll(s.c_str());
		if(isprime(b)) {
			cout<<b<<endl;
			exit(0);
		}
	}
	else {
		FOR(i,5) if((mask&(1<<i))==0) {
			string t=s;
			FORR(r,t) if(r==a) r='1'+2*i;
			dfs(t,mask|(1<<i));
		}
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>s;
	dfs(s,0);
	cout<<-1<<endl;
}

まとめ

ここまではすんなり。