AtCoder Regular Contest 003

B - さかさま辞書


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 64MB

問題文

高橋君は友達とチャットで逆さしりとりをすることにしました。
逆さしりとりとは、前の人が言った単語の頭文字で終わる単語を答えるしりとりです。
しかし、高橋君は英単語に自信がないのでこっそり「さかさま辞書」を使うことにしました。

普通の辞書は単語の先頭の文字がABC順になるように並べられており、同じ文字同士の場合はその次の文字がABC順になるように並べられます。
先頭から見ていく普通の辞書順に対して、「さかさま辞書」は後ろの文字から見ていきます。
例えば apple, bee, card は、普通の辞書なら apple → bee → card の順になります。
しかし、「さかさま辞書」では d で終わる card1 番、apple とbee は同じ e で終わるのでその 1 つ前が e である bee2 番、l であるapple3 番の順になります。
図(a):普通の辞書順に並べた例  図(b):さかさま辞書順に並べた例

高橋君の代わりに「さかさま辞書」を作成し、与えられた単語を「さかさま辞書」順に並べてください。

入力

入力は以下の形式で標準入力から与えられる。
N
s_{1}
s_{2}
:
:
s_{N}
  • 1 行目は、並べる単語数を表す整数 N (1 ≦ N ≦ 100) が与えられる。
  • 2 行目から N 行は、並べる単語を表す文字列が 1 行に 1 つずつ与えられる。
  • i+1 行目の文字列 s_i の長さは 1 文字以上 20 文字以下で、含まれる文字はアルファベットの小文字のみ(a-z)です。
  • なお、重複する単語が与えられることはありません。

出力

入力として与えられた単語を、さかさま辞書順に標準出力に 1 行ずつ出力せよ。
なお、最後には改行を出力せよ。

入力例 1

5
chokudai
kensho
imos
yuichirw
ao

出力例 1

chokudai
ao
kensho
imos
yuichirw
  • まず、それぞれの一番後ろの文字は、chokudai、kensho、imos、yuichirw、aoなのでABC順に並べると、i,o,s,wの順になります。
  • しかしkenshoとao2 人が同じ o なので、この 2 人に関してはその 1 つ前の文字の順で並べます。
  • kenshoの後ろから 2 つ目の文字は h、ao の後ろから 2 つ目の文字は a なので、ao, kensho の順になります。
  • よって、chokudai, ao, kensho, imos, yuichirw の順が答えになります。

入力例 2

2
dart
art

出力例 2

art
dart
  • 後ろから 1,2,3 番目とも同じ文字なので、後ろから 4 番目の文字を比較します。
  • しかし、art の後ろから 4 番目の文字はありません。
  • 無い場合は、a よりも早いので、art, dart の順になります。

Source name

ARC 003

Submit提出する