kmjp's blog

競技プログラミング参加記です

AtCoder ARC #019 : A - お買い物クライシス、B - こだわりの名前

ARC#019に参加。
Cが想定外に手こずったが、周りも手こずった人が多かった様子。
Dが微妙な部分点しか取れなかったが、それでもなかなか好順位で終わることができた。
http://arc019.contest.atcoder.jp/tasks/arc019_1
http://arc019.contest.atcoder.jp/tasks/arc019_2

A - お買い物クライシス

文字列中以下のルールでアルファベットを数値に置き換えよ。
O → 0
D → 0
I → 1
Z → 2
S → 5
B → 8

やるだけ。あと3秒でFAだった…。

void solve() {
	int f,i,j,k,l,x,y;
	string S;
	cin>>S;
	FOR(i,S.size()) {
		if(S[i]=='O') S[i]='0';
		if(S[i]=='D') S[i]='0';
		if(S[i]=='I') S[i]='1';
		if(S[i]=='Z') S[i]='2';
		if(S[i]=='S') S[i]='5';
		if(S[i]=='B') S[i]='8';
		
	}
	cout << S << endl;
}

B - こだわりの名前

L文字の文字列Sが与えられるので、そのうち1文字を別のアルファベットに変えたい。
変えた後の文字列のうち回文でないものの数を答えよ。

まず最初に、初期状態で何か所回文でない文字の対(S[i],S[L-1-i])があるかカウントしておく。

後は各文字を1文字変えるとき、回文となるかどうかを判定していく。

  • 奇数文字の真ん中を変える場合:
    • すでに回文なら、その文字を何に変えても回文になるので0通り。
    • まだ回文じゃないなら、真ん中を変えても回文にならないので25通り。
  • それ以外のS[i]を変える場合:
    • 今見ているのがi文字目で、S[i]とS[L-1-i]文字が一致せず、かつそれ以外がすべて回文になっているなら、S[i]とS[L-1-i]文字を一致させると全体が回文になってしまうのでそれ以外24通りを選べばよい。
    • すでに全体が回文なら、S[i]を他の文字に変えれば回文じゃなくなるので25通り。
    • その他のケースは他の文字で回文にならない場所がある場合なので、S[i]は何に変えても良く、25通り。
int rot[400000];

void solve() {
	int f,i,j,k,l,x,y;
	
	string S;
	cin>>S;
	l=S.size();
	FOR(i,l) rot[i]=(S[i]!=S[l-1-i]);
	int r=count(rot,rot+l,1);
	
	int ret=0;
	FOR(i,l) {
		if(i==l-1-i) {
			if(r) ret += 25;
		}
		else {
			if(r==0) ret+=25;
			else if(r==2 && S[i]!=S[l-1-i]) ret+=24;
			else ret+=25;
		}
	}
	cout << ret << endl;
	
}

まとめ

地味にBで頭がこんがらがって手こずった…。

広告を非表示にする