SRM 545 div1 easy: StrIIRec - mayoko’s diary

問題

a, b, c, ... (a から n 番目の文字) を 1 回ずつ使って長さ n の文字列 s を作る。このとき, 以下の条件が成り立つようにしたい。

s は minStr よりも辞書順で後ろ
s は最低でも minInv 個の反転文字を持つ(i < j, s[i] > s[j] というやつ)

これらを満たす辞書順で最小の文字列を求めよ。

解法

貪欲に解けます。

まず, n 文字で得られる最大の反転文字数は n*(n-1)/2 となることに注意します。

例えば先頭の文字 c を決定した場合, 反転文字の個数の最大値は (c 未満のアルファベットの数) - (n-1 文字で得られる最大の反転文字数) となり, もしこれが minInv よりも小さかったら先頭の文字を c にしてはいけません。逆にこれが minInv より大きく, かつ「minStr より辞書順で小さくなることがない」ことが成り立つのであれば, 貪欲に c を選ぶべきです。

これを繰り返せば文字列を得られます。

int calc(int n) {
	return n*(n-1)/2;
}

bool done[22];

class StrIIRec {
public:
	string recovstr(int n, int minInv, string minStr) {
		memset(done, false, sizeof(done));
		string ret;
		bool flag = false;
		int now = 0;
		for (int i = 0; i < n; i++) {
			int index = -1;
			cout << i << " " << now << " " << ret << endl;
			for (int j = 0; j < n; j++) {
				if (done[j]) continue;
				char c = (char)('a'+j);
				int cnt = 0;
				for (int k = 0; k < j; k++) 
					if (!done[k]) cnt++;
				cnt += calc(n-i-1);
				bool ok = (i >= minStr.size());
				if (!ok) ok |= (flag || c >= minStr[i]);
				if (now+cnt >= minInv && ok) {
					index = j;
					now += cnt-calc(n-i-1);
					flag |= c > minStr[i];
					break;
				}
			}
			if (index == -1) return "";
			ret += (char)('a'+index);
			done[index] = true;
		}
		return ret;
	}
};