AtCoder Beginner Contest 428 [ABC428] A ~ D問題

AtCoder Beginner Contest 428に参加しました。
A~Dの4完でした。
パフォーマンス 1120
レーティング 1139 → 1137 (-2) となりました。
かなり悔しい結果でした。

A - Grandma's Footsteps

$(A + B)$ 秒の周期で考えると 高橋君は $A \cdot \lfloor \frac{X}{A + B} \rfloor $ 秒走ることができます。
残りの$X \, \% \, (A + B)$ 秒で 高々 $A$ 秒走ることができるので、
答えは$S \cdot \Bigl(A \cdot \lfloor \frac{X}{A + B} \rfloor + \min(X \, \% \, (A + B), \, A)\Bigr)$ です。

cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    int S, A, B, X;
    cin >> S >> A >> B >> X;
    cout << S * (A * (X / (A + B)) + min(X % (A + B), A)) << endl;
}

B - Most Frequent Substrings

std::mapに 長さ $K$ である$S$ の連続部分列を全て記録します。出現回数が最も多い部分列は
簡単に列挙することができます。

cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, K;
    string S;
    cin >> N >> K >> S;
    map<string, int> mp;
    int M = 0;
    for (int i = 0; i + K - 1 < N; i++) {
        string T = S.substr(i, K);
        mp[T]++;
        M = max(M, mp[T]);
    }

    cout << M << endl;
    for (auto &[s, cnt] : mp) if (cnt == M) cout << s << " ";
    cout << endl;
}

C - Brackets Stack Query

長さ $N$ の文字列 $T$ が 「良い括弧列」 であるとは次のことと同値です。

• $T$ に含まれる ( と ) の個数が等しい
• $1 \leq i \leq N$ を満たす任意の整数 $i$ について、
  ($T[1, i]$ に含まれる ( の個数) $\geq$ ($T[1, i]$ に含まれる ) の個数) が成り立つ。

したがって、$S$ に含まれる (, ) の個数を表す変数と 上の2つめの条件を満たす $i$ の個数を表す変数を持てばよいです。
それらは $O(1)$ で更新できるので、計算量は $O(Q)$ です。

cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    int Q;
    cin >> Q;

    string S;
    int cnt_l = 0, cnt_r = 0, now = 0;
    auto update = [&](char c, int x) {
        if (x == -1) now -= (cnt_l >= cnt_r);
        if (c == '(') cnt_l += x;
        else cnt_r += x;
        if (x == 1) now += (cnt_l >= cnt_r);
    };

    while (Q--) {
        int type;
        cin >> type;
        
        if (type == 1) {
            char c;
            cin >> c;
            update(c, 1);
            S.push_back(c);
        }

        else {
            update(S.back(), -1);
            S.pop_back();
        }

        cout << (cnt_l == cnt_r && now == cnt_l + cnt_r ? "Yes" : "No") << endl;
    }
}

D - 183184

整数 $a$ の桁数を $len(a)$ と表すことにします。また、 $len(C + x) = d$ とします。
これは $10^{d - 1} \leq C + x \leq 10^d - 1$ と同値です。
また、 $1 \leq x \leq D$ より、 $C + 1 \leq C + x \leq C + D$ となります。
これらが共通部分を持つとき、
$\max(10^{d - 1}, C + 1) \leq C + x \leq \min(10^d - 1, C + D)$ が成り立ちます。
よって、$f(C, C + x)$ の取り得る値の範囲にある平方数の個数を求めることができます。
1つのテストケースあたりほぼ $O(1)$ で計算することができるので、十分高速です。

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll SQRT(ll a) {
    ll x = sqrtl(a);
    while ((x + 1) * (x + 1) <= a) x++;
    while ((x - 1) * (x - 1) >= a) x--;
    return x;
}

ll range_SQRT(ll l, ll r) {
    return SQRT(r) - SQRT(l - 1);
}

int len(ll x) {
    string s = to_string(x);
    return int(s.size());
}

ll Pow(int x) {
    ll res = 1;
    for (int i = 0; i < x; i++) res *= 10;
    return res;
}

void solve() {
    ll C, D;
    cin >> C >> D;
    ll ans = 0;
    for (int d = len(C + 1); d <= len(C + D); d++) {
        ll L = max(Pow(d - 1), C + 1);
        ll R = min(Pow(d) - 1, C + D);
        if (L <= R) ans += range_SQRT(C * Pow(d) + L, C * Pow(d) + R);
    }

    cout << ans << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}