TCO2012 Round2B Easy(300)

BlurredDartboard

読めない点数を狙う場合、矢が均等に当たるようにするのが最善。Pを読めない点数で割った余りについて、読めない点数に矢を何本当てるかを変えて最小回数を求める。

#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

class BlurredDartboard{public:
int minThrows( vector <int> points, int P )
{
    int n = (int)points.size();

    //  読めない数字
    vector<int> H;
    for ( int i=1; i<=n; i++ )
        if ( find(points.begin(),points.end(),i)==points.end() )
            H.push_back(i);
    int hn = (int)H.size();
    int sum = accumulate(H.begin(),H.end(),0);
    //  読める数字の最高点
    int mp = *max_element(points.begin(),points.end());

    //  読めない数字に1本ずつ当てたときの点数が、
    //  読める数字で最高の点数に全て当てたときより小さいか、
    //  読めない数字が無ければ、全て読める数字の最高点に当てる
    if ( hn==0 || sum<mp*hn )
    {
        return (P+mp-1)/mp;
    }

    //  読めない数字それぞれに同数の矢を当てる
    int c = P/sum*hn;
    P %= sum;

    //  読める数字が無いなら、読めない数字に1本ずつ当てていく
    if ( hn==n )
    {
        int s=0;
        int i;
        for ( i=0; i<hn && s<P; i++ )
            s += (int)H[i];
        return c+i;
    }

    //  読めない数字に当てる矢の数を変えて、最適解を探す
    int t = 9999;
    for ( int i=0; i<=hn; i++ )
    {
        int s = accumulate(H.begin(),H.begin()+i,0);
        t = min( t, i+(max(P-s,0)+mp-1)/mp );
    }

    return c+t;
}};