Codeforces #55 (div2) C "Title"

問題：http://codeforces.com/problemset/problem/59/C

プラクティス．

使うアルファベットの数と小文字と？で書かれた文字列が与えられる．アルファベットの数すべてを用いて，与えられた文字列の？をアルファベットに置き換えたものが回文（Palindrome）になっている文字列のうち辞書順で最初になるものを求める．

まず，反対側が普通の文字である？を埋め，現在使われている文字とこれから使える文字数をカウントする．これが使うべきアルファベットの数よりも小さいと上記の条件を満たせない．あとは，使うべきアルファベットを埋めつつ？を全部置き換える．使うべきアルファベットはそれぞれ一回ずつ使えばいいので，中心を終点とした部分文字列を考えたときに，その部分文字列の最後のほうでそのアルファベットを使って，残りの部分をaで埋めればいいと考えて実装．あとは文字列の長さが奇数のときの処理を無駄に記述．

コード

import java.util.*;

public class C_Title {
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int k = s.nextInt();
		char cs[] = s.next().toCharArray();
		int r = 0, n = cs.length;
		BitSet used = new BitSet();
		for (int i = 0; i < n / 2; ++i) {
			char a = cs[i], b = cs[n - i - 1];
			if (a != '?' && b != '?' && a != b) {
				System.out.println("IMPOSSIBLE");
				return;
			}
			if (a == '?' && b != '?') {
				cs[i] = b;
				used.set(b - 'a');
			} else if (a != '?' && b == '?') {
				cs[n - i - 1] = a;
				used.set(a - 'a');
			} else if (a == '?' && b == '?') {
				++r;
			} else {
				used.set(a - 'a');
			}
		}
		if (n % 2 > 0) {
			if (cs[n / 2] == '?') {
				++r;
			} else {
				used.set(cs[n / 2] - 'a');
			}
		}
		int c = used.cardinality();
		if (k > r + c) {
			System.out.println("IMPOSSIBLE");
			return;
		}
		int p = 0;
		for (int i = 0; i < n / 2; ++i) {
			if (cs[i] == '?') {
				--r;
				if (r < k - c) {
					p = used.nextClearBit(p);
					cs[i] = cs[n-i-1] = (char)('a' + p);
					used.set(p);
				} else {
					cs[i] = cs[n - i - 1] = 'a';
				}
			}
		}
		if (n % 2 > 0) {
			if (cs[n / 2] == '?') {
				if(r < k - c){
				cs[n/2] = (char)('a' + used.nextClearBit(p));
				}else{
					cs[n/2] = 'a';
				}
			}
		}
		System.out.println(new String(cs));
	}
}