POJ 3370 Halloween treats
問題
n個の整数が与えられる。
この中から適当な(空でない)部分集合を選び、その要素の和がcの倍数にすることはできるか。
できるならそのような集合(どれでもよい)の要素を全て出力し、
不可能なら"no sweets"と出力せよ。
制約条件
1≦c≦n≦100000
方針
愚直にDPすると、O(cn)かかって明らかにTLE.
c≦nという制約に注目する。
sum[i]=(Σ[k≦i]a[k]) mod cとする。
すると、sumは0〜c-1までのc通りの値しか取らないから、必ず
i≠jでsum[i]=sum[j]となるi,jが存在する。
そのようなi,jを見つけたら、
a[i+1], a[i+2], ..., a[j]が答えである。
これでO(n)で出来る。
のだがやたら制限時間が厳しく、O(n)なのに制限時間ギリギリになる。
ソースコード
int c,n,a[100001]; int index[100001]; int main() { while(scanf("%d%d",&c,&n),c){ rep(i,n)scanf("%d",a+i), index[i]=-1; int sum=0; rep(i,n){ (sum+=a[i])%=c; if(sum==0){ rep(j,i+1) printf("%d%c",j+1,j==i?'\n':' '); break; } if(index[sum]>=0){ for(int j=index[sum]+1;j<=i;j++) printf("%d%c",j+1,j==i?'\n':' '); break; } index[sum]=i; } } return 0; }