ABC179 解法

Posted on 2 mins read

ABC179の参加記です。

フル提出

A - Plural Form

場合分け。

signed main() {
    std::string s;
    std::cin >> s;
    if (s.back() == 's') {
        s += "es";
    } else {
        s += "s";
    }
    std::cout << s << std::endl;
}

B - Go to Jail

for文。

signed main() {
    Int n;
    std::cin >> n;
    std::vector<Int> a(n), b(n);
    REP(i, n) std::cin >> a[i] >> b[i];
    REP(i, n - 2) {
        bool ok = true;
        REP(j, i, i + 3) {
            if (a[j] != b[j]) ok = false;
        }
        if (ok) {
            std::cout << "Yes" << std::endl;
            return 0;
        }
    }
    std::cout << "No" << std::endl;
}

C - A x B + C

Aを固定すると、正の(B, C)の候補は(n - 1)/A通りになる。

signed main() {
    Int n;
    std::cin >> n;
    Int ans = 0;
    REP(a, 1, n + 1) { ans += (n - 1) / a; }
    std::cout << ans << std::endl;
}

D - Leaping Tak

DPを考えると、更新式が連続区間の和の形で表せるため、累積和で高速化できる。

signed main() {
    Int n, K;
    std::cin >> n >> K;
    std::vector<Int> L(K), R(K);
    REP(i, K) std::cin >> L[i] >> R[i];
    std::vector<mint> dp(n), acc(n + 1);
    dp[0] = acc[1] = 1;
    REP(i, 1, n) {
        REP(j, K) { dp[i] += acc[std::max(0LL, i - L[j] + 1)] - acc[std::max(0LL, i - R[j])]; }
        acc[i + 1] = acc[i] + dp[i];
    }
    std::cout << dp[n - 1] << std::endl;
}

E - Sequence Sum

一度出た数がもう一度出るとそれ以降は繰り返しなので、周期M以下。 繰り返しはまとめることでO(M)で計算できる。

signed main() {
    Int n, x, m;
    std::cin >> n >> x >> m;
    std::vector<Int> memo(m + 2, x);
    std::vector<Int> cnt(m, -1);
    REP(i, m + 1) {
        if (cnt[memo[i]] != -1) {
            Int ans = 0, tmp = 0;
            REP(j, std::min(n, cnt[memo[i]])) ans += memo[j];
            REP(j, cnt[memo[i]], i) tmp += memo[j];
            Int rem = n - cnt[memo[i]];
            if (rem > 0) {
                Int cycle = i - cnt[memo[i]];
                ans += tmp * (rem / cycle);
                REP(j, cnt[memo[i]], cnt[memo[i]] + rem % cycle) ans += memo[j];
            }
            std::cout << ans << std::endl;
            return 0;
        }
        cnt[memo[i]] = i;
        memo[i + 1] = memo[i] * memo[i] % m;
    }
}

F - Simplified Reversi

1点取得と区間chminができればよいので遅延セグ木で殴った。

#include <atcoder/lazysegtree>

Int min(Int a, Int b) { return std::min(a, b); }
Int inf() { return 1e18; }
signed main() {
    Int n, Q;
    std::cin >> n >> Q;
    atcoder::lazy_segtree<Int, min, inf, Int, min, min, inf> seg1(std::vector<Int>(n - 1, n - 1));
    atcoder::lazy_segtree<Int, min, inf, Int, min, min, inf> seg2(std::vector<Int>(n - 1, n - 1));
    Int ans = (n - 2) * (n - 2);
    REP(q, Q) {
        Int t, x;
        std::cin >> t >> x, x--;
        if (t == 1) {
            Int j = seg2.get(x);
            ans -= j - 1;
            seg1.apply(0, j, x);
        } else {
            Int j = seg1.get(x);
            ans -= j - 1;
            seg2.apply(0, j, x);
        }
    }
    std::cout << ans << std::endl;
}