kmjp's blog

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

DigitalArts プログラミングコンテスト2012 : B - Password

続いて2問目。
答えが色々ある問題。
http://digitalarts2012.contest.atcoder.jp/tasks/digitalarts_2

文字列の合計値が変わらない範囲で、別の文字列を答える問題。

文字数は1~20なので、合計値が最小となる"a"と最大となる"zzzzzzzzzzzzzzzzzzzz"は別の文字列で合計数をそろえられない。
それ以外は必ず解がある。

ここでは以下のように場合分けしてみた。

  • aだけで構成されている場合~

最後のaを消して1つ前のaをbにする。

  • 20文字未満の場合~

aじゃない文字を1つ探して1つ減らし、最後にaを付け加える

  • それ以外、つまりa以外を含む20文字の場合

最大の文字を1減らし、最小の文字を1増やす。


char line[100];
char fir[100];


void solve() {
	int x,y,i,j,l;
	
	GETs(line);
	strcpy(fir,line);
	
	l=strlen(line);
	if(strcmp(line,"a")==0 || strcmp(line,"zzzzzzzzzzzzzzzzzzzz")==0) {
		_P("NO\n");
		return;
	}
	sort(line,line+l);
	reverse(line,line+l);
	
	//全部a
	if(line[0]=='a') {
		line[l-2]++;
		line[l-1]=0;
	}
	else if(l!=20) {
		line[0]--;
		line[l]='a';
		line[l+1]=0;
		_P("%s\n",line);
		return;
	}
	else {
		line[0]--;
		line[l-1]++;
		if(strcmp(line,fir)==0) {
			FOR(i,l) {
				FOR(j,l) {
					if(line[i]!=line[j]) {
						x=line[i];
						line[i]=line[j];
						line[j]=x;
						goto out;
					}
				}
			}
		}
		out:
		;
	}
	
	_P("%s\n",line);
	
	return;
}

まとめ

ほかの人の回答も見たけど、やり方はいろいろだね。
その意味で単純だけど面白い問題。

広告を非表示にする