TopCoder SRM 646 Div1 Easy TheConsecutiveIntegersDivOne

SRM646は不参加。
Easyは割と簡単に解けたかと思ったけど凡ミスしていたので出なくてよかったかな。
Mediumは先にTwitterでDijkstra+座標圧縮というヒントを見てしまっていたのであっさり解けたけど、ヒントなしで解けていたか不明。
http://community.topcoder.com/stat?c=problem_statement&pm=13625

問題

N要素の数の集合numbersがある。
各要素を増減して、K要素以上が連続した整数列となるようにしたい。
増減する数の最小値を求めよ。

解法

先日のSRM645のDiv2 Mediumで、車両の長さが1固定だと思えばよい。
TopCoder SRM 645 Div2 Medium ConnectingCars - kmjp's blog

numbersをソートして、連続したK要素の部分列に対し、SRM645 Div2 Medium相当の処理をして最小値を取るだけ。

class TheConsecutiveIntegersDivOne {
	public:
	int find(vector <int> numbers, int k) {
		int N=numbers.size();
		int mi=1000000000,i,x,y;
		
		sort(numbers.begin(),numbers.end());
		FOR(x,N) numbers[x]-=x;
		FOR(x,N) if(x+k<=N) {
			for(y=x;y<x+k;y++) {
				int tot=0;
				for(i=x;i<x+k;i++) tot+=abs(numbers[y]-numbers[i]);
				mi=min(mi,tot);
			}
		}
		
		return mi;
		
	}
}

まとめ

なぜこんな短期間に似たような問題出したんだろ。