Google Code Jam 2022 Round 1A : A. Double or One Thing

満点で突破できてよかったね。
https://codingcompetitions.withgoogle.com/codejam/round/0000000000877ba5/0000000000aa8e9c

問題

文字列Sが与えられる。
S中いくつかの位置を選び、その文字を倍化できるものとする。
こうして得られる文字列のうち、辞書順最小のものを求めよ。

解法

手前から1つずつ、「この文字を倍化した場合、倍化する前より辞書順で小さくなるか」をどん欲に試せばよい。
文字列長が小さいのでこれで十分間に合う。

string S;
int N;

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>S;
	N=S.size();
	string R;
	FOR(i,N) {
		string A=S.substr(i);
		string B=S[i]+S.substr(i);
		if(B<A) {
			R+=S[i];
			R+=S[i];
		}
		else {
			R+=S[i];
		}
	}
	
	cout<<"Case #"<<_loop<<": "<<R<<endl;
}

まとめ

まぁこれはすんなり。