また詰めが甘くてEasy落とした。辛うじて1Chalで踏ん張った。
https://community.topcoder.com/stat?c=problem_statement&pm=14248
問題
1~100の数字のうちK個を選ぶ。
K個の部分集合を足し引きしてもNが作れないようなK個の選び方を1つ示せ。
解法
Nがpの倍数でないなら、pの倍数だけからなるK個の整数を選べば確実にNが作れない。
kの上限は15なので、Nが2~6で割り切れるか判定し、割り切れなければそのようなpの倍数をK個答えよう。
Nが2~6のいずれでも割り切れるケースというのはN=60しかない。
この場合7の倍数を列挙していけばよいが、1~100の間には7の倍数は14個しかない。
60を7で割った余りは4なので、K=15の場合は7の倍数以外に1を入れておけば良い。
class WolfCardGame { public: vector <int> createAnswer(int N, int K) { int i,j; for(j=2;j<=6;j++) if(N%j!=0) { vector<int> V; FOR(i,K) V.push_back(j*(i+1)); return V; } vector<int> V; V.push_back(1); FOR(i,K-1) V.push_back(7*(i+1)); return V; } }
まとめ
N=60の時の処理を雑にやりすぎた…。