kmjp's blog

競技プログラミング参加記です

TopCoder SRM 690 Div1 Easy WolfCardGame

また詰めが甘くて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の時の処理を雑にやりすぎた…。

広告を非表示にする