AtCoder Marketを解いてみた！
注意
初心者なので、至らない点が多々あると思います。
先にお詫び申し上げます。
問題
問題文
Atcoderマーケットは、$100 \ 000 \ 000$個のマスが1列に繋がったマス目で表されるスーパーマーケットである。ここでは、左から$i$番目のマスを「マス$i$」とする。
ある日、$N$人の買い物客がAtcoderマーケットに来る。$i$人目の買い物客は、マス$A_i$にある品物とマス$B_i$にある品物を買う。
square1001君は、Atcoderマーケットに入口と出口を$1$つずつ設置することにした。
入口と出口はいずれかのマス目に設置する。入口と出口は同じ場所にあってよい。
そのとき、買い物客は次のような経路で移動する。
・まず、入口からスタートする。マス$A_i$とマス$B_i$を経由して、出口でゴールする。
全ての買い物客について、隣り合ったマス目に進むのに$1$秒かかるとき、最適に入口と出口を設置したときの「すべての買い物客の移動時間の合計」の最小値を求めなさい。
制約
- $1 \leq N \leq 30$
- $1 \leq A_i \lt B_i \leq 100 \ 000 \ 000$
解法
方針
小さい問題に分けて考える。
やってみる
小さい問題に分ける
まず、買い物客の経路を分けて考える。
買い物客の経路は次の$2$通りである。
- 入口→マス$A_i$→マス$B_i$→出口
- 入口→マス$B_i$→マス$A_i$→出口
マス$A_i$→マス$B_i$とマス$B_i$→マス$A_i$の移動時間は等しく、入口と出口の位置に関係しないので、それらを除いた経路を考えればよい。
また、$2$において、制約より$A_i \leq B_i$なので、
入口→マス$B_i$=入口→マス$A_i$→マス$B_i$
マス$B_i$→マス$A_i$は余分だとわかる。
以上より、$1$が最短経路である。
この移動時間を最小化するには、入口→マス$A_i$とマス$B_i$→出口の移動時間を最小化すればよい。
入口→マス$A_i$の移動時間は、出口の位置に関係せず、マス$B_i$→出口の移動時間は入口の位置に関係しないので別々に分けて考えることができる。
移動時間を最小化する方法
入口のあるマスをマス$X$とおく。
$A_i \leq A_j$なる$A_i,A_j$において、入口→マス$A_i$と入口→マス$A_j$の移動時間の和を求めると次の$2$つの場合がある。
- $A_i \leq X \leq A_j$を満たす
$$ (X-A_i)+(A_j-X)=A_j-A_i $$ - $X \lt A_i,A_j \lt X$を満たす
2.1 $X \lt A_i$のとき
$$ \begin{align} (A_i-X)+(A_j-X)&=(A_i-X)+(A_j-A_i)+(A_i-X) \\ &=(A_j-A_i)+2 \cdot (A_i-X) \gt A_j-A_i \end{align} $$
2.2 $A_j \lt X$のとき
$$ \begin{align} (X-A_i)+(X-A_j)&=(X-A_j)+(A_j-A_i)+(X-A_j) \\ &=(A_j-A_i)+2 \cdot (X-A_j) \gt A_j-A_i \end{align} $$
以上より、入口→マス$A_i$と入口→マス$A_j$の移動時間の和の最小値は$A_j-A_i$とわかる。
ここで、$A_i$を数列とみて、$A_i \leq A_j \ (i< j)$を満たすように並び替えたものを$A_i \prime$とおく。
$i \leq \frac{N}{2},j=N-i+1$として、全ての$i$における入口→マス$A_i \prime$の移動時間の総和の最小値を$2$つの場合に分けて考える。
- $N$が偶数の場合
$i=1,2 \ldots \frac{N}{2}$となり、$i \lt j$より、
$X=A_{\frac{N}{2}} \prime$とすると、
全ての$i,j$において$A_i \prime \leq X,X+1 \leq A_j \prime$より$A_i \prime\leq X \lt A_j \prime$だから、最小値は$\sum_{i=1}^{\frac{N}{2}} A_j \prime-A_i \prime$となる。 - $N$が奇数の場合
$i=1,2, \ldots \lfloor \frac{N}{2} \rfloor$となり、$i \lt j$より、
$X=A_{\lceil \frac{N}{2} \rceil} \prime$とすると、
全ての$i,j$において$A_i \prime \leq X \lt A_j \prime$だから、最小値は$\sum_{i=1}^{\lfloor \frac{N}{2} \rfloor} A_j \prime-A_i \prime+A_{\lceil \frac{N}{2} \rceil} \prime-X=\sum_{i=1}^{\lfloor \frac{N}{2} \rfloor} A_j \prime-A_i \prime$となる。
以上より、全ての$i$における入口→マス$A_i$の移動時間の総和の最小値は$\sum_{i=1}^{\lfloor \frac{N}{2} \rfloor} A_j \prime-A_i \prime$
入口→マス$B_i$についても同様に考えて、$B_i \leq B_j \ (i< j)$を満たすように並び替えたものを$B_i \prime$とおくと、最小値は$\sum_{i=1}^{\lfloor \frac{N}{2} \rfloor} B_j \prime-B_i \prime$
まとめると、「すべての買い物客の移動時間の合計」の最小値は、
$$
\sum_{i=1}^{N} (B_i-A_i)+\sum_{i=1}^{\lfloor \frac{N}{2} \rfloor} (A_{N-i+1} \prime-A_i \prime+B_{N-i+1} \prime-B_i \prime)
$$
計算量オーダーは$O(N \cdot \log_{2} N)$となり、$1 \leq N \leq 30$から、実行時間制限内に収まるとわかる。
感想・まとめ
自分としては、結構綺麗に解けたんじゃないかなと思っています。
並べ替えることに気づいたのが良かったです。
