ページ

2012/06/12

[競技プログラミング][C言語][AtCoder]さかさま辞書

B - さかさま辞書

時間制限 : 2sec / スタック制限 : 10MB / メモリ制限 : 64MB

問題文

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

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

図(a):普通の辞書順に並べた例  図(b):さかさま辞書順に並べた例

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

入力

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

出力

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

出典

B: さかさま辞書 - AtCoder Regular Contest #003 | AtCoder

回答

AtCoder/arc003_2.cpp at master · wada811/AtCoder
配列の中身の文字列を逆順にしてソートしてもう一回逆順にして戻して表示すればOK。
流石に同じ配列内でやるのは面倒なので反転用の配列を用意した。
PHPを始めたから関数名がPHPっぽくなってる。
main関数だけ見るとロジックだけ書かれてて日が経っても把握しやすくて良いなぁと思った。