lay_contest round 00002 近所迷惑高橋くん

問題

www.hackerrank.com

解法

kmjp さんの解法を参考にしました。
kmjp.hatenablog.jp

L bit の bitset を考えて, i bit 目が立っていたら, 「時刻 i に目覚ましが鳴る」と考えることにします。愚直にやるなら, 各 (A[i], B[i]) について, A[i] からスタートして B[i] ごとにフラグを 1 にしていく, となります。

この計算を高速化するために, B[i] の値ごとに区分けします。
今インターバルが b になっている目覚まし時計のセットについて考えている時, 最初に B[i] = b を満たす i について A[i] bit 目にフラグを立てます。その後は, b 個ごとにまとめて or を取ることで計算を高速化します。

最初はこれを bitset で出来ないかなーと思ってたんですが難しそうだったので諦めました。注意したことは,

• unsigned long long を使わないと計算がおかしくなる(long long は NG)
• 64 bit ごとにやるので区切りが中途半端なところは注意が必要(写真)

const int INF = 1e9;
const int MAXL = 11000000;

ull M[MAXL/64], M2[MAXL/64];
int memo[64][64];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
        int L, N;
        cin >> L >> N;
        memset(M, 0, sizeof(M));
        for (int i = 0; i < 64; i++) for (int j = 0; j < 64; j++) {
            memo[i][j] = MAXL-10000;
        }
        for (int i = 0; i < N; i++) {
            int a, b;
            cin >> a >> b;
            memo[b][a%b] = min(memo[b][a%b], a);
        }
        for (int i = 1; i <= 60; i++) {
            memset(M2, 0, sizeof(M2));
            for (int j = 0; j < i; j++) {
                int tmp = memo[i][j];
                M2[tmp/64] |= 1ull<<(tmp%64);
            }
            for (int j = 0; j*64 < MAXL; j++) {
                if (j) M2[j] |= M2[j-1] >> (64-i);
                for (int k = 0; k <= 64/i+1; k++) M2[j] |= M2[j]<<i;
                M[j] |= M2[j];
            }
        }
        ull ans = 0;
        for (int i = 1; i <= L; i++) ans += (M[i/64]>>(i%64))&1;
        cout << ans << endl;
    }
    return 0;
}