CodeForces 462 C - Appleman and Toastman

Calendar Clock iconCalendar Clock icon

Code Forces

目次

# 問題

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

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

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

グループGGの要素数NN1N1051 \leq N \leq 10^5で、要素aia_i1ai1061 \leq a_i \leq 10^6です.

# 入力

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

# 出力

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

# 入出力例

3
3 1 5
26

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

# 解説

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

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

      9
     / \
    4   5
   / \
  1   3

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

0000010101011

と符号化出来ます.

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

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

      9
     / \
    8   1
   / \
  5   3

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

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

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

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

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

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

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

# 計算量

O(N)O(N)

# 解答

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;
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;
}

リモートフリーランス。ウェブサービス、スマホアプリエンジニア。
東アジアを拠点に世界を移動しながら活動してます!

お仕事のご依頼・お問い合わせはこちら

コメント