Google Code Jam 2018 Round1B: Rounding Error

問題概要

原文 → Google Code Jam

長さ の数列 (この数列の 番目の要素を とする) と、整数 が与えられる。 は より大きく、数列の要素の総和は 未満である。

新たな数列 を作ることを考える (この数列の長さを とし、 番目の要素を とする)。 は長さが 以上であって、 を満たし、 でなければならない。

数列 について、その数列のスコアを と定義する。あり得る数列を全て考慮したときの、スコアの最大値を求めよ。

解説

総和を大きくしたいので、できるだけ切り上げがたくさん起こるようにしたいです。

すでに切り上げが発生する要素に対して票を追加するのは無駄ですので、切り上げが発生していない要素に対して効果的に票を追加していきましょう。少ない追加票数で切り上げが起こる要素を優先したいので、 (現在の票数) が を超えないものの中で最大値をとるような要素に対して票を貪欲に追加することが最善であり、この操作は状態を priority_queue で管理することで可能です。

新たな要素に票をいれることが最善である場合もあることに注意する必要があります (この部分の条件文間違えて 6WA しました・・・)

ソースコード

実装は割と楽です。誤差絶対回避するマンなので round 関数を自前で作るなどしました。

#include <cstdio>
#include <queue>
#include <vector>
#include <cmath>
using namespace std;

int N, L;
struct Elem {
    int value;
    bool operator<(const Elem &e) const {
        int moa = value * 100 % N;
        int mob = e.value * 100 % N;

        if(2 * moa >= N) moa -= N;
        if(2 * mob >= N) mob -= N;
        return moa < mob;
    }
};

int round_user(int A, int B) {
    int div = A / B, mod = A % B;
    if(mod * 2 >= B) div++;
    return div;
}

int main() {
    int T; scanf("%d", &T);
    for(int z=1; z<=T; z++) {
        scanf("%d%d", &N, &L);

        priority_queue<Elem> que;
        int ans = 0, rest = N;
        for(int i=0; i<L; i++) {
            int A; scanf("%d", &A);
            rest -= A;
            que.push(Elem{A});
        }

        while(rest--) {
            Elem cur = que.top(); que.pop();
            // 新たな要素に票をいれたほうが得
            if(cur < Elem{0}) {
                que.push(cur);
                que.push(Elem{1});
            }
            else {
                que.push(Elem{cur.value + 1});
            }
        }

        while(que.size()) {
            int v = que.top().value; que.pop();
            ans += round_user(v * 100, N);
        }
        printf("Case #%d: %d\n", z, ans);
    }
    return 0;
}