lay_contest round 00002 : C - 近所迷惑高橋くん

このwriterならあり得るとゴリ押ししたけど、想定解と違うっぽい？
https://www.hackerrank.com/contests/lay-contest-00002/challenges/challenge-387

問題

N個のアラームがある。
各アラームは最初に時刻A[i]に鳴った後時間B[i]毎にまた鳴る。
時刻0～Lの間にアラームは何回鳴るか。
ただし同一時刻に複数のアラームが鳴った場合、1回と数える。

解法

Bの範囲が狭いことを利用して、bit演算でゴリ押した。

L bitのbitsetを考える。
下からk bit目が立っていたら時刻kにアラームが鳴るとする。

B[i]が同じpであるようなアラーム群をまとめて処理しよう。
bitsetのうちB[i]がpであるアラームに対しA[i]bit目を立て、L/p回左シフトした値とのorを取る。

最終的にp=1～60に対して同じ処理をしたbitsetの論理和を取り立っているビット数を数えれば解。
1テストケースの計算量はO(L*H_maxB)程度なので何とか間に合う。(H_nは第n調和数。…この計算量の表記法あっているのかな？)

int T;
int L,N;
int A[10100],B[10101];
unsigned long long M[11111111/64];
unsigned long long M2[11111111/64];
vector<int> V[61];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		ZERO(M);
		
		FOR(i,61) V[i].clear();
		cin>>L>>N;
		FOR(i,N) {
			cin>>A[i]>>B[i];
			V[B[i]].push_back(A[i]);
		}
		for(i=1;i<=60;i++) {
			ZERO(M2);
			FORR(r,V[i]) M2[r/64] |= 1ULL<<(r%64);
			FOR(j,11000000/64) {
				if(j) M2[j] |= M2[j-1]>>(64-i);
				FOR(x,64/i+2) M2[j] |= M2[j]<<i;
				M[j] |= M2[j];
			}
		}
		
		int cnt=0;
		for(i=1;i<=L;i++) cnt+=(M[i/64]>>(i%64))&1;
		cout<<cnt<<endl;
	}
}

まとめ

betaが取れたことですし、次回以降の開催に期待します。