TopCoder SRM 719 Div1 Easy LongMansionDiv1、Div2 Medium LongMansionDiv2

Mediumに手間取ったけどChallengeのおかげでHighest更新。
https://community.topcoder.com/stat?c=problem_statement&pm=14641
https://community.topcoder.com/stat?c=problem_statement&pm=14674

問題

N行と無限個の列からなる2次元グリッドがある。
i行目のセルを通るにはT[i]のコストがかかる。
sX行sY列目のセルからeX行eY列目のセルに隣接マスをたどって移動する際、通るセルのコストの総和の最小値を求めよ。

なお、Div2はsX=0, eX=N-1, sY=0と固定されている以外Div1と同じ。

解法

sX行～eX行のセルは、縦方向に移動する過程で最低1回ずつは通過しなければならない。
横移動をする行は1つに定めて問題ない(複数の行を通って得することはない)ので、横移動する行rを総当たりしよう。
その都度(sX,sY)→縦移動→(r,sY)→横移動→(r,eY)→縦移動→(eX,eY)と移動するコストを計算して最小値を答えればよい。

計算量は手を抜いてO(N^2)、累積和を使ってO(N)だが、Nが異様に小さいのでどちらでも通る。

class LongMansionDiv1 {
	public:
	long long minimalTime(vector <int> t, int sX, int sY, int eX, int eY) {
		int N=t.size();
		int dy=abs(eY-sY);
		
		ll ret=1LL<<60;
		for(int tx=0;tx<N;tx++) {
			ll tot=(ll)t[tx]*(dy-1);
			
			for(int x=min(sX,tx);x<=max(sX,tx);x++) tot+=t[x];
			for(int x=min(eX,tx);x<=max(eX,tx);x++) tot+=t[x];
			ret=min(ret,tot);
		}
		return ret;
		
	}

}

まとめ

今回変な固有名詞が多くて問題が読みにくかった。