貪欲法 ハフマン符号 462 c appleman and toastman codeforces

CodeForces 462 C - Appleman and Toastman

CodeForces 462 C - Appleman and Toastman
Feb. 2, 2020, 1:52 p.m.

目次

問題

http://codeforces.com/contest/462/problem/C

数のグループが与えられて、以下の操作を終了まで繰り返して獲得できる最大のスコアを答える問題です.

  1. スコアを0から始めます
  2. 数のグループの要素の合計をスコアに加えます
  3. グループから任意の個数、任意の要素を取り出し2グループに分割し、両方のグループの合計値をスコアに加えます
  4. グループの要素数が1つのみの場合はその要素の値をスコアに加えてグループを破棄します
  5. すべてのグループが破棄されたら終了です

グループ$G$の要素数$N$は$1 \leq N \leq 10^5$で、要素$a_i$は$1 \leq a_i \leq 10^6$です.

入力

N
a_1 a_2 ... a_N
  • N - グループの要素数
  • a_i - $i$番目の要素の値

出力

最大値の整数を出力してください.

入出力例

3
3 1 5
26

まず$3 + 1 + 5 = 9$をスコアに加算します.
次に$3, 5$と$1$をグループに分けて$3 + 5 = 8$と$1$を加算します.
$9 + 8 + 1 = 18$です.
$1$は要素が1つだけになったので破棄します.
$3, 5$はさらに$3$と$5$に分割してそれぞれ加算します.
$18 + 3 + 5 + 26$.
$3$と$5$はそれぞれ要素が1つになったので破棄します.
すべてのグループが破棄されたので終了です.

解説

ハフマン符号のアルゴリズムを知っていれば簡単に解ける問題です.
ハフマン符号は圧縮用のアルゴリズムなので、スコアを最小化することが目的です.

上の例の場合は、数をある文字の出現頻度とみなすろと以下のような二分木になります.

      9
     / \
    4   5
   / \
  1   3

例えば、Aが5回、Bが3回、Cが1回出現する文章だとすると、AAAAABBBC

0000010101011

と符号化出来ます.

葉が左から小さい順に並んでいることに着目してください.

今回は反対にスコアを最大化するように応用すれば良いです.
葉を左から大きい順に並べます.

      9
     / \
    8   1
   / \
  5   3

葉とノードの数をすべて合計すると最大のスコアになります.
26になります.

実装してみましょう.
左から一直線に加算していくので、複雑な木構造は不要で配列を先頭から走査するだけでOKです.
計算量的には$O(N)$です.

まず数を大きい順にソートします.
後は先頭から畳み込んで加算していきます.

まずは葉の$5$から始めて、次の葉$3$とノード(自分+次の葉)の$5 + 3$を加えます.

$5 + 3 + (5 + 3) = 16$.

次に葉の$1$とノードの$8 + 1$を加えます.

$16 + 1 + (8 + 1) = 26$

計算量

$$O(N)$$

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
Int N;
vector<Int> A;

void input() {
  cin >> N;
  Int a_;
  while (cin >> a_) A.push_back(a_);
}

void solve() {
  sort(span_all(A));
  reverse(span_all(A));
  Int acc = A[0];
  Int sum_ = acc;
  loop(a_i,1,A.size()) {
    acc += A[a_i];
    sum_ += acc + A[a_i];
  }
  cout << sum_ << endl;
}

int main() {
  input();
  solve();
  return 0;
}