開催時間中空の上にいたので不参加でした。
http://community.topcoder.com/stat?c=problem_statement&pm=14933
問題
N要素の数列が与えられる。各要素は1~100である。
要素の値をいくつか動かし、全体を等差数列となるようにしたい。
各要素動かす値の絶対値の総和の最小値を答えよ。
解法
初項と公差を総当りすればよい。
初項は0以下や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もミスしていたので結果的には出ないで助かったことになる。