yukicoder No.322 Geometry Dash

問題文

http://yukicoder.me/problems/884

解法

開始地点に戻される時間は順序に関係なく一定なので無視してもよい。 よって最小化すべきは次の値である。

$$ S=D_1T_1+D_2(T_1+T_2)+D_3(T_1+T_2+T_3)+\cdots+D_N(T_1+\cdots+T_N) $$

とりあえず$(D_2,T_2)$と$(D_3,T_3)$を入れ替えてみる。

$$ S=D_1T_1+D_3(T_1+T_3)+D_2(T_1+T_3+T_2)+\cdots+D_N(T_1+\cdots+T_N) $$

すると$S$は$D_2T_3-D_3T_2$だけ変化することが分かる。 一般に$(D_i,T_i)$と$(D_{i+1},T_{i+1})$を入れ替えると、$D_iT_{i+1}-D_{i+1}T_i$だけ変化する。

このことから$D_iT_{i+1}-D_{i+1}T_i \gt 0$なら$i$と$i+1$をswapするという操作を繰り返すことで最大値が得られることがわかる。 しかし実際にこの操作を行うのは時間的に厳しいので、比較関数$D_i T_j - D_j T_i \gt 0$を使ってソートしてあげよう。

iとi+1をswapする操作がソートになるのはバブルソートを考えれば明らか。 隣同士を入れ替えるだけだと局所的最適解に陥るのではと思うかもしれないが、 この比較関数は全順序なのでソート結果が一意に定まる。

yukicoder No.322 Geometry Dash

隣同士以外を入れ替えて変化量を見ると気づきにくい。 ところでこれってD[i]/T[i]でソートしているとも見れるのだけれど、 D[i]/T[i]は何を意味してるんだろう。