C - 荷物の配送トラック / Cargo Delivery Truck Editorial
by 
MMNMM
「積載量の制限のない \(M\) 台のトラックに荷物を積み分けて、どのトラックの積載量も \(K\) 以下にできる」ことは、「積載量の上限が \(K\) であるトラックを好きな台数使って荷物を積み分けて、トラックの台数を \(M\) 台以下にできる」ことと同値です。
証明
前者ができるとき、明らかに後者も可能です。
後者が \(M\) 台ちょうどで積み分けられているとき、明らかに前者も可能です。
後者が \(M\) 台より少ない台数で積み分けられているときについて考えます。 このとき、末尾から必要な台数だけ、荷物を \(1\) つ載せているトラックを作ることでちょうど \(M\) 台にすることができます。 新しく作られた荷物を \(1\) つだけ載せているトラックと、（存在すれば）余った荷物からなるトラックは、それぞれ対応する元のトラックより少ない積載量をもちます。 よって、これが \(M\) 台のトラックへの荷物の積み分けでどのトラックの積載量も \(K\) 以下であることが示されました。
よって、後者の積み分けが可能であるか判定すればよいです。
これは、次のアルゴリズムで使用するトラックが \(M\) 台以下であるかで判定できます。
- はじめ、空のトラックを \(1\) つ用意する。
- 荷物を順に見て、次の操作を行う。
- 最新のトラックに荷物を積むことができるなら（積んでも積載量が \(K\) を超えないなら）、積む。
- そうでなければ、新しいトラックを用意し、用意したトラックに荷物を積む。
証明
このアルゴリズムが \(M\) 台以下のトラックを使用して終了したとき、明らかに\(M\) 台以下での積み分けが可能です。
よって、\(M\) 台以下で積み分けられるとき、このアルゴリズムが \(M\) 台以下のトラックを使用して終了することを示せばよいです。
\(n\) 台 \((n\le M)\) での積み分け方をひとつとり、荷物の列を分割した位置を \(0=L _ 0\lt L _ 1\lt L _ 2\lt\cdots\lt L _ n=N\) とします。 次に、このアルゴリズムが出力する積み分け方について、荷物の列を分割した位置を \(0=H _ 0\lt H _ 1\lt H _ 2\lt\cdots\lt H _ m=N\) とします。
\(i\ (1\le i\le\min\lbrace n,m\rbrace)\) について、\(L _ i\le H _ i\) が成り立つことを示します。
\(1\le i\le m\) に対して、アルゴリズムの条件より、\(H _ {i-1}+1\) 番目から \(H _ i\) 番目までの荷物の重さの合計は \(K\) 以下で、\(H _ {i-1}+1\) 番目から \(H _ i+1\) 番目までの荷物の重さの合計は \(K\) より大きいです（ここで、便宜上 \(N+1\) 番目に十分大きな荷物を置くこととします）。
\(i\ (1\le i\le\min\lbrace n,m\rbrace)\) について、\(L _ {i-1}\le H _ {i-1}\) を仮定して \(L _ i\le H _ i\) を示します。
\(L\) は積載量の上限が \(K\) であるトラックを使った積み分けなので、\(L _ {i-1}+1\) 番目から \(L _ i\) 番目までの荷物の重さの合計は \(K\) 以下です。 \(H _ {i-1}+1\) 番目から \(H _ i+1\) 番目までの荷物の重さの合計は \(K\) より大きく、\(L _ {i-1}\le H _ {i-1}\) なので、\(L _ {i-1}+1\) 番目から \(H _ i+1\) 番目までの荷物の重さの合計も \(K\) より大きいです。 よって、\(L _ i\lt H _ i+1\) が成り立ちます。 \(L _ i,H _ i\) は整数なので、\(L _ i\le H _ i\) が示されました。
\(L _ 0=H _ 0=0\) なので、\(i=1\) に対して仮定が成り立ち、この結果を順に適用することですべての \(1\le i\le\min\lbrace n,m\rbrace\) について \(L _ i\le H _ i\) がわかります。
この結果から、\(n\lt m\) なら \(L _ n\le H _ n\lt H _ m\) とならなければなりませんが、\(L _ n=H _ m=N\) より \(N\lt N\) となり矛盾です。 よって、\(m\le n\) が示され、\(m\le M\) が成り立つことが示されました。
このアルゴリズムは \(O(N)\) 時間で動作するので、この問題を \(O(N)\) 時間で解くことができました。
余談ですが、積載量の最大値の最小値 \(S\) の具体的な値を求める問題を、二分探索によって今回の問題を \(\displaystyle \left\lceil\log _ 2\sum A _ i\right\rceil\) 回解くことに帰着することができます。
実装例は以下のようになります。
#include <iostream>
int main() {
using namespace std;
int N, M;
long K;
cin >> N >> M >> K;
int truck_count = 0; // いくつトラックが埋まったか
long now_load = 0; // 今見ているトラックにどれだけ積まれているか
for (int i = 0; i < N; ++i) {
int A;
cin >> A;
while (now_load + A > K) { // 今見ているトラックに積めなければ
++truck_count; // 埋まったトラックを増やして
now_load = 0; // 新しいトラックを用意する
if (truck_count >= M) { // M 台を超えたら
cout << "Yes" << endl; // Yes
return 0;
}
}
now_load += A; // 今見ているトラックに荷物を積む
}
// M 台を超えなかったら
cout << "No" << endl; // No
return 0;
}
N, M, K = map(int, input().split())
truck_count = 0 # いくつトラックが埋まったか
now_load = 0 # 今見ているトラックにどれだけ積まれているか
for A in map(int, input().split()):
while now_load + A > K: # 今見ているトラックに積めなければ
truck_count += 1 # 埋まったトラックを増やして
now_load = 0 # 新しいトラックを用意する
if truck_count >= M: # M 台を超えたら
print('Yes') # Yes
exit()
now_load += A # 今見ているトラックに荷物を積む
# M 台を超えなかったら
print('No') # No
posted:
last update: