結構整理するの大変！　茶色あっても良さそうだと思ったけど、灰色上位問題だった。

問題へのリンク

問題概要

2 つの長さ $N$ の文字列 $S, T$ が与えられる。これらは英小文字または文字 '@' のみからなる。

$S, T$ の各文字 '@' は、"atcoder" に含まれるいずれかの文字に変えることができる。

その後、 $S$ の文字を並び替えることで $T$ に一致させることが可能かどうかを判定せよ。

制約

$1 \le N \le 2 \times 10^{5}$

考えたこと

まずは入力例を見て考えよう。

ch@kud@i
akidu@ho

一つ言えるのは、 $S$ と $T$ とで同じ文字があったら、対消滅させて削除してしまってよい。たとえば、上の入力例で、 $S$ の前から 2 文字目の 'h' と、 $T$ の後ろから 2 文字目の 'h' は消し去ってよい。

対消滅操作をやり切った上で、 $S, T$ をそれぞれアルファベット順に並び替えると、次のようになる。

c@@
ao@

残りは、次のようにすることで、 $S, T$ を等しくできる。

$S$ の残り文字列 "c" を、 $T$ の "@" に当てはめる
$T$ の残り文字列 "ao" を、 $S$ の "@@" に当てはめる

ダメな場合を洗い出す

問題の様子を掴めて来たところで、「No になるのはどんな場合か」を洗い出すことが有効だ。たとえば、入力例 3 を考えよう。

aoki
@ok@

先ほどと同様に、 $S, T$ の同じ文字を除去すると次のようになる。

ai
@@

ここで、一見 $T$ の "@@" を "ai" にすればよいように思われる。しかし、文字 'i' は文字列 "atcoder" に含まれていないため、ダメだ。

また、次のケースもダメだ。

aaac@@
acccc@

ダメな理由を考えてみよう。 $S, T$ の同じ文字を除去すると次のようになる。

aa@@
ccc@

この場合、文字 '@' の個数が足りないのだ。

ここまでで、ダメな場合として次のパターンが洗い出された。

$S, T$ の共通の文字をすべて除去したあと

$S$ または $T$ に、文字列 "atcoder" に含まれない文字が含まれる場合はダメ
「 $S$ の '@' 以外の文字数 > $T$ の '@' の個数」の場合はダメ
「 $T$ の '@' 以外の文字数 > $S$ の '@' の個数」の場合はダメ

逆に、これらダメな場合をすべてクリアしていれば、大丈夫なことは明らかだ。

コード

以上のロジックは次のように実装できる。計算量は $O(N)$ となる。

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    // "atcoder" 内部の文字
    set<char> atc;
    for (auto c : "atcoder") atc.insert(c);
    
    // 入力
    string S, T;
    cin >> S >> T;
    
    // S, T 中の @ の個数を数える
    int alpha_num_S = 0, alpha_num_T = 0;
    for (auto c : S) if (c == '@') ++alpha_num_S;
    for (auto c : T) if (c == '@') ++alpha_num_T;
    
    // 各文字 c = 'a', 'b', ..., 'z' に対して、S, T で共通の文字を対消滅させる
    bool ok = true;
    for (char c = 'a'; c <= 'z'; ++c) {
        // S, T 中の文字 c の個数を数える
        int c_num_S = 0, c_num_T = 0;
        for (auto sc : S) if (sc == c) ++c_num_S;
        for (auto tc : T) if (tc == c) ++c_num_T;
        
        // もし S, T いずれかに文字が余ったとき、それが "atcoder" に含まれないとダメ
        if (c_num_S != c_num_T && !atc.count(c)) ok = false;
        
        // S, T の文字 c を対消滅させて、残った個数分、文字 @ を削る
        if (c_num_S > c_num_T) alpha_num_T -= (c_num_S - c_num_T);
        else alpha_num_S -= (c_num_T - c_num_S);
    }
    if (alpha_num_S < 0 || alpha_num_T < 0) ok = false;
    
    cout << (ok ? "Yes" : "No") << endl;
}

Python3

import string

# 入力
S, T = input(), input()
alpha_num_S, alpha_num_T = S.count('@'), T.count('@')

# 各文字 c = 'a', 'b', ..., 'z' に対して、S, T で共通の文字を対消滅させる
ok = True
for c in string.ascii_lowercase:
    # S, T 中の文字 c の個数を数える
    c_num_S, c_num_T = S.count(c), T.count(c)
    
    # もし S, T いずれかに文字が余ったとき、それが "atcoder" に含まれないとダメ
    if c_num_S != c_num_T and c not in "atcoder":
        ok = False
        
    # S, T の文字 c を対消滅させて、残った個数分、文字 @ を削る
    if c_num_S > c_num_T:
        alpha_num_T -= (c_num_S - c_num_T)
    else:
        alpha_num_S -= (c_num_T - c_num_S)

# 文字 @ が不足したらダメ
if alpha_num_S < 0 or alpha_num_T < 0:
    ok = False
    
print("Yes" if ok else "No")

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 301 C - AtCoder Cards (灰色, 300 点)

問題概要

制約

考えたこと

ダメな場合を洗い出す

コード

C++

Python3