2012 TCO Algorithm Round 2B easy: BlurredDartboard
解法
見えない部分の得点が小さい順に 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; } };