TCO R2B 300pt : BlurredDartboard
問題概要
1~Nを並び替えた順列pがある。pのうちいくつかは分かっているがほかは分からない。pの中から何かを選んで加点する。加点してP点を確実に越えるようにしたい。最小なんかい選ぶ必要があるか求める問題。
解法
分からないものの平均値と分かっているものの最大値=Mを比べて、Mが平均値以上だったらMを何度も選べば良い。そうでないとき、余りがでるまでは分からないものを均等に叩く。最後に余ったものに対しては、分からない数を叩くかMを選ぶのを繰り返せば良い。
以下のコードではMを何回叩くかを全探索している。これは下手にO(N)でとくのより安全で良かったかなと思う。
acceptされたコード
#include <vector> #include <algorithm> #include <numeric> using namespace std; struct BlurredDartboard { int minThrows(vector <int> points, int P) { const int N = points.size(); int maxi = *max_element(points.begin(), points.end()); vector<int> nons; for(int i=1; i<=N; ++i){ if(find(points.begin(), points.end(), i) == points.end()){ nons.push_back(i); } } const int Z = nons.size(); const int total = accumulate(nons.begin(), nons.end(), 0); //分かってるのを打った方がよいとき if(maxi * Z >= total){ return (P + maxi - 1) / maxi; } //分からないのを打った方がよいとき int ans = Z * ((P + total - 1) / total); for(int i=0; i<100000; ++i){ int A = P - maxi*i; int add = 0; if(A > 0){ add += Z * (A / total); A %= total; for(int j=0; j<Z && A > 0; ++j){ A -= nons[j]; ++add; } } ans = min(ans, i + add); } return ans; } };