SRM719 Lv1 : LongMansionDiv1
作成日：2017.08.15
最終更新日：2017.08.15
問題概要
$N$行$\infty$列のマス目があり、行には$0$から$N-1$まで番号が振られている。
$i$行目にあるマスを通るには$t_i$だけ時間がかかり、始点や終点においても同じだけかかる。
このマス目上で$(sX,sY)$から$(eX,eY)$へ移動する時の最短時間を求めよ。
制約
$1 \leq N \leq 50$
$1 \leq t_i \leq 1000$
$0 \leq sX,eX \leq N-1$
$0 \leq sY,eY \leq 10^9$
考え方
同じ行のマスならばかかる時間は同じであるから、$sY=eY$の時は寄り道しない経路が最善である。
また$sY \neq eY$の時も同様に考えることで、少なくとも列が変わる方向には寄り道しない方が良いことが分かる。
各列で行が変わる方向への移動をすると考えづらいので、ある列での移動を隣の列に移すことを考える。
このことによって変化する時間は行方向への移動の始点と終点がそれぞれ$i,j$行にある時、$\pm (t_i - t_j)$である。
このうち少なくとも一方は$0$以下であるので、そのような方に動かすとして良い。
またこれにより移動が重なって打ち消しあった時、その分だけかかる時間を減らすことができる。
これを繰り返していくことで、始点と終点のある列以外は行が変わる方向の移動をしなくて良いことが分かる。
すなわちかかる時間が最小となる経路は、ある行$i$が存在して$(sX,sY)$ $\rightarrow$ $(i,sY)$ $\rightarrow$ $(i,eY)$ $\rightarrow$ $(eX,eY)$を順に線分で結ぶ経路として表すことができる。
$i$は$N (\leq 50)$しかないので全探索可能である。
ソースコード
マクロ等はこちら
class LongMansionDiv1 {
LL s[1010];
public:
LL minimalTime(vector<int> t, int sX, int sY, int eX, int eY) {
int N = t.size();
s[0] = 0;
repp(i,0,N) s[i+1] = s[i] + t[i];
LL dY = abs(sY-eY)-1;
LL ans = 123456789012345678;
repp(i,0,N){
ans = min(ans , s[max(i,sX)+1]-s[min(i,sX)]+s[max(i,eX)+1]-s[min(i,eX)]+t[i]*dY);
}
return ans;
}
};解法まとめ
$(sX,sY)$ $\rightarrow$ $(i,sY)$ $\rightarrow$ $(i,eY)$ $\rightarrow$ $(eX,eY)$という経路を通るのにかかる時間の最小値を行$i$についての全探索により求める。(8-12行)
$sX$と$eX$、$sY$と$eY$に大小関係が定まっていないことに注意する。
SRM719の他の問題 Lv2 Lv3