ARC 163

Wed, Jun 4, 2025

A. Divide String

https://atcoder.jp/contests/arc163/tasks/arc163_a

自力 AC

文字列の長さは 2 としてよい。なぜなら $t_1 < t_2 + \cdots + t_k$ であるから。

よって文字列を前半と後半に分割して $t_1 < t_2$ となる分割方法があるか判定すればよい。

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

    auto cal = []() -> void {
        ll N;
        string S;
        cin >> N >> S;

        rep2(i, 1, N) {
            string l = S.substr(0, i);
            string r = S.substr(i, N - i);
            if (l < r) {
                Yes();
                return;
            }
        }
        No();
    };

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

B. Favorite Game

https://atcoder.jp/contests/arc163/tasks/arc163_b

自力 AC

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

    int N, M;
    cin >> N >> M;
    vll A(N);
    rep(i, N) cin >> A[i];

    ll l = A[0], r = A[1];
    vll B;
    rep2(i, 2, N) B.push_back(A[i]);
    sort(all(B));

    ll ans = INF;
    for (int i = 0; i + M - 1 < N - 2; i++) {
        ll left = B[i], right = B[i + M - 1];
        ll tmp = 0;
        if (left < l) tmp += l - left;
        if (r < right) tmp += right - r;
        chmin(ans, tmp);
    }
    cout << ans << endl;
}