Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 301 C問題 AtCoder Cards

AtCoder ABC ABC301 C問題 300 pts

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

英小文字と {\tt @} からなる長さが等しい文字列 S,T がある. この S,T に対して, 以下の操作を順に行う.

  • S,T にある {\tt @} をそれぞれ {\tt a}, {\tt t}, {\tt c}, {\tt o}, {\tt d}, {\tt e}, {\tt r} のどれかに置き換える.
  • S,T を適用に並び替える.

S=T にすることは可能か?

制約

  • S,T は英小文字と {\tt @} からなる長さ 1 以上 2 \times 10^5 以下の文字列.

解法

文字列 U に含まれる c の数を \chi_U(c) と書く. ここで, 並び替えが自由にできるので, 結局は \chi_S(c), \chi_T(c) にのみ着目すれば良いことがわかる.

このとき, {\tt a}, {\tt t}, {\tt c}, {\tt o}, {\tt d}, {\tt e}, {\tt r} ではない英小文字 {\tt c} については \chi_S(c)=\chi_T(c) でなくてはならない.

一方で, {\tt a}, {\tt t}, {\tt c}, {\tt o}, {\tt d}, {\tt e}, {\tt r} のどれかである英小文字については, \chi_S(c), \chi_T(c) を比較し, 小さい方の文字列における {\tt @} をその差分だけ {\tt c} に置き換えなければならず, 実際に, その差だけ置き換えれば良い.

この置き換えによって, {\tt @} が不足してしまうと, 不可能であり, 不足しなければ可能である.