問題
https://community.topcoder.com/stat?c=problem_statement&pm=13946&rd=16549
解き方
すべての場合の数を考えるとはまってしまう。
逆に制約条件を考えると、Sが与えられた時、最大まで分割した時は１がS個並ぶ、
つまり最大でS-1回分割することができる。
次に、N回分割するとき、その数の最大は均等に分割すると得られる。
よって、分割数を２〜S-1まで試していき、最大がMを超えたものが答えになる。
コード
class SubdividedSlimes {
public: int needCut(int S, int M) {
for(int i=2;i<=S;i++){
vector<long long> num;
FORE(j,0,i)num.push_back(S/i);
FORE(j,0,S%i)num[j]++;
long long total=0;
FORE(j,0,i)total+=num[j];
long long sum=0;
FORE(j,0,i)sum+=num[j]*(total-num[j]);
if(sum/2>=M)return i-1;
}
return -1;
}
};
public: int needCut(int S, int M) {
for(int i=2;i<=S;i++){
vector<long long> num;
FORE(j,0,i)num.push_back(S/i);
FORE(j,0,S%i)num[j]++;
long long total=0;
FORE(j,0,i)total+=num[j];
long long sum=0;
FORE(j,0,i)sum+=num[j]*(total-num[j]);
if(sum/2>=M)return i-1;
}
return -1;
}
};