F - Bread Editorial by mechanicalpenciI
まず、問題を少し限定して \(L=A_1+A_2+\ldots +A_N\) の時にかかる最小コストを求めることを考えます。
これは順序を逆にすることで、長さ \(A_1\), \(\ldots\), \(A_N\) のパンから始めて、長さ \(x\) のパンと長さ \(y\) のパンをコスト \(x+y\) を払って繋げる問題として見ることができます。
このとき、 多重集合 \(S=\{ A_1,A_2,\ldots,A_N \}\) から始めて次の操作を \(N-1\) 回繰り返した時にかかるコストの総和が元の問題のコストの最小値となります。
- \(S\) の要素のうち、小さい方から \(2\) つ取り出し \(s_1,s_2\) とする。コスト \(s_1+s_2\) を払って長さ \(s_1\)のパンと長さ \(s_2\) のパンを繋げる。その後、\(S\) から \(s_1, s_2\) を取り除き、\(s_1+s_2\) を\(S\) に追加する。
\(S\) の要素数は \(1\) 回でちょうど \(1\) つずつ減少するため、このような操作ができることは明らかです。このようにした時、最小となる証明を以下に載せます。
上の手法を取ったとき最小となる事の証明
以下の証明はハフマン符号がコンパクト符号である事の証明とほぼ同一です。
準備
繋げる過程 (最初と最後含む) で出てくるパンを頂点とし、最初のパンを葉、最後に一つながりになったパンを根とし、根以外のパンについてそのパンを繋げた先のパンを親として持つような根付き木を考えます。このとき、この根付き木の葉以外の頂点はかならずちょうど $2$ つの子を持っています。
また、各頂点の重みをその頂点に対応するパンの長さで定めると、繋げる過程全体でかかったコストは葉以外の頂点の重みの総和として表されます。このとき、葉以外の頂点について、その重みは子の重みの和となっていることに注意します。さらに、それぞれの葉の重みがその祖先において何回加算されたかを考えることで、これはそれぞれの葉について（重み）$\times$（根付き木における深さ）を足し合わせたものとしても数えられることが分かります。
よって、コストを最小にするような繋げ方に対応する木においては、重みが小さい方から $2$ つの葉を取ってきたとき、それら木の中で深さが最大の $2$ 頂点であるとしてよいです。（ここで、葉でない頂点が必ず $2$ つの子を持つことから最大の深さの頂点は $2$ つ以上存在することに注意）なぜなら、そうでない時、葉の重みを入れ替えることを考える事で全体のコストをより小さくできるからです。さらに、これらは同じ親を持つとしてよいです。なぜなら、同じ深さの葉同士を入れ替えても全体でコストは変わらないからです。
証明
$N$ についての帰納法によって示す。
i ) $N=2$ のとき
この時は繋げる操作が $1$ 通りがないため、明らかである。
ii ) $N=N_0$ で成り立っているとして, $N=N_0+1$ のとき
$A_1,A_2, \ldots, A_{N_0+1}$ を繋げる時のコストの最小値を $C'$ とします。また、ここで、$A_1, A_2$ が $A_1,A_2, \ldots, A_{N_0+1}$ の中で小さい方から $2$ つとして一般性を失いません。 $A_1+A_2, A_3,A_4,\ldots, A_{N_0+1}$ を繋げる時のコストの最小値を$C$ とすると、帰納法の仮定から上の手法で繋げた時のコストの総和は$C+A_1+A_2$ となります。 よって、$C'\leq C+A_1+A_2$ です。 一方で、$A_1,A_2, \ldots, A_{N_0+1}$ を繋げる時のコストを最小にする繋げ方に対応する木を考えると、上の準備で述べたように、重さ $A_1$, $A_2$ の葉を子として持つ頂点が存在します。このときこの $2$ つの葉を取り除くことで $A_1+A_2, A_3,A_4,\ldots, A_{N_0+1}$ を繋げる方法に対応する木となります。この木に対応するコストは $C'-A_1-A_2$ ですので、$C\leq C'-A_1-A_2$より、$C'\geq C+A_1+A_2$ です。 ゆえに、$C'=C+A_1+A_2$ であり、上の手法はそれを達成しています。よって、示されました。
\(L=A_1+A_2+\cdots+A_N\) のときの最小値についてはこれで示されました。
\(L>A_1+A_2+\cdots+A_N\)のときについては、\(B_1+B_2+\cdots+B_M=L-(A_1+A_2+\cdots+A_N)\), \(B_i>0\) となるような整数の組\((B_1,B_2,\ldots, B_M)\)にわたって、長さ \(A_1, A_2,\ldots,A_N, B_1,B_2,\ldots, B_M\) のパンを繋げる時の最小値を求める必要があります。
結論としては \(M=1\), \(B_1=L-(A_1+A_2+\cdots+A_N)\) のときにコストは最小となります。
これを示すためには、\(A_1,A_2,\ldots, A_N\)を繋げるために必要な最小コストが \(A_1+A_2,A_3,A_4, \ldots, A_N\)を繋げるために必要な最小コスト以上になる事を示せば十分です。 前者に対応する木を考え、 という操作を行うと、この木に対応するコストは元の木に対するコスト以下となります。一方で、これは\(A_1+A_2,A_3,A_4, \ldots, A_N\)を繋げるために必要な最小コスト以上であるため、
示したいことが示されました。証明
さて、このアルゴリズムは優先度付きキューなどを用いることで \(O(N\log N)\) で実装できます。よって、十分高速にこの問題を解くことができました。
c++による実装例 :
#include <bits/stdc++.h>
using namespace std;
int main(void) {
int n;
priority_queue<long long, vector<long long>, greater<long long> >pq;
long long x, y, l;
long long ans = 0;
cin >> n >> l;
for (int i = 0; i < n; i++) {
cin >> x;
l -= x;
pq.push(x);
}
if (l > 0) {
pq.push(l);
n++;
}
for (int i = 0; i < (n - 1); i++) {
x = pq.top();
pq.pop();
y = pq.top();
pq.pop();
ans += x + y;
pq.push(x + y);
}
cout << ans << endl;
return 0;
}
posted:
last update: