kmjp's blog

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

Codeforces ECR #039 : E. Largest Beautiful Number

あと一歩で全完だったのに時間切れ。
http://codeforces.com/contest/946/problem/E

問題

整数Tが与えられる。
T未満の整数のうち、桁順を並べ替えると偶数長の回文になるものの最大値を答えよ。

解法

「桁順を並べ替えると偶数長の回文になるもの」は結局各数字の出現回数が偶数回であるものである。

Tの下からi桁目をTの物より小さい値にした場合、それより下の桁は0~9の任意の値を配置できる。
上からi桁目までの0~9の登場回数の偶奇を覚えておこう。
奇数になってしまっている数がある場合、i桁目より下の桁数がそれをカバーできるだけあるなら、i桁目以下をそのように割り当てる。

150000のような場合、下から5ケタ目を5→4とすることで条件を満たせるが、その場合149941のように余った桁を9で埋めておこう。

int T,N;
string S;

string decdec(string A) {
	for(int i=A.size()-1;i>=0;i--) {
		if(A[i]--!='0') break;
		A[i]='9';
	}
	A=A.substr(A[0]=='0');
	if(A.empty()) A="0";
	return A;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>S;
		S=decdec(S);
		N=S.size();
		
		if(N%2==1) {
			FOR(i,N-1) cout<<9;
			cout<<endl;
			continue;
		}
		if(S[0]=='1' && count(ALL(S),'0')==N-1) {
			FOR(i,N-2) cout<<9;
			cout<<endl;
			continue;
		}
		int mask=0;
		FORR(c,S) mask ^= 1<<(c-'0');
		if(mask==0) {
			cout<<S<<endl;
			continue;
		}
		FOR(i,N) {
			mask ^= 1<<(S[N-1-i]-'0');
			for(j=S[N-1-i]-'0'-1;j>=0;j--) {
				int mask2=mask^(1<<j);
				if(__builtin_popcount(mask2)<=i && (i-__builtin_popcount(mask2))%2==0) {
					S[N-1-i]=j+'0';
					for(j=i-1;j>=0;j--) {
						if(j+1>__builtin_popcount(mask2)) {
							S[N-1-j]='9';
						}
						else {
							for(x=9;x>=0;x--) if(mask2&(1<<x)) {
								S[N-1-j]=x+'0';
								mask2^=1<<x;
								break;
							}
						}
					}
					i=N;
					break;
				}
			}
		}
		cout<<S<<endl;
		
	}
}

まとめ

方針自体はあまり迷わなかった。
まぁ1ミスしてしまったけど…。