ABC-110:C
問題
提出したやつ
紙
自分の思考
- アルファベット毎の出現回数をS,Tそれぞれintで取りArrays.sort()して同じだと正しそうな気がする。
- テストケースが通るから提出
問題点
- 提出時点で正しい理由が分かっていないのでWAの可能性がある。
正しい理由
editorial.pdfにあるように置換表を求める必要がある。
上記の例で言うとただintをソートしたと考えるのではなく(a,1),(b,0),(c,0)...を後ろの数字でソートしたと考えて、ソート後にできたS,Tそれぞれの(b,0),(c,0)...(z,2)の前のアルファベットの並びが置換表になっている。
他の上位提出者との比較
一人同じ解法してた。
他にあったのはmap<char,char>を二つ作って直接置換表を作っていく方法。
mapが2つある意味が最初は良く分からなかったけど1つだと1対多の関係を許してしまうんだと思うのでTに同じ文字が2個あるとバグる(テストケース2)。
あとあったのが
- Sの1文字目のアルファベットをA,2文字目以降で初めてAでない文字をB...のように置換する。
- Tも同様
- S.equals(T)ならYes、でないならNo
これはSをs0..s0s1..s1s2...s2...だと考えてs0->A,s1->B,s2->Cという置換表をつくっているのと同様でTについても置換表を作ってそれを比較している(はず)。