TopCoderOpen 2013 Round1A Easy HouseBuilding

初のTCO参加。Round1B/1Cは日程的に出られないので、1Aで抜けておきたい。
結局、Mediumはsubmitしたものの計算量見積もりミスで失敗。
Easyをかなり速く解けたので、それで1Aを突破。
http://community.topcoder.com/stat?c=problem_statement&pm=12396

問題

最大50x50の広さの土地について、各点の高さが0-9で与えられる。
土地の高さを1変更するのに1の労力がかかる。
土地の高さの差を最大1以内に抑えるのに必要な最小労力を答える。

解法

さほど土地の広さが無いので、最低の高さを0～8で全部試してみればよい。

class HouseBuilding {
	public:
	int getMinimum(vector <string> area) {
		int H=area.size();
		int W=area[0].size();
		
		int mi=1<<30;
		int th,x,y;
		
		for(th=0;th<=8;th++) {
			int t=0;
			int th2=th+1;
			
			FOR(y,H) FOR(x,W) {
				int hoge=area[y][x]-'0';
				t += min(abs(hoge-th),abs(hoge-th2));
			}
			mi=min(mi,t);
		}
		return mi;
	}

};

まとめ

今回、かなりEasyの早解きになりそうな雰囲気だったので速く解けて良かった。
でも25pt落とすと予選から落ちるので、怖くてチャレンジ出来なかったな…。