TCO2012 Round2B 300 BlurredDartboard

問題概要

ダーツの天才がダーツをする。彼の命中率は百発百中、狙った的には必ずあてる。しかし的が汚れていて何点か分からない的がいくつかある。ダーツの的はN個の領域に分かれていてそれぞれ1,2,3, ..., N点のどれかである。最適な戦略で点数を取っていたとき必ずP点を超えるのに必要な最小の手数はいくつか？

方針

単純に考えると、以下の3通りを考えればよさそう。

1. 点数が見えている的のうち一番高いところだけを射抜いていく
2. 点数が見えていないところを使う
3. 点数が見えている的のうち一番高いところ+見えていないところを使う

見えないところを狙う時、例えば見えていない的が10個あったとする。その中で1つの的に絞って打ちまくったとする。もし、そこが見えていない的のうち点数が最小だった場合多くの手数が必要となるので、異なる場所を狙った方がいいことになる。あくまでも最悪の場合でも確実にP点超える最小の手数を考えているので、最悪の場合どうなるかという思考でいく。

3.について考えてみる。3は、点数最高の場所を狙う的集合に加えると、見えていない場所の点数の平均値があがる場合に有効な戦略だが、そもそもそんな場合は、1.の戦略をとったほうがお得なので、3.は考える必要がないことが分かる。

ソースコード

本番書いたソースは酷過ぎた。考えを整理して書き直してみた。

#define REP(i, n) for(int i=0; i<(int)(n); i++)
#define FOR(i, s, e) for (int i = (int)(s); i < (int)(e); i++)

class BlurredDartboard {
public:
    int minThrows(vector<int> points, int P) {
        int ret = 1<<30;
        int N = points.size();

        // use the highest point visible
        int maxv = *max_element(points.begin(), points.end());
        if (maxv)
            ret = (P+maxv-1)/maxv;

        // use invisible points
        bool visible[64] = {0};
        REP(i, N)
            if (points[i])
                visible[points[i]] = 1;

        vector<int> unvisible;
        FOR (i, 1, N+1)
            if (!visible[i])
                unvisible.push_back(i);

        int sum = accumulate(unvisible.begin(), unvisible.end(), 0);
        int m = unvisible.size();

        if (sum) {
            int x = P/sum*m;
            P %= sum;

            // use the highest point for the points remained
            if (maxv)
                ret = min(ret, x+(P+maxv-1)/maxv);

            // use invisible points for the points remained
            int cnt = 0;
            while (P > 0)
                P -= unvisible[cnt++];
            ret = min(ret, x + cnt);
        }

        return ret;
    }
};