TCO2012 Round2B Easy(300)
読めない点数を狙う場合、矢が均等に当たるようにするのが最善。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; }};