TopCoderOpen 2017 Round2B Easy DengklekGaneshAndChains

なんとかEasy/Medium通ったけど、Medium遅いしChallenge遅いしでレート微減。
https://community.topcoder.com/stat?c=problem_statement&pm=14604

問題

K文字も文字列C[i]が書かれたリングがN個ある。
これとは別に、M要素の数列Lが与えられる。
リングを1つ選び、任意の場所で切り離して長さL[i]の文字列を作り順に連結するとき、辞書順最大のものを答えよ。

解法

まず各リングについて切り離し後辞書順最大になるようにC[i]を回転させておこう。
以後、連結順が手前にある文字列ほど優先的に辞書順で大きなものを持ってきたいので、以下のように貪欲する。

• 残ったリングのうち、L[i]文字のprefixが最大のものを探す
• そのようなものが複数ある場合、その中で辞書順最小のものを用いる

前者は当然として、後者はのちにもっと大きなL[j]が登場する可能性があるので、そちらにより良いものを残していくことに相当する。

class DengklekGaneshAndChains {
	public:
	string getBestChains(vector <string> chains, vector <int> lengths) {
		int i;
		
		FORR(s,chains) {
			string t=s+s;
			FOR(i,s.size()) s=max(s,t.substr(i,s.size()));
		}
		
		string ret="";
		FORR(l,lengths) {
			string m="";
			FORR(c,chains) m=max(m,c.substr(0,l));
			ret += m;
			
			int id=-1;
			FOR(i,chains.size()) if(m==chains[i].substr(0,l)) {
				if(id==-1 || chains[i]<chains[id]) id=i;
			}
			chains.erase(chains.begin()+id);
		}
		
		return ret;
		
	}
}

まとめ

Div2やRound1ならともかく、Round2でなぜこれが300ptなんだ…。