TopCoder SRM 774 : Div1 Medium ClassRankings

ECRをあきらめてこれを書いている…。
https://community.topcoder.com/stat?c=problem_statement&pm=14803

問題

3つの学校がそれぞれの生徒数A[3]が与えられる。
彼らがテストを受けたところ、i番目の学校の生徒はL[i]以上H[i]以下の得点を得ていることが分かった。
また、彼ら全員が異なる得点を得たとする。

生徒を得点順に並べ、その学校番号を並べた文字列を作るとき、文字列の構成法は何通りか。

解法

文字列の先頭から1文字ずつ決めていくわけだが、後のことを考えると生徒の得点は後の選択肢が広がるよう、同じ文字列のprefixを定めるなら極力低いほうがよい。
すなわち、prefixの最後の生徒の得点がx点なら、次の生徒は(x+1)点以上で低ければ低いほうが良い。

f(x,a,b,c) := prefixに含まれない3校の生徒の残人数がa,b,c人であり、prefixの最後の生徒の最少得点がx点であるようなく見合わせ数
ここから、f(x',a-1,b,c)、f(y',a,b-1,c)、f(z',a,b,c-1)に遷移させていこう。
x',y',z'以降はx+1点以上で最小の各学校の生徒がとりうるスコアである。

なお、この問題はTLE/MLEが割と厳しい。
自分は最初書いたらTLEしたので、配列の添え字順を変えたら通った。
ほかにも得点の座標圧縮などで処理を絞ることも考えられる。

class LandSplitter {
	public:
	long long cheapest(int N, int A, int B) {
		ll mi=1LL<<60;
		
		for(ll i=1;1LL*A*i<=N;i++) {
			ll a=1LL*i*A;
			ll b=1LL*i*B;
			
			if(a<=N&&N<=b) {
				ll pat=0;
				if(A==B || b==N) {
					pat=1LL*B*(N/B)*(N-B);
				}
				else {
					ll lef=N-a;
					int nb=lef/(B-A);
					pat+=1LL*nb*B*(N-B);
					pat+=1LL*(A+(lef%(B-A)))*(N-(A+(lef%(B-A))));
					pat+=1LL*(i-nb-1)*A*(N-A);
				}
				mi=min(mi,pat);
			}
			
		}
		if(mi==1LL<<60) return -1;
		mi/=2;
		return mi;
	}
}

まとめ

Win10環境に移行したら漢字変換の学習結果が消えてしまい非常に文章が打ちづらくなった。