AtCoder Beginner Contest 367（ABC367）

atcoder.jp

A - Shout Everyday

for文などで寝ている時間のフラグを立てて、判定する

提出コード

void solve() {
    int A, B, C;
    cin >> A >> B >> C;
    vector<int> awake(24, true);
    for (int i = B;; i++) {
        awake[i] = false;
        if (i == 23) i = -1;
        if (i == C - 1) break;
    }
    cout << (awake[A] ? "Yes" : "No") << endl;
}

B - Cut .0

文字列で受け取って、後ろから連続する0を削除する

提出コード

void solve() {
    string X;
    cin >> X;
    string seisu = "";
    string shosu = "";
    bool ok = false;
    for (char c : X) {
        if (c == '.') {
            ok = true;
            continue;
        }
        if (!ok) seisu += c;
        if (ok) shosu += c;
    }
    for (int i = shosu.size() - 1; i >= 0; i--) {
        if (shosu[i] == '0') shosu.pop_back();
        else break;
    }
    if (shosu.empty()) cout << seisu << endl;
    else cout << seisu << "." << shosu << endl;
}

C - Enumerate Sequences

再帰関数などで実際に列挙して出力する

提出コード

void solve() {
    int N, M;
    cin >> N >> M;
    vector<int> A(N * 2);
    REP(i, N) {
        cin >> A[i];
        A[i + N] = A[i];
    }
    map<ll, ll> mp;
    vector<ll> cum(2 * N + 1);
    ll ans = 0;
    REP(i, N) {
        cum[i + 1] = cum[i] + A[i];
        mp[cum[i] % M]++;
    }
    REP(i, N, 2 * N) {
        cum[i + 1] = cum[i] + A[i];
        mp[cum[i - N] % M]--;
        ans += mp[cum[i] % M];
        mp[cum[i] % M]++;
    }
    cout << ans << endl;
}

D - Pedometer

Zero-Sum rangesみたいな感じ
1周分の長さを保ちながらしゃくとりっぽくやる

提出コード

void solve() {
    int N, M;
    cin >> N >> M;
    vector<int> A(N * 2);
    REP(i, N) {
        cin >> A[i];
        A[i + N] = A[i];
    }
    map<ll, ll> mp;
    vector<ll> cum(2 * N + 1);
    ll ans = 0;
    REP(i, N) {
        cum[i + 1] = cum[i] + A[i];
        mp[cum[i] % M]++;
    }
    REP(i, N, 2 * N) {
        cum[i + 1] = cum[i] + A[i];
        mp[cum[i - N] % M]--;
        ans += mp[cum[i] % M];
        mp[cum[i] % M]++;
    }
    cout << ans << endl;
}

E - Permute K times

ダブリングをする
1回の操作を元の $ A $ のindexのうち、どのindexに移動するかと考えるとそれぞれのindexに対応する移動先は固定になるのでダブリングで求めることができる

提出コード

void solve() {
    ll N, K;
    cin >> N >> K;
    vector<int> X(N);
    vector<int> A(N);
    REP(i, N) {
        cin >> X[i];
        X[i]--;
    }
    REP(i, N) cin >> A[i];

    vector<vector<ll>> to(62, vector<ll>(N));
    REP(i, N) to[0][i] = X[i];
    REP(i, 61) REP(j, N) to[i + 1][j] = to[i][to[i][j]];

    REP(i, N) {
        ll cur = i;
        REP(j, 62) {
            if ((K >> j) & 1) {
                cur = to[j][cur];
            }
        }
        cout << A[cur] << " ";
    }
    cout << endl;
}

F - Rearrange Query

各要素にZobrist Hashでhashを割り当てておく
Mo法で各クエリにおける集合のhashを求め、それが一致するかどうかで判定ができる
同じ要素が複数ある時の場合でも、hashの加減算で一致判定が高い確率で行える

提出コード

void solve() {
    int N, Q;
    cin >> N >> Q;
    vector<int> a(N), b(N);
    REP(i, N) { cin >> a[i]; }
    REP(i, N) { cin >> b[i]; }
    vector<uint32_t> hash(202020);
    REP(i, 202020) { hash[i] = XorShift(); }
    vector<int> l(Q), r(Q), L(Q), R(Q);

    REP(i, Q) {
        cin >> l[i] >> r[i] >> L[i] >> R[i];
        --l[i], --L[i];
    }
    vector<uint32_t> ans1(Q), ans2(Q);
    uint32_t sum1 = 0, sum2 = 0;
    auto add1 = [&](int idx) { sum1 += hash[a[idx]]; };
    auto erase1 = [&](int idx) { sum1 -= hash[a[idx]]; };
    auto out1 = [&](int idx) { ans1[idx] = sum1; };
    auto add2 = [&](int idx) { sum2 += hash[b[idx]]; };
    auto erase2 = [&](int idx) { sum2 -= hash[b[idx]]; };
    auto out2 = [&](int idx) { ans2[idx] = sum2; };
    Mo mo1(N);
    Mo mo2(N);
    REP(i, Q) {
        mo1.add(l[i], r[i]);
        mo2.add(L[i], R[i]);
    }
    mo1.build(add1, erase1, out1);
    mo2.build(add2, erase2, out2);
    REP(i, Q) { cout << (ans1[i] == ans2[i] ? "Yes" : "No") << endl; }
}