kmjp's blog

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

CODE FESTIVAL 2016 Qual A : C - 次のアルファベット / Next Letter

RoundBは全完できて良かったけど、AはDに手間取ってグダグダだった。
http://code-festival-2016-quala.contest.atcoder.jp/tasks/codefestival_2016_qualA_c

問題

文字列Sが与えられる。
どこかの文字を選んで(アルファベット小文字の範囲で)1つ手前にrotateする、という処理をK回行う。
そうして得られる辞書順最小の文字列は何か。

解法

辞書順最小を求めるので、先頭に近いものほど文字を小さくしたい。
そこで、先頭から順に、K回分に達するまで'a'に向けてrotateを繰り返そう。
全部'a'になってもK回に達しない場合、しょうがないので末尾の数を残りの数だけrotateする。

string S;
int K;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S>>K;
	FORR(c,S) {
		if(c=='a') continue;
		x='z'+1-c;
		if(x<=K) {
			c='a';
			K -= x;
		}
	}
	
	K %= 26;
	while(K--) {
		if(S.back()=='z') S.back()='a';
		else S.back()++;
	}
	cout<<S<<endl;
	
}

まとめ

先日の
AIM Tech Round 3 : Div1 A. Letters Cyclic Shift - kmjp's blog
に似ている。