ABC 418

Table of Contents

https://atcoder.jp/contests/abc418

A. I’m a teapot

https://atcoder.jp/contests/abc418/tasks/abc418_a

自力 AC

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

    int N;
    string S;
    cin >> N >> S;

    int m = S.size();
    int ok = 1;
    if (m < 3) {
        ok = 0;
    } else {
        string subs = S.substr(m - 3, 3);
        ok = subs == "tea";
    }

    yesno(ok);
}

B. You’re a teapot

https://atcoder.jp/contests/abc418/tasks/abc418_b

自力 AC

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

    string S;
    cin >> S;

    double ans = 0.0;
    int N = S.size();
    rep(i, N) rep2(j, i + 1, N) {
        if (S[i] == 't' && S[j] == 't' && j - i >= 2) {
            ll len = j - i + 1;
            ll x = 0;
            rep2(k, i, j + 1) if (S[k] == 't') x++;
            chmax(ans, (double)(x - 2) / (double)(len - 2));
        }
    }

    printf("%.15lf\n", ans);
}

C. Flush

https://atcoder.jp/contests/abc418/tasks/abc418_c

自力 AC

$b > \max(A_i)$ のとき、勝利することは不可能。

それ以外のとき

\begin{align*} \left( \sum_{i \in \{ i | A_i < b \}} A_i \right) + \left(\sum_{i \in \{ i | A_i \geq b \}} 1 \right)(b-1) + 1. \end{align*}

ディーラーとしてはあるフレーバーのうち $b$ 個のティーバッグが揃わないようにしたいので、 $b$ 未満の個数しかないティーバッグ全てと、$b$ 個以上あるフレーバーでは $b-1$ 個を配るのが最適。 これ以上配るとどうやっても $b$ 個のティーバッグが揃うフレーバーが出る。

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

    ll N, Q;
    cin >> N >> Q;
    vll A(N), B(Q);
    rep(i, N) cin >> A[i];
    rep(i, Q) cin >> B[i];

    sort(all(A));

    Cumsum cumsum(A);

    for (ll b : B) {
        auto it = lower_bound(all(A), b);
        if (it == A.end()) {
            cout << -1 << endl;
            continue;
        }

        int dist = it - A.begin();
        ll ans = cumsum.sum(0, dist);
        ans += (A.end() - it) * (b - 1);
        ans++;
        cout << ans << endl;
    }
}

D. XNOR Operation

https://atcoder.jp/contests/abc418/tasks/abc418_d

自力 AC

左端を1番目、右端を $j$ 番目 ($j \geq i$) としたときの文字列が美しい文字列となるならば $v_j = 1$、そうでないならば $v_j = 0$ とする。

左端を $i$ 番目としたときの文字が $1$ の場合

$v_i=1$ のとき

$i \leq k \leq N$ の範囲にある $A_k = 1$ のなる $k$ 番目を右端とする文字列は美しい文字列となる。 よって $i \leq k \leq N$ の範囲にある $A_k = 1$ のなる $k$ の個数が $i$ 番目を左端としたときの美しい文字列の個数となる。

$v_i=0$ のとき

$i \leq k \leq N$ の範囲にある $A_k = 0$ のなる $k$ 番目を右端とする文字列は美しい文字列となる。 よって $i \leq k \leq N$ の範囲にある $A_k = 0$ のなる $k$ の個数が $i$ 番目を左端としたときの美しい文字列の個数となる。

左端を $i$ 番目としたときの文字が $0$ の場合

$v_i=1$ のとき

$i \leq k \leq N$ の範囲にある $A_k = 0$ のなる $k$ 番目を右端とする文字列は美しい文字列となる。 よって $i \leq k \leq N$ の範囲にある $A_k = 0$ のなる $k$ の個数が $i$ 番目を左端としたときの美しい文字列の個数となる。

$v_i=0$ のとき

$i \leq k \leq N$ の範囲にある $A_k = 1$ のなる $k$ 番目を右端とする文字列は美しい文字列となる。 よって $i \leq k \leq N$ の範囲にある $A_k = 1$ のなる $k$ の個数が $i$ 番目を左端としたときの美しい文字列の個数となる。

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

    ll N;
    string T;
    cin >> N >> T;

    fenwick_tree<ll> fw(N);
    int pr = T[0] == '1';
    fw.add(0, pr);
    rep2(i, 1, N) {
        if (pr == 1 && T[i] == '1') {
            fw.add(i, 1);
            pr = 1;
        } else if (pr == 1 && T[i] == '0') {
            fw.add(i, 0);
            pr = 0;
        } else if (pr == 0 && T[i] == '1') {
            fw.add(i, 0);
            pr = 0;
        } else if (pr == 0 && T[i] == '0') {
            fw.add(i, 1);
            pr = 1;
        }
    }

    ll ans = 0;
    rep(i, N) {
        int x = T[i] - '0';
        ll numok = fw.sum(i, N);
        if (x == 0) {
            if (fw.sum(i, i + 1) == 1) {
                ll tot = N - i;
                ans += tot - numok;
            } else {
                ans += numok;
            }
        } else {  // x== 1
            if (fw.sum(i, i + 1) == 1) {
                ans += numok;
            } else {
                ll tot = N - i;
                ans += tot - numok;
            }
        }
    }
    cout << ans << endl;
}

E. Trapezium

https://atcoder.jp/contests/abc418/tasks/abc418_e

解説 AC

2点を結んだときの線分を傾きでグルーピングする。 同じ傾き同士の線分を結ぶと台形ができるので、同じ傾きの線分の数を $N$ としたとき $N(N-1)/2$ 個の台形ができる。 ただし、同じ長さ同士の物を結ぶと違う傾きでも同じ台形ができダブルカウントしてしまうので、その分を最終的に引く必要がある。

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

    ll N;
    cin >> N;
    vll X(N), Y(N);
    rep(i, N) cin >> X[i] >> Y[i];

    using P = pair<ll, ll>;
    map<P, vll> mp;
    rep(i, N) rep2(j, i + 1, N) {
        ll xi = X[i], yi = Y[i];
        ll xj = X[j], yj = Y[j];

        ll dy = yj - yi;
        ll dx = xj - xi;
        if (dx == 0) dy = abs(dy);
        if (dy == 0) dx = abs(dx);
        ll g = gcd(dx, dy);
        ll length = dx * dx + dy * dy;
        dy /= g;
        dx /= g;

        if (dx == 0) dy = abs(dy);
        if (dy == 0) dx = abs(dx);

        if (dx < 0) {
            dx *= -1;
            dy *= -1;
        }

        mp[{dx, dy}].push_back(length);
    }

    ll ans = 0;
    ll sq = 0;
    for (auto [p, v] : mp) {
        int sz = v.size();
        ans += sz * (sz - 1) / 2;
        map<ll, ll> freq;

        rep(i, sz) {
            freq[v[i]]++;
        }
        for (auto [_, tt] : freq) {
            sq += tt * (tt - 1) / 2;
        }
    }

    ans -= sq / 2;
    cout << ans << endl;
}

F. We’re teapots

https://atcoder.jp/contests/abc418/tasks/abc418_f

G. Binary Operation

https://atcoder.jp/contests/abc418/tasks/abc418_g