解説スライドの「※途中で人数が負䛾数になる場合がありますが、動かす順番をうまく決めることでこ䛾状態を回避できます。」の部分が本当に回避できるのかという部分と、三分探索パートの別解の紹介です。

解説

説明の簡単のため、都市 \(0\) は都市 \(N\) を、都市 \(N+1\) は都市 \(1\) のことを表すものとします。

まず、都市 \(i\) と都市 \(i+1\) の間の道に関して、都市 \(i\) から都市 \(i+1\) の方向に通る人とその逆向きに通る人が同時に存在するような最適な移動方法は存在しません (\(\star\))。

理由

ある $2$ 人が $(p _ 0 \to p_1 \to \cdots \to i \to i+1 \to q_0 \to q_1\to \cdots)$ および $(r _ 0 \to r_1 \to \cdots \to i+1 \to i \to s_0 \to s_1\to \cdots)$ と移動するような移動方法に対して、$2$ 人の経路を $(p _ 0 \to p_1 \to \cdots \to i \to s_0 \to s_1\to \cdots)$ および $(r _ 0 \to r_1 \to \cdots \to i+1 \to q_0 \to q_1\to \cdots)$ のように変更することで、条件を満たしたまま移動コストを $2$ だけ減らすことが可能であるためです。

そして、移動コストは非負なので、このような経路の変更操作は高々有限回しか行うことができません。従って、最適な移動方法においてはある $2$ 人がすれ違うことはありません。

\(y_i\) を、都市 \(i\) から都市 \(i+1\) の方向に移動した人数 \(z_i\) が \(z_i \gt 0\) なら \(y_i = z_i\)、そうでなければ都市 \(i+1\) から都市 \(i\) の方向に移動した人数を \(z'_i\) として \(y_i=-z'_i\) と定めます。

また、都市 \(i\) と都市 \(i+1\) の間の距離を \(w_i\) とすると、(\(\star\)) の事実より移動コスト \(C\) に関して \((1)\) を得ます。

\[C = \sum _ {i = 1} ^ N w_i|y_i|.\tag{1}\]

都市 \(i\) の人数の増減に注目することで、\((2)\) を得ます。

\[b_i - c_i = y_i - y_{i-1}. \tag{2}\]

\(x\coloneqq y_0\ (=y _ N)\) とおけば、\((2)\) より \((3)\) を得ます。

\[y_i = x + \sum _ {j = 1}^{i} (b _ j - c _ j). \tag{3}\]

\(\displaystyle \sum _ {i = 1} ^ N b _ i = \sum _ {i = 1} ^ N c_i\) の制約より、\((3)\) において矛盾なく \(y_N = x\) が成立することに注意します。

さて、\(\displaystyle t_i \coloneqq - \sum _ {j = 1} ^ i (b _ j - c _ j)\) とおけば、\((3)\) より \(y _ i = x - t _ i\) が成立するので、\((1)\) よりコスト \(C\) は \(x\) にのみ依存する関数 \(C(x)\) として書け、これは \((4)\) で表されます。

\[ C(x) = \sum _ {i = 1} ^ N w _ i |x - t _ i|. \tag{4} \]

ここで、\(\forall i. w_i \gt 0\) および \(\displaystyle \sum _ {i = 1} ^ N b _ i \geq 1\) の下では、任意の整数 \(x\) に対して \(\displaystyle y _ i = x - t_i\) となるような移動方法が実際に存在することが \(C\) に関する数学的帰納法により証明できます。

証明

1. $C = 0$ の場合

$(1)$ において $w_i \gt 0$ より $\forall i. y_i=0$ となりますが、これは一切移動しないことで達成されます。

2. $C = k\; (k \gt 0)$ の場合

$0\leq C\lt k$ に対して命題が成り立つことを仮定します。

まず、$y_i\geq 1$ かつ $b_i \geq 1$ なる $i$ が存在する場合を考えます。このとき、都市 $i$ から 都市 $i+1$ へと $1$ 人を移動させることができますが、この移動を行うことで $b_i\leftarrow b_i-1,b_{i+1}\leftarrow b_{i+1}+1,y_i \leftarrow y_i-1$ へと変化し、また、$y_i \gt 0$ の下で $|y_i|-|y_i-1|=1$ なので $C\leftarrow C-w_i$ へと変化します。

ここで、$w_i \gt 0$ なので $C-w_i \lt C$ であり、また $y_i \geq 1 \Rightarrow C\geq w_i |y_i| \geq w_i \Rightarrow C - w _ i \geq 0$ なので $0 \leq C - w _ i \lt C$ がいえます。従って、帰納法の仮定より、以降の移動方法が存在することが言えます。

次に、$y_{i-1}\leq -1$ かつ $b_i \geq 1$ なる $i$ が存在する場合を考えます。これは、都市 $i$ から都市 $i-1$ に $1$ 人移動させることを考えると、上記の場合と同様に示すことができます。

最後に、$y_i \geq 1\Rightarrow b_i = 0$ かつ $y_{i-1} \leq -1 \Rightarrow b_i = 0$ の場合を考えます。$y_i \geq 1$ のとき、$b_i=0$ および $c_i\geq 0$ より $y_{i-1}=y_i-b_i+c_i=y_i+c_i \geq y_i \geq 1$ が成り立ちます。同様にして $y_{i-1} \leq -1\Rightarrow y_i\leq y_{i-1}\leq -1$ も言えます。$y_0=y_N$ であったので、(a) $\forall i. y_i\geq 1$ (b) $\forall i. y_i\leq -1$ (c) $\forall i. y_i = 0$ のいずれかが成り立ちますが、いずれの場合も以下のように矛盾を導くことができます。

(a) $\forall i. y_i\geq 1$ を仮定した場合、$y_i \geq 1 \Rightarrow b_i=0$ より$\forall i. b_i=c_i=0$ なので、$\displaystyle \sum_{i=1}^N b_i \geq 1$ に矛盾します。

(b) $\forall i. y_i\leq -1$ を仮定した場合、$y_{i-1} \leq -1 \Rightarrow b_i=0$ より$\forall i. b_i=c_i=0$ なので、$\displaystyle \sum_{i=1}^N b_i \geq 1$ に矛盾します。

(c) $\forall i. y_i = 0$ を仮定した場合、$(1)$ より $C=0$ となり $C \gt 0$ の仮定に矛盾します。

以上 1, 2 より、主張が正しいことが言えました。

従って、\(x\) は整数全体を動くとして \((4)\) の右辺を最小化すればよいですが、一旦 \(x\) は実数全体を動くとします。\((4)\) の右辺を最小化する実数 \(x\) を求めるにあたっては、次の事実が有用です。

広義単調増加な数列 \(A=(A_1,\ldots, A_N)\; (\forall i.A_i\in\mathbb{R})\) に関して、\(\displaystyle f(x)=\sum _ {i = 1} ^ N |x - A_i|\) を最小化する \(x\in\mathbb{R}\) の集合 \(X^\ast\) は、\(N\) が奇数なら \(X^{\ast}=\{A_{(N+1)/2}\}\)、\(N\) が偶数なら \(X^{\ast}=[A_{N/2},A_{N/2+1}]\) である。

これは部分問題として何度か目にしたことがあるので、知識として覚えておいて損はないと思います。

さて、\((4)\) において各 \(w_i\) は整数なので、次のように \(w_i|x-t_i|\) を分解することで先ほどの問題に帰着することができます。

\[ w_i|x-t_i| = \underbrace{|x-t_i|+|x-t_i|+\cdots +|x-t_i|}_{\normalsize w_i\ 個}. \]

従って、\((1,\ldots,N)\) を \(t_i\) の昇順に並び替えてできる順列を \(p\) とすれば、

\[ T\coloneqq (\underbrace{t_{p_1},\ldots,t_{p_1}}_{\normalsize w_{p_1}\ 個},\underbrace{t_{p_2},\ldots,t_{p_2}}_{\normalsize w_{p_2}\ 個},\ldots,\underbrace{t_{p_N},\ldots,t_{p_N}}_{\normalsize w_{p_N}\ 個}) \]

の \(\displaystyle\left\lfloor \dfrac{1}{2}\left(1+ \sum _ {i = 1} ^ N w _ i\right)\right\rfloor = \left\lceil\dfrac{L}{2}\right\rceil\) 項目、即ち \(x=T_{\lceil L/2\rceil}\) は \(C(x)\) を (実数の範囲で) 最小化し、なおかつ整数です。

以上より、本問題の解法は次のようになります。

1. 各 \(i=1,\ldots,N\) に対して組 \((t_i,w_i)\) を計算する。
2. 組 \((t_i,w_i)\) の列をソートしたものを改めて \((t_1,w_1),(t_2,w_2),\ldots,(t_N,w_N)\) とする。
3. \(\displaystyle 2\sum _ {i=1}^m w_i \geq L\) を満たす最小の \(m\) を計算し、\(x=t_m\) とする。
4. \(C(x) = \displaystyle \sum _ {i = 1} ^ N w_i |x - t_i|\) を答えとして出力する。

2 のソートする部分がボトルネックとなるので、計算量は \(O(N \log N)\) です。

実装

実装例 (C++ (GCC 9.2.1), 38ms)