A~Eを解いたと思ったらCミスしてるしD誤差死してるし散々。
http://codeforces.com/contest/600/problem/C
問題
アルファベット小文字で構成される文字列がある。
この文字列のうち何文字かを別の文字に変換できる。
また、並び順を任意に並べ替えられる。
この文字列から変換・並べ替えをして生成できる回文を成す文字列のうち、変換数最小のものの中で辞書順最小なものを求めよ。
解法
まず各文字の登場回数を求める。
奇数回の登場回数の文字があれば、それが1個以下になるまで変換により増減させなければならない。
辞書順最小なものを生成するため、辞書順最大の奇数回登場の文字を辞書順最最小の奇数回登場に変換するようにしていくと良い。
各アルファベットの登場回数を確定させたら、辞書順小さい順に前から(と回文なので後ろも)詰めていこう。
ただし元の文字列が奇数長の場合、奇数回登場する文字が1個あるはずなので、中央にはその文字が来るようにすること。
string S; int num[26]; void solve() { int i,j,k,l,r,x,y; string s; cin>>S; FORR(r,S) num[r-'a']++; x=0,y=25; while(x<y) { while(x<26&&num[x]%2==0) x++; while(y>=0&&num[y]%2==0) y--; if(x>=y) break; num[x]++; num[y]--; } string T=S; x=0; FOR(i,26) { FOR(y,num[i]/2) T[x]=T[S.size()-1-x]='a'+i, x++; if(num[i]%2) T[S.size()/2]='a'+i; } cout<<T<<endl; }
まとめ
ここ数回、CFの調子がすこぶる悪い。