TopCoderOpen 2018 Round2A Easy ArithmeticSequenceDiv1

開催時間中空の上にいたので不参加でした。
http://community.topcoder.com/stat?c=problem_statement&pm=14933

問題

N要素の数列が与えられる。各要素は1～100である。
要素の値をいくつか動かし、全体を等差数列となるようにしたい。
各要素動かす値の絶対値の総和の最小値を答えよ。

解法

初項と公差を総当りすればよい。
初項は０以下や101以上が最適になる場合もある(100,100,98,97,96など)ので注意すること。

class ArithmeticSequenceDiv1 {
	public:
	int findMinCost(vector <int> x) {
		ll ret=1LL<<60;
		for(int s=-200;s<=200;s++) {
			for(int d=-100;d<=100;d++) {
				ll dif=0;
				for(int i=0;i<x.size();i++) dif += abs(x[i]-(s+i*d));
				ret=min(ret,dif);
			}
		}
		return ret;
	}
}

まとめ

EasyもMediumもミスしていたので結果的には出ないで助かったことになる。