ARC 175

Wed, Jul 2, 2025

A. Spoon Taking Problem

https://atcoder.jp/contests/arc175/tasks/arc175_a

解説 AC. 解説読んで言わんとすることは理解できたが、時間おいてまた解けるかというと自信ない。

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

    ll N;
    cin >> N;
    vll P(N);
    rep(i, N) {
        cin >> P[i];
        P[i]--;
    }
    string S;
    cin >> S;

    auto calL = [&]() -> mint {
        mint ret = 1;
        vint used(N);

        rep(i, N) {
            int now = P[i];
            int r = (P[i] + 1) % N;
            if (!used[r] && S[now] == 'R') {
                ret = 0;
            }
            if (used[r] && S[now] == '?') {
                ret *= 2;
            }
            used[now] = 1;
        }
        return ret;
    };

    auto calR = [&]() -> mint {
        mint ret = 1;
        vint used(N);

        rep(i, N) {
            int now = P[i];
            int l = P[i], r = (P[i] + 1) % N;
            if (!used[l] && S[now] == 'L') {
                ret = 0;
            }
            if (used[l] && S[now] == '?') {
                ret *= 2;
            }
            used[r] = 1;
        }
        return ret;
    };

    mint ans = calL() + calR();
    cout << ans.val() << endl;
}

B. Parenthesis Arrangement

https://atcoder.jp/contests/arc175/tasks/arc175_b

解説 AC. 方針としては概ねあっていたが、))(( のときに操作2だけを適用したときのコストを $4B$ としてしまっていた。正しくは $2B$ であった。

カッコの対応が取れている部分に対して操作をする必要はないので除外することを繰り返すと最終的に文字列は ))...)(...(( の形になる。

ここで ))(( を正しいカッコ列にするには 1, 4 番目を swap する(操作1) か、 1 番目, 4 番目を反転させる (操作2) のどちらかを適用する必要がある。 (1度の swap 操作で4つのカッコを消すことができる。)( に対してすぐに正しいカッコ列を作るよりもまとまりを大きくしたほうが得なことがある。)

操作 1 を適用する場合はコスト $A$ 掛かり、操作 2 を適用する場合はコスト $2B$ 掛かる。このうちコストを小さい方を適用できる限り適用していくのが最適である。

余剰の ( または ) が 1 個だけ残った場合は、操作 1, 2 のうちコストが小さい方を適用して余剰分を消す。

最終的に ( または ) のいずれかが残る文字列になる。その長さを $M$ とすると $\frac{M}{2} \times B$ をさらに答えに加えると最終的な答えになる。

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

    ll N, A, B;
    string S;
    cin >> N >> A >> B >> S;

    string T = "";

    rep(i, N * 2) {
        if (T.size() && S[i] == ')' && T.back() == '(') {
            T.pop_back();
        } else {
            T.push_back(S[i]);
        }
    }

    ll numl = 0, numr = 0;
    for (char c : T) {
        if (c == ')')
            numl++;
        else
            numr++;
    }

    ll num = min(numl, numr);
    ll q = num / 2;

    ll ans = 0;
    ans += min(A, B * 2) * q;

    numl -= q * 2;
    numr -= q * 2;

    if (min(numl, numr) == 1) {
        ans += min(A, B * 2);
        numl--;
        numr--;
    }

    num = max(numr, numl);
    ans += num / 2 * B;
    cout << ans << endl;
}