lyrics-lesson

解説

方針

• 本問題では任意の 2 点入れ替えが許されるため、 可否の必要十分条件は「文字ごとの出現回数（多重集合）が一致すること」 である。ここが一致しない場合はどれだけ入れ替えても一致しないので -1 を出力する。
• 可能な場合は、左から順に位置を確定する貪欲法で構成できる。添字 $i$ を左から見ていき、すでに $S_i = T_i$ なら何もしない。$S_i \ne T_i$ なら、右側（$j>i$）のどこかにある $T_i$ を 1 つ選び、$i$ と $j$ を 1 回の入れ替えで一致させて位置 $i$ を確定する。以後、確定済みの左側は触らない。
• 正当性は次の不変量で保証される：前段で多重集合が一致しており、かつ左から順に一致を固定していくので、任意の時点で「未確定区間 $i..N-1$ に含まれる各文字数」は「$T_i..T_{N-1}$ に含まれる各文字数」と一致し続ける。したがって毎ステップで右側に必ず $T_i$ が存在し、1 回の入れ替えで位置 $i$ を確定できる。これを最後まで繰り返せば $S=T$ が得られる。操作回数は不一致箇所ごとに高々 1 回なので 高々 $N$ 回。

計算量

• 全体の計算量が $O(N)$ となり制約下で十分高速に動作します。

実装例は以下のようになります。

余談

問題名(lyrics-lesson) の由来について解説します。
この問題の元ネタはアーケード版アイドルマスター内の、「歌詞レッスン」というミニゲームです。 現在でも稼働しているゲームセンターもありますので、興味の沸いた方は是非遊んでみてください。(設置店舗)