Haskell: codefes 2017 qualC

D 問題が解けなかったのはまずい。何故か AtCoder だと DP じゃない気がしてくるんだよね…。

A 問題

point-free style、関数の本質を捉えてる感があって良い。

import Data.List
 
main :: IO ()
main = getLine >>= putStrLn . yesno . isInfixOf "AC"
 
yesno :: Bool -> String
yesno True = "Yes"
yesno False = "No"

B 問題

数式を書いただけ。

main :: IO ()
main = getLine >> getLine >>= print . solve . map read . words
 
solve :: [Int] -> Int
solve a = let n = length a; e = length . filter even $ a
          in 3 ^ n - 2 ^ e

C 問題

標準で Data.Sequence.Seq という deque の機能を持ったデータ構造が用意されているのでこれを使うと良い。失敗したら-∞を返そうかと思ったけど、Maybe モナドでやるのがお洒落な気がしたのでそうした。

solve を 2 つに分離させたんだけど、分離する必要はないらしい。そもそも何で分離させたのかというと、長さ 1 以下の Seq が来た時 viewl/viewr が評価されてエラーになると思ったからなんだけど、遅延評価されるから(多分?)気にしなくてよかったらしい。strict に慣れすぎてて lazy で起こる事柄は難しく感じる。

import Control.Applicative
import Data.Maybe
import qualified Data.Sequence as S
import Data.Sequence (Seq, fromList, (<|), (|>), viewl, viewr, ViewL(..), ViewR(..))
 
main = getLine >>= print . fromMaybe (-1) . solve . fromList
 
solve :: Seq Char -> Maybe Int
solve q | S.length q <= 1 = Just 0
solve q
  | l == r    = solve ms
  | l == 'x'  = succ <$> solve (q |> 'x')
  | r == 'x'  = succ <$> solve ('x' <| q)
  | otherwise = Nothing
  where
    (l :< rs) = viewl q
    (ms :> r) = viewr rs

まとめ

最近 Haskellアルゴリズムを構築するのにハマっている。アルゴリズム系は
Haskell で書くと結構きついんだけど(速度とかの最適化の面で)、使い捨てプログラムとかは python とかで書くより Haskell で書いた方が楽な気がする。