これは割と簡単。
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にしてはすんなり。