ABC 428

Table of Contents

https://atcoder.jp/contests/abc428

A. Grandma’s Footsteps

https://atcoder.jp/contests/abc428/tasks/abc428_a

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll S, A, B, X;
    cin >> S >> A >> B >> X;
    ll ans = 0;
    ans += S * A * (X / (A + B));
    ans += S * min(A, X % (A + B));
    cout << ans << endl;
}

B. Most Frequent Substrings

https://atcoder.jp/contests/abc428/tasks/abc428_b

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, K;
    string S;
    cin >> N >> K >> S;

    map<string, ll> cnt;
    rep(i, N - K + 1) {
        cnt[S.substr(i, K)]++;
    }

    ll mx = 0;
    for (auto [k, v] : cnt) chmax(mx, v);
    vector<string> ans;
    for (auto [k, v] : cnt)
        if (v == mx) ans.push_back(k);
    sort(all(ans));

    cout << mx << endl;
    print(ans);
}

C. Brackets Stack Query

https://atcoder.jp/contests/abc428/tasks/abc428_c

pair が作れていない ( の数を $L$ と、pair が作れていない ) の数を $R$ とする。 $L, R$ がともに 0 のとき良い括弧列となり、それ以外のときは良い括弧列にはならない。

タイプ1のクエリが来たとき、( が来たら $L$ を 1 増やし、) が来たら $L$ を 1 減らす。 ただし $L$ が 0 のときに ) が来たら $R$ を 1 増やす。また、タイプ2のクエリが来たときに ) を削除する際に、その ) が pair が作られていたものかどうかが区別できないと $R$ を更新する必要があるのかどうかがわからないので、$R$ を増やすときはその位置にある ) が pair が作られていないものであることを記録しておく。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int Q;
    cin >> Q;
    string S = "";

    vint invalid(Q + 1);
    ll unpaired_left, invalid_right;
    unpaired_left = invalid_right = 0;

    rep(i, Q) {
        int t;
        cin >> t;
        if (t == 1) {
            char c;
            cin >> c;

            if (c == '(') {
                unpaired_left++;
            } else {  // )
                if (unpaired_left) {
                    unpaired_left--;
                } else {
                    invalid[S.size()] = 1;
                    invalid_right++;
                }
            }

            S.push_back(c);
        } else {
            char c = S.back();

            if (c == '(') {
                unpaired_left--;
            } else {
                if (invalid[(int)S.size() - 1]) {
                    invalid[(int)S.size() - 1] = 0;
                    invalid_right--;
                } else {
                    unpaired_left++;
                }
            }
            S.pop_back();
        }

        yesno(unpaired_left == 0 && invalid_right == 0);
    }
}

D. 183184

https://atcoder.jp/contests/abc428/tasks/abc428_d

上位の桁が $C$ と同じになるような平方数の平方根はどんな数字かということについて考えると、

を調べれればよいことがわかる。 ここで suffix の数字は $x \in [C+1, C+D]$ の範囲に収まる数字であるため、この範囲に入らない分は除外する必要がある。

上限と下限が決まれば $X$ 以下の平方数の数は $\lfloor \sqrt{X} \rfloor$ で求められるため、 上限を $U$, 下限を $L$ としたときに $ \lfloor \sqrt{U} \rfloor - \lfloor \sqrt{L-1} \rfloor$ でその範囲にある平方数の数を求めることができる。

単純に $\lfloor \sqrt{f(C, C+D)} \rfloor - \lfloor \sqrt{f(C, C)} \rfloor$ を求めるだけでも良さそうに見えるけれど、これでは suffix に leading zero が含まれる場合を除外できない。

たとえば $C = 1$ のときを考えると $10201 = 101^2$ であるが $0201$ のような leading zero は十進数表記ではありえないためこの平方数はカウントしてはいけない。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    vll tenth(11);
    tenth[0] = 1;
    rep2(i, 1, 11) {
        tenth[i] = tenth[i - 1] * 10;
    }

    auto cal = [&]() -> void {
        ll C, D;
        cin >> C >> D;

        ll MI = C + 1, MX = C + D;
        ll ans = 0;
        rep(i, 10) {
            ll tc = C;

            ll mi = max(MI, tenth[i]);
            ll mx = min(MX, tenth[i + 1] - 1);
            if (mi > mx) continue;

            tc *= tenth[i + 1];
            ll l = sqrtl(tc + mi - 1), r = sqrtl(tc + mx);
            ans += r - l;
        }
        cout << ans << endl;
    };

    int t;
    cin >> t;
    rep(i, t) cal();
}

E. Farthest Vertex

https://atcoder.jp/contests/abc428/tasks/abc428_e

答えは木の直径になるパスの端点のうちのどちらかになる。 まず適当な頂点から DFS して最も遠い頂点を求める。同じ距離のものが複数ある場合はそのうちの最大の頂点番号を選ぶ。 その頂点番号を $v$ とする。

次に $v$ から DFS して最も遠い頂点を求める。同じ距離のものが複数ある場合はそのうちの最大の頂点番号を選ぶ。 その頂点番号を $u$ とする。

$u$, $v$ からそれぞれ DFS して各頂点までの距離を求める。 各頂点について、$u$ からの距離と $v$ からの距離を比較し、距離が大きい方の頂点番号を答えとする。 距離が同じ場合は頂点番号の大きい方を答えとする。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vvint graph(N);
    rep(i, N - 1) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    {
        vll dist(N);
        auto dfs = [&](auto dfs, auto& dist, int now, int p, ll depth) -> void {
            chmax(dist[now], depth);

            for (int nx : graph[now]) {
                if (nx == p) continue;
                dfs(dfs, dist, nx, now, depth + 1);
            }
        };

        dfs(dfs, dist, 0, -1, 0);

        int rid = -1, lid = -1;

        {
            ll mx = *max_element(all(dist));
            rep(i, N) if (dist[i] == mx) rid = i;
        }

        vll rdist(N, 0);
        dfs(dfs, rdist, rid, -1, 0);

        {
            ll mx = *max_element(all(rdist));
            rep(i, N) if (rdist[i] == mx) lid = i;
        }

        vll ldist(N, 0);
        dfs(dfs, ldist, lid, -1, 0);
        rep(i, N) {
            ll ans;
            if (ldist[i] == rdist[i]) {
                ans = max(rid, lid) + 1;
            } else if (ldist[i] < rdist[i]) {
                ans = rid + 1;
            } else {
                ans = lid + 1;
            }
            cout << ans << '\n';
        }
    }
}

F. Pyramid Alignment

https://atcoder.jp/contests/abc428/tasks/abc428_f

G. Necklace

https://atcoder.jp/contests/abc428/tasks/abc428_g