kmjp's blog

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

TopCoder SRM 625 Div2 Medium IncrementingSequence

これは割と簡単。
http://community.topcoder.com/stat?c=problem_statement&pm=12107

問題

N要素の数列A[i]と数値kが与えられる。
A[i]の任意の要素にkを加える、という処理を任意回繰り返し、A[i]中に1~Nが1回ずつ登場するようにできるか答えよ。

解法

A[i]に数値を足すことはできても、減らすことはできない。
よって、1~Nを順に作っていく際、A[i]のうち小さい順に未使用かと差がkの倍数となるものを割り当てていけばよい。

class IncrementingSequence {
	public:
	string canItBeDone(int k, vector <int> A) {
		int num[51];
		int i,L=A.size(),x;
		ZERO(num);
		FOR(i,L) num[A[i]]++;
		for(i=1;i<=L;i++) {
			for(x=1;x<=i;x++) {
				if(num[x] && (i-x)%k==0) {
					num[x]--;
					break;
				}
			}
			if(x>i) return "IMPOSSIBLE";
		}
		return "POSSIBLE";
	}
}

まとめ

Div2 Mediumにしてはすんなり。