Hatena::Grouptopcoder

TopCoder戦記

研究開発者・ellerのTopCoder挑戦記録。言語は主にJavaを使用しています。ドキュメンテーションコメントはSubmit完了後、ブログ掲載前に補完したものです。

2011-04-14

SRM348 Div2 Easy

| 08:38

Google Code Jam Japan 2011にエントリー→フツーに予選落ちの予感→フツーに参加しても面白くないんじゃね?→そうだHaskellにしよう!

Haskellは私の「今年の言語」なのだが、なかなか使う機会がなかったので言語のキャッチアップを兼ねようという魂胆。ということでしばらくの間、以前Javaで解いた問題をHaskellで解き直してみる。今回はこれ


解法1

文字列置換と再帰を用いた解法。まずソートして"NS"を空文字列に置換、その後headとlastがそれぞれ'E','W'ならばそれを取り除いていく。

ガードを使用しており個人的にはHaskellっぽくない*1印象。replace関数の引数は第1引数にtargetを持ってきたかったのだが、部分適用を用いるために最後に定義することにした。無名関数を使えば第1引数でも大丈夫なんだろうとは思う。

import System
import Data.List
import Text.Regex.Posix

optimize :: String -> String
optimize cs = removeEW . removeNS $ sort cs
  where
    removeEW :: String -> String
    removeEW s
      | hl == "EW" = removeEW $ init $ tail s
      | otherwise  = s
        where hl = [head s, last s]
    removeNS :: String -> String
    removeNS s = replace "NS" "" s

replace :: String -> String -> String -> String
replace pattern new target 
  | match == "" = target
  | otherwise   = head ++ new ++ replace pattern new tail
  where
    (head, match, tail) = target =~ pattern

main = getArgs >>= putStrLn . optimize . concat

解法2

まず'E','N','S','W'それぞれの文字数をカウントして、必要な文だけ文字をreplicateしてやる。++にHaskellっぽくない印象を感じるものの個人の趣味の範囲か。解放1より断然シンプル。

whereに同じコードが4つも出てくるのでまとめてしまいたいが、Haskellでどうやるのかが謎。Javaならfor (char c : "ENSW".toCharArray())とかの採用を検討するところだが。

import System

optimize :: String -> String
optimize cs = 
  replicate (e - w) 'E' ++ replicate (n - s) 'N' ++ 
  replicate (s - n) 'S' ++ replicate (w - e) 'W'
  where
    e = length $ filter (== 'E') cs
    n = length $ filter (== 'N') cs
    s = length $ filter (== 'S') cs
    w = length $ filter (== 'W') cs

main = getArgs >>= putStrLn . optimize . concat

*1:「ただし」とか場合分け定義とかが数式に出てくるのは好きじゃない派、なんか流れがぶった切られる感じ