AtCoder Beginner Contest (ABC) 219 PythonでC問題解いてみた 解説あり

前回の続きです。

前回

mery-kirokudayo.hateblo.jp

こんにちは。メリーです。

今回は前回のABC219の続きです。

ようやく実家から一人暮らしの家に戻ってこれたので、まともなPCでブログ更新ができるようになりました。
（今までは６年前くらいに買ったノーパソ。Youtubeと雀魂の２窓したらカクつくレベル。）

これでApexもできるよ！やったね！！って思いながら起動したらサーバーが壊れているじゃないですか・・・・。まともにゲームができないなんて・・・。まぁ、今日の夜中に直るらしいですけど。

コンテストをやっていて思ったのですが、A,B問題はほぼほぼ完全にできるので、次回から過去問はC問題埋めをメインでやっていきます。

といわけでAtCoder Beginner Contest (ABC) 219のC問題を解いていきます。
言語はPython、提出はPyPyです。

目次

C問題　

問題文

C - Neo-lexicographic Ordering

全探索するとTLEになりそうな未来しか見えない。

新しい辞書順が与えられて、その辞書順通りに文字列を並び替える問題。
コンテスト中はこの問題無理だったな・・・。

比較のシステムをずっと考えてた・・・。
いろいろ解説をみた結果、
「もともと実装されているsortを使うのが楽そう」
という結論に。

というわけで方針を。
1. 元の辞書順を用意(abcd・・・・)
2. 文字列S_iの各文字をabc順に変換する
3. 文字列S_iをabc順に変換したら、文字列S_iのリストに入れる
4. ソートする
5. 出力する

という流れで行けました。

ただ、Pythonだと、TLEになるので、PyPyで提出しましょう。

というわけで実装。

x = list(input())
n = int(input())
s = []*n
for i in range(n):
    s.append(input())
y = "abcdefghijklmnopqrstuvwxyz"

# s[i]に元の辞書順に戻した物を追加する。
for i in range(n):
    t = []  
    for j in range(len(s[i])):  
        for k in range(len(x)):
            if s[i][j] == x[k]:
                ans = y[k]
                t.append(ans)
    s[i] = [t,s[i]]
s.sort()

for i in range(n):
    print(s[i][1])

コードの解説です。

y にもとの辞書順（abcd~~~）を格納してます。

そして、すべての文字列S_iの文字をもとの辞書順の文字に変換します。
※入力例1の場合、文字列のbをaに、aをbに、というように。

その部分のコードが以下のコード。

for i in range(n):
    t = []  
    for j in range(len(s[i])):  
        for k in range(len(x)):
            if s[i][j] == x[k]:
                ans = y[k]
                t.append(ans)

このコードで、文字列S_iを元の辞書順に変換したものが文字列tです。

そして、

s[i] = [t,s[i]]

で、配列の先頭にtを追加します。
※ここで、先頭に追加しないと、ソートの時にs[i]が参照されるので、うまくソートできません。

s.sort()

で、各文字列S[i]が文字列tを参照にしてソートされます。

for i in range(n):
    print(s[i][1])

そして最後に順番に沿って最初に入力された文字列S_iを出力していけば完成です。

このコードでは、

S = [[t(0),s(0)],[t(1),s(1)],[t(2),s(2)]]

のような配列になっているので、注意です。

以上で完成です。

次回からも元気に更新していく予定です。

それでは。