概要
POH6は易化していたが、ここからが本当の地獄だ……。
もっとも、POH5+に比べればまだ簡単だと思う。あっちは15パズル解かせるとかいうガチ問題だったから最初から投げてたからね……。
ただ、あちこちに罠を巡らせた素敵仕様なので、何も考えず解こうとするとコーナーケースにひっかかるのは間違いない。よって、ネタバレとなりうる詳細な解説は次回に移して、今回はポイントだけ解説する。
※2015/09/04：重大なミスが見つかりましたので修正しました。
ポイント
端的に言えば、問題文をよく読むことが重要である。
と言うと、そんなの簡単だろ、と思うかもしれないが冗談じゃない。プログラミングコンテストにおいて文章をよく読むのは重要なことである。その主な目的は思い込みをなくすことだ。
例えば、今回の問題は、文章にするとこんな感じになる。
問題
N個の単語のリストw_1～w_Nが与えられる。
単語は英小文字のみからなる文字列である。
この際、リストから作られる最長の回文で辞書順最小のものを一行に出力せよ。
最後は改行し、余計な文字、空行を含んではならない。
ただし、1 ≦ N ≦ 1000・1 ≦ |w_i| ≦ 10であり、すべての単語は同じ長さである。
何気ないようだが、既に幾つもの罠が動き出している。 その力の源はタワーだ
- 単語長は全て同じなので、回文を生成しやすい(いちいち探索せずとも生成できる)
- リスト中に単語が重複していることもありうる
- 「最長」でかつ「辞書順最小」でなければならない(両方満たす必要がある)
つまり、サンプルで与えられた2つの入出力例に加え、次の例について正答しなければならない。
・入力例3(対称な単語が存在しない場合)
5
tcp
udp
ppm
aac
pct
・出力例3
pcttcp
・入力例4(対称な単語しか存在しない場合)
5
pnp
sos
aaa
www
tst
・出力例4
aaa
・入力例5(対称な単語が重複している場合1)
5
aaa
aaa
vvv
aaa
aaa
・出力例5
aaaaaaaaaaaaではなくaaaaaavvvaaaaaa
・入力例6(対称な単語が重複している場合2)
5
vvv
vvv
aaa
aaa
vvv
・出力例6
vvvvvvvvvではなくaaavvvvvvvvvaaa
・入力例7(巨大なデータ相手の場合)
1000
(以下、「abbbbbbbbb」が500個、「bbbbbbbbba」が500個並んでいる)
・出力例7
abbbbbbbbb(中略)abbbbbbbbbbbbbbbbbba(中略)bbbbbbbbba
・入力例8(ごちゃごちゃしている場合)
10
ac
bc
cc
aa
ca
cb
cb
ac
ca
cc
・出力例8
acacbccccccbcacaではなくacacbcccaacccbcaca
まとめ
通らないテストケースがあったらプログラムを見直してみよう！