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;
	}

};