SRM545 275pt : StrIIRec

問題概要

アルファベットの先頭n(<20)文字を適当に並び替える。このときできる文字の転倒数がa以上で、かつ文字が辞書順でstrより小さくないような中で辞書順最小のものを求める問題。

考えたこととか

• 辞書順最小の何かを構成する問題なのでいつものパターンで行けるか？
• 先頭からみていって、yes/noを返す判定関数を作れさえすれば良い。nが小さいので計算量は無視してよかろう。
• えっと、今考えてる文字より後ろは余ってる文字を逆につなげてそれでできるか判定すれば良い？
• 超簡単じゃん。よし書くか。
• サンプル通らん。何故だ。
• あ、辞書順比較するタイミング、新しい文字列作るより先に判定してる。
• 修正。サンプル全部通った。
• 275だし何か引っ掛けあるのかちょっと考えてたけど、コーナーケースはなさそうだし残り時間も少ないしさっさと出すか…。
  • 何事もなく通ってた。275という感覚はなかったけど、みんなそれなりに時間かかってるしこんなもんなのか。

acceptされたコード

#include <string>
#include <algorithm>
using namespace std;

bool used[26];

struct StrIIRec {

	string recovstr(int n, int minInv, string minStr) {
		string ret = "";

		for(int i=0; i<n; ++i){
			for(int j=0; j<n; ++j)if(!used[j]){
				string tmp = ret;
				tmp += (char)('a' + j);

				for(int k=n-1; k>=0; --k)if(j!=k && !used[k]){
					tmp += (char)('a' + k);
				}

				if(tmp < minStr){
					continue;
				}

				int cnt = 0;
				for(int a=0; a<n; ++a){
					for(int b=a+1; b<n; ++b){
						if(tmp[a] > tmp[b]){
							++cnt;
						}
					}
				}

				if(cnt >= minInv){
					used[j] = true;
					ret += (char)('a' + j);
					break;
				}
			}
			if((int)ret.length() != i + 1){
				break;
			}
		}

		bool check = true;
		check &= (int)ret.length() == n;
		check &= ret >= minStr;
		int cnt = 0;
		for(int i=0; i<n; ++i){
			for(int j=i+1; j<n; ++j){
				if(ret[i] > ret[j]){
					++cnt;
				}
			}
		}
		check &= cnt >= minInv;
		return check ? ret : "";
	}

};