あと一歩で全完だったのに時間切れ。
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ミスしてしまったけど…。