Edited at

atcoder ABC110 C問題

今回は方針は立ちやすかったが、中々色々なパターンが存在し、全てに対応できる解法を思いつくのが難しかった。

https://atcoder.jp/contests/abc110/tasks/abc110_c


方針

文字列S,Tが与えられSの文字の中のある文字c1とc2をスワップしていき、最終的にTになるかという問題。方針としては、S,Tについて左から文字を見ていき、次の2パターンについて考える。

(1)Sのi文字目とTのi文字目が一緒の時

ok

(2)Sのi文字目とTのi文字目が違う時

Tについて、i文字目より後ろの文字を見ていき、Tのi文字目と同じ時、何文字目かを配列などで記録。その後、Sについてi文字目より後ろを見ていき、先ほど記録した文字目では、Sのi文字目と一緒か判定。また、それ以外の文字目では、Sのi文字目と違うかを判定していく。一度判定が終わったら、そのアルファベットは関与しないので消していくことで、TLEを防げる。