2012 TCO Algorithm Round 2B easy: BlurredDartboard

問題

TopCoder Statistics - Problem Statement

解法

見えない部分の得点が小さい順に a1, a2, ..., aK であるとすると, 見えない部分については, 順番に a1, a2, ..., aK というように投げていくのが最適です(例えば 1 箇所に集中狙いのような投げ方では, 最悪の場合 a1, a1, ... というように a1 しか出なくなる。)。

見える部分については, 明らかに得点が一番大きい物に対してのみ投げるのが最適です。この得点を maxi としましょう。すると,

• maxi*K >= a1+a2+...+aK のとき
  • maxi に向かってだけ投げるのが明らかに最適です。この時は, P/maxi + (P%maxi>0) が答えですね。
• maxi*K < a1+a2+...+aK のとき
  • 目標点数が a1+a2+...+aK 以上残っているときは, maxi を使わず a1+a2+...+aK を使うほうが損をしません。その後はわからないので, a1+...+ai の i をどこまで使うかを全探索します。

これ結構難しいと思うんですが statistics を見るに正答率 7 割弱あってみなさんお強いんですねって感じです…

class BlurredDartboard {
public:
    int minThrows(vector <int> points, int P) {
        int n = points.size();
        vector<bool> canSee(n+1);
        for (int i = 0; i < n; i++) canSee[points[i]] = true;
        vector<int> a;
        int maxi = 0;
        for (int i = 1; i <= n; i++) {
            if (!canSee[i]) a.push_back(i);
            else maxi = max(maxi, i);
        }
        int K = a.size(), sum = 0;
        for (int el : a) sum += el;
        if (maxi == 0) {
            int ans = (P/sum)*K;
            P %= sum;
            if (P > 0) {
                for (int i = 0; i < K; i++) {
                    ans++;
                    P -= a[i];
                    if (P <= 0) break;
                }
            }
            assert(P <= 0);
            return ans;
        }
        if (K==0 || K*maxi >= sum) return P/maxi + (P%maxi>0);
        int ans = (P/sum)*K;
        P %= sum;
        int tmp = 0, rest = P;
        if (rest > 0) {
            tmp = (P/maxi)+(P%maxi>0);
            for (int i = 0; i < K; i++) {
                rest -= a[i];
                if (rest <= 0) {
                    tmp = min(tmp, i+1);
                    break;
                }
                tmp = min(tmp, rest/maxi+(rest%maxi>0) + i+1);
            }
        }
        ans += tmp;
        return ans;
    }
};