fork download
  1. -- ******************************************************************************************
  2. -- * POH6+ (パイザ オンライン ハッカソン) *
  3. -- * 単語リストの単語を用いて作ることができる最長の回文のうち辞書順(昇順)最小の回文を求める *
  4. -- ******************************************************************************************
  5. module Main where
  6.  
  7. main :: IO ()
  8. main = do n <- readLn
  9. wordlist <- getWordList n
  10. printPalindrome (makeMaximumSizeAndMinimumOrderPalindrome (sortSringList wordlist) [] "" [])
  11.  
  12. -- 結果を表示する
  13. printPalindrome :: [String] -> IO ()
  14. printPalindrome [] = putStrLn ""
  15. printPalindrome (wordlist_head:wordlist_tail) = do putStr wordlist_head
  16. printPalindrome wordlist_tail
  17.  
  18. -- リストの先頭の要素を抽出する
  19. headOfList :: [anytype] -> anytype
  20. headOfList (head:tail) = head
  21.  
  22. -- リスト同士を繋ぐ
  23. concatList :: [anytype] -> [anytype] -> [anytype]
  24. concatList [] [] = []
  25. concatList front [] = front
  26. concatList [] end = end
  27. concatList [element] end = element : end
  28. concatList (front_head:front_tail) end = front_head : concatList front_tail end
  29.  
  30. -- 標準入力から単語リストを読み込む
  31. getWordList :: Int -> IO [String]
  32. getWordList 0 = return []
  33. getWordList n = do front <- getLine
  34. end <- getWordList (n - 1)
  35. return (front : end)
  36.  
  37. -- 文字列を反転する
  38. reverseString :: String -> String
  39. reverseString "" = ""
  40. reverseString (str_head:str_tail) = concatList (reverseString str_tail) [str_head]
  41.  
  42. -- 文字列リストの並び順を反転する
  43. reverseStringList :: [String] -> [String]
  44. reverseStringList [] = []
  45. reverseStringList (strlist_head:strlist_tail) = concatList (reverseStringList strlist_tail) [strlist_head]
  46.  
  47. -- 文字列を辞書順(昇順)で比較する
  48. compareString :: String -> String -> Int
  49. compareString "" "" = 0
  50. compareString left "" = 1
  51. compareString "" right = -1
  52. compareString (left_head:left_tail) (right_head:right_tail) = if left_head < right_head
  53. then -1
  54. else if left_head == right_head
  55. then compareString left_tail right_tail
  56. else 1
  57.  
  58. -- ソート用の内部関数。文字列リストからキーワードより辞書順で小さい文字列をリストアップする
  59. underPartition :: String -> [String] -> [String]
  60. underPartition keyword [] = []
  61. underPartition keyword (wordlist_head:wordlist_tail) = if compareString keyword wordlist_head > 0
  62. then wordlist_head : (underPartition keyword wordlist_tail)
  63. else underPartition keyword wordlist_tail
  64.  
  65. -- ソート用の内部関数。文字列リストからキーワードと一致する文字列をリストアップする
  66. sameWordPartition :: String -> [String] -> [String]
  67. sameWordPartition keyword [] = []
  68. sameWordPartition keyword (wordlist_head:wordlist_tail) = if compareString keyword wordlist_head == 0
  69. then wordlist_head : (sameWordPartition keyword wordlist_tail)
  70. else sameWordPartition keyword wordlist_tail
  71.  
  72. -- ソート用の内部関数。文字列リストからキーワードより辞書順で大きい文字列をリストアップする
  73. upperPartition :: String -> [String] -> [String]
  74. upperPartition keyword [] = []
  75. upperPartition keyword (wordlist_head:wordlist_tail) = if compareString keyword wordlist_head < 0
  76. then wordlist_head : (upperPartition keyword wordlist_tail)
  77. else upperPartition keyword wordlist_tail
  78.  
  79. -- 文字列リストの先頭の文字列を抽出する
  80. headOfStringList :: [String] -> String
  81. headOfStringList [] = ""
  82. headOfStringList (strlist_head:strlist_tail) = strlist_head
  83.  
  84. -- 文字列リスト内の文字列を辞書順(昇順)でソートする
  85. sortSringList :: [String] -> [String]
  86. sortSringList [] = []
  87. sortSringList (strlist_head:strlist_tail) = concatList (concatList (concatList (sortSringList (underPartition strlist_head strlist_tail)) [strlist_head]) (sortSringList (sameWordPartition strlist_head strlist_tail))) (sortSringList (upperPartition strlist_head strlist_tail))
  88.  
  89. -- 文字列リスト内にキーワードが存在するか判定する
  90. findKeywordInWordList :: String -> [String] -> Bool
  91. findKeywordInWordList keyword [] = False
  92. findKeywordInWordList keyword (wordlist_head:wordlist_tail) = if compareString keyword wordlist_head == 0 then True else findKeywordInWordList keyword wordlist_tail
  93.  
  94. -- 文字列リスト内にキーワードが存在する場合に文字列リストで始めに出てきたキーワードを取り除いた文字列リストを作る
  95. deleteKeywordInWordList :: String -> [String] -> [String]
  96. deleteKeywordInWordList keyword [] = []
  97. deleteKeywordInWordList keyword (wordlist_head:wordlist_tail) = if compareString keyword wordlist_head == 0 then wordlist_tail else wordlist_head : deleteKeywordInWordList keyword wordlist_tail
  98.  
  99. -- POH6+の問題を解くための関数。ソートされた単語リストから最長回文のうち辞書順昇順で最小のものを生成する。
  100. -- 引数の初期値には、第一引数にはソートされた単語リスト。第二~第四引数はには空リストを指定すること。
  101. -- 第二引数には回文の前部に並ぶ単語が逆順でリストアップされる。
  102. -- 第三引数には回文の中央部に位置する単語が格納される。
  103. -- 第四引数には回文の後部に並ぶ単語がリストアップされる。
  104. -- 戻り値は最長回文で辞書順(昇順)最小になるように並べられた単語のリストである。
  105. makeMaximumSizeAndMinimumOrderPalindrome :: [String] -> [String] -> String -> [String] -> [String]
  106. makeMaximumSizeAndMinimumOrderPalindrome [] front center end = concatList (concatList (reverseStringList front) [center]) end
  107. makeMaximumSizeAndMinimumOrderPalindrome (wordlist_head:wordlist_tail) front center end = if findKeywordInWordList (reverseString wordlist_head) wordlist_tail
  108. then makeMaximumSizeAndMinimumOrderPalindrome (deleteKeywordInWordList (reverseString wordlist_head) wordlist_tail) (wordlist_head : front) center ((reverseString wordlist_head) : end)
  109. else if compareString wordlist_head (reverseString wordlist_head) == 0 && (compareString "" center == 0 || compareString wordlist_head center < 0)
  110. then makeMaximumSizeAndMinimumOrderPalindrome wordlist_tail front wordlist_head end
  111. else makeMaximumSizeAndMinimumOrderPalindrome wordlist_tail front center end
  112.  
  113. -- End Of File --
Success #stdin #stdout 0s 4724KB
stdin
6
fdk
jnv
vnj
kdf
qaq
bhh
stdout
fdkjnvqaqvnjkdf