D - 図書館の本の返却 / Returning Library Books Editorial
by 
MMNMM
まず、\(1\) 冊以上の本を持ってカウンターを出発したとし、持っているすべての本を戻してカウンターに戻ってくるために必要な移動距離について考えます。
考察
この一連の移動の中で到達すべきもっとも大きい座標を \(x _ {\max}\) 、もっとも小さい座標を \(x _ {\min}\) とします。
移動のうち \(x _ {\max}\) に到達している瞬間をひとつ取り、直前に座標 \(0\) にいた時点から直後に座標 \(0\) にいる時点までの右半開区間を考えます。 同様に、\(x _ {\min}\) に到達している瞬間をひとつ取り、直前に座標 \(0\) にいた時点から直後に座標 \(0\) にいる時点までの右半開区間を考えます。 高橋君は前者の区間ではのべ \(2x _ {\max}\) の移動を、後者の区間ではのべ \(-2x _ {\min}\) の移動を行っています。
\(x _ {\min}\) から \(x _ {\max}\) へ、もしくは \(x _ {\max}\) から \(x _ {\min}\) へ移動するためには座標 \(0\) を通る必要があるため、これらの区間に重なりはありません。 よって、高橋君は少なくとも \(2x _ {\max}-2x _ {\min}\) 以上の距離を移動する必要があります。
逆に、次のように移動することで \(2x _ {\max}-2x _ {\min}\) の移動ですべての本を戻すことができます。ここで、移動の途中で持っている本に対応する書棚の座標へ訪れた場合、ただちにその本を戻していることとします。
- カウンターから \(x _ {\max}\) へ移動する。
- \(x _ {\max}\) から \(x _ {\min}\) へ移動する。
- \(x _ {\min}\) から \(x _ {\max}\) へ移動する。
よって、持つ本を決めたとき、移動距離の最小値は \(2x _ {\max}-2x _ {\min}\) となることがわかりました。
合計移動距離を最小にする運び方をひとつ取ります。 上の考察から、カウンターから出発した時点で持っている本を決めたとき、移動距離の最小値は動くべき範囲の長さの \(2\) 倍です。 このことから、それぞれの出発時点で持っている本を、対応する本棚が正の方向にあるかそうでないかでさらに（高々）\(2\) つずつの集合に分け、各集合ごとに別々に運ぶとしても移動距離が増加しないことがわかります。 よって、対応する本棚がすべて正の方向にあるとした問題を解くことができれば、\(2\) つの方向について解いた答えを合計することでこの問題を解くことができます。
以下、どの本に対しても対応する本棚は正の方向にあるとします。 適切に本の番号を付け替えることで、\(0\lt X _ 1\le X _ 2\le\cdots\le X _ N\) としておきます。
カウンターを出発した時点で持っている本の番号の集合を \(S\) とします。 これらを戻してカウンターに戻ってくるまでの移動距離の最小値は \(\displaystyle2\max _ {i\in S}X _ i\) となります。
答えが \(2(X _ N+X _ {N-K}+X _ {N-2K}+\cdots+X _ {(N-1)\%K+1})\) となることを示します。
証明
\(i\) 番目に運んだ本の集合を \(S _ i\) とし、適切に運ぶ順番を並び替えることで \(\displaystyle\max _ {k\in S _ i}X _ k\le\max _ {k\in S _ {i+1}}X _ k\) が成り立つとします。
すると、\[\begin{aligned}\max _ {k\in S _ i}X _ k&=\max _ {1\le j\le i}\max _ {k\in S _ j}X _ k\\&=\max _ {k\in S _ 1\cup S _ 2\cup\cdots\cup S _ i}X _ k\end{aligned}\] となります。 最右辺は \((X _ 1,X _ 2,\ldots,X _ N)\) から \(\displaystyle\sum _ {j=1} ^ i|S _ j|\) 個選んだうちの最大値なので、\(X _ {\sum _ {j=1} ^ i|S _ j|}\) 以上です。 よって、 \(X _ {\sum _ {j=1} ^ i|S _ j|}\le\displaystyle\max _ {k\in S _ i}X _ k\) がわかります。
ここから、答えは \(2\sum X _ {\sum _ {j=1} ^ i|S _ j|}\) 以上です。
また、各 \(S _ i\) を \((1,2,\ldots,N)\) の部分文字列として取ることでこの下界を達成することができます。 よって、各 \(S _ i\) が \((1,2,\ldots,N)\) の部分文字列であるような最適解があることがわかります。
\(S _ i\) に対して \(\displaystyle\max _ {k\in S _ i}X _ k=X _ {f(i)}\) なる関数 \(f\) を定めます。 上の考察から、\(\displaystyle f(i)=\sum _ {j=1} ^ i|S _ j|\) なる最適解が存在します。 \(|S _ j|\le K\) なので、\(f(1)\le K\) 、\(f(i+1)\le f(i)+K\) です。 また、運ぶ回数を \(M\) とすると \(f(M)=N\) です。
この \(2\) つを合わせて \(f(i)\ge N-(M-i)K\) が成り立ちます。 \(f(1)\le K\) なので \(\dfrac NK\le M\) です。 \(X _ i\) を昇順に並べていたので、\(X _ {f(i)}\ge X _ {N-(M-i)K}\) です。
この不等式を \(i=1,2,\ldots,\lceil N/K\rceil\) にわたって足すことで、この問題の答えが \(\displaystyle2\sum _ {i=1} ^ {\lceil N/K\rceil}X _ {N-(\lceil N/K\rceil-i)K}\) 以上であることがわかります。
これは \(X _ i\) を大きいほうから \(K\) 個ずつ取ることで達成できるため、求める答えは \(\displaystyle2\sum _ {i=1} ^ {\lceil N/K\rceil}X _ {N-(\lceil N/K\rceil-i)K}\) です。
あとは、これを計算することで答えを求めることができます。
ソートがボトルネックとなり、計算量は \(O(N\log N)\) となります。
実装例は以下のようになります。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int N, K;
cin >> N >> K;
// 正のものと負のものに分ける
vector<int> positive_X, negative_X;
for (int i = 0; i < N; ++i) {
int X;
cin >> X;
if (X > 0) {
positive_X.emplace_back(X);
} else {
negative_X.emplace_back(-X); // 負のほうは -1 倍しておく
}
}
// 降順に並べて
ranges::sort(positive_X, greater{});
ranges::sort(negative_X, greater{});
long ans = 0;
// K 個ごとに足す
for (int i = 0; i < size(positive_X); i += K) {
ans += positive_X[i];
}
for (int i = 0; i < size(negative_X); i += K) {
ans += negative_X[i];
}
// 2 倍が答え
cout << 2 * ans << endl;
return 0;
}
N, K = map(int, input().split())
# 正のものと負のものに分ける
positive_X = []
negative_X = []
for x in map(int, input().split()):
if x > 0:
positive_X.append(x)
else:
negative_X.append(-x) # 負のほうは -1 倍しておく
# 降順に並べて
sort(positive_X, reverse=True)
sort(negative_X, reverse=True)
# K 個ごとに足したものの 2 倍が答え
print(2 * (sum(positive_X[::K]) + sum(negative_X[::K]))
posted:
last update: