【AtCoder】ABC 447 C - Insert and Erase A

2026-03-01

AtCoder/ABC/C問題 AtCoder/ABC/300点問題 AtCoder/灰Diff AtCoder/NoviSteps/2Q AtCoder/文字列操作による一致可能性の判定競技プログラミング

C - Insert and Erase A

C - Insert and Erase A

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 326 / NoviSteps: 2Q / 配点: 300 点

問題概要

英大文字からなる文字列 $S,T$ が与えられる。あなたは以下の $2$ 種類の操作を好きな順序で $0$ 回以上行うことができる。

$S$ の好きな位置(先頭および末尾を含む)に文字Aを $1$ つ挿入する。
$S$ に含まれる文字Aを $1$ つ選んで削除する。なお、残った文字は元の順序を保ったまま連結される。

$S$ を $T$ に一致させることが可能かどうか判定し、可能な場合は必要な操作回数の合計の最小値を求めよ。

制約

$1 \le |S|, |T| \le 3 \times 10^5$

考察

操作によって変更を加えられるのは文字列内のAの個数のみであるから、 $S$ と $T$ の両方から文字Aを全て取り除いた文字列をそれぞれ $S', T'$ としたとき、 $S' \neq T'$ ならば、 $S = T$ にすることは不可能である。

その後、 $S$ と $T$ をA以外の文字で分割し、それぞれの区間に含まれるAの個数を数える配列 $s, t$ を作る。サンプルケース3で言えば、以下のようになる。

\begin{align*} s & = \{3, 1, 4, 3, 0\} \\ t & = \{1, 2, 1, 5, 1\} \end{align*}

ある区間でAを削除して別の区間にAを追加すると、合計2回の操作になる。これは、それぞれの区間で独立して削除と追加を行うのと同じコストであるから、各区間ごとに独立して $S$ のAの数を $T$ の対応する区間のAの数に合わせるのが最適である。

したがって、求めるべき答えは $\displaystyle \sum |s_i - t_i|$ となる。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
5. 
6.// ======================================== //
7. 
8.int main()
9.{
10.    string S, T;
11.    cin >> S >> T;
12. 
13.    vector<int> s_a_cnts, t_a_cnts;
14.    string s_no_a, t_no_a;
15.    int cnt_s = 0, cnt_t = 0;
16.    for (char c : S)
17.    {
18.        if (c == 'A')
19.        {
20.            cnt_s++;
21.        }
22.        else
23.        {
24.            s_no_a += c;
25.            s_a_cnts.push_back(cnt_s);
26.            cnt_s = 0;
27.        }
28.    }
29.    s_a_cnts.push_back(cnt_s);
30. 
31.    for (char c : T)
32.    {
33.        if (c == 'A')
34.        {
35.            cnt_t++;
36.        }
37.        else
38.        {
39.            t_no_a += c;
40.            t_a_cnts.push_back(cnt_t);
41.            cnt_t = 0;
42.        }
43.    }
44.    t_a_cnts.push_back(cnt_t);
45. 
46.    if (s_no_a != t_no_a)
47.    {
48.        cout << -1 << endl;
49.        return 0;
50.    }
51. 
52.    int ans = 0;
53.    rep(i, 0, s_a_cnts.size())
54.    {
55.        ans += abs(s_a_cnts[i] - t_a_cnts[i]);
56.    }
57. 
58.    cout << ans << endl;
59. 
60.    return 0;
61.}

https://atcoder.jp/contests/abc447/submissions/73691188

実装時間: 10分

コメント

この問題、サンプルケースにA以外の文字が連続するケースがないので、 $s, t$ をランレングス圧縮によって構築するような解法がサンプルを通ってしまうのがちょっと怖いなと思った。