[Codeforces] Educational Round 68 (Div. 2) C. From S To T

2019年7月23日

問題

方針

題意

文字列 \( s \) に \( p\) に含まれる文字の数だけ任意の場所に挿入して、文字列 \(t\) を作ることができるか調べます。

文字が現れる頻度を計算する

各文字列についてどの文字の頻度を計算します。もし、 \( s \) のある文字の頻度が \( t \) よりも大きい場合、作ることはできません。また、\( s \) と \( p \) のある文字の頻度の合計が、\( t \) のものよりも小さい時、作ることはできません。

実際に文字列を作れるか調べる

上記の計算をクリアした文字列について実際に \( t \) を作れるかどうかを調べます。\( s \) と \( t \) の先頭の文字から調べていき、それぞれに対応するインデックスを \( i_s \), \( i_t\) とします。

  1. \( i_s = |s| \) のとき、\(s \) の最後尾に文字を追加して \( t \) を作れるかどうかを調べます。
  2. \( i_s < |s| \) のとき、\( s(i_s) = t(i_t) \) ならば、\(i_s\) と \(i_t\) をインクリメントします。\( s(i_s) \neq t(i_t) \) ならば、\(s(i_s) = t(i_t) \) となるように、\( p \) から文字を持ってきます。そして、\( i_t\) をインクリメントします。

コード