https://codeiq.jp/q/2549

Mayoi.hs

import Data.Array

data Dir = ToY | ToZ
  deriving (Eq, Ord, Enum, Ix)

data Node = Y | A | B | C | Z
  deriving (Eq, Ord, Enum, Ix)

data Stat = Stat Int Dir Node
  deriving (Eq, Ord, Ix)

main :: IO ()
main = interact $ show . mayoi . read

mayoi :: Int -> Integer
mayoi x = memoMayoi $ start x
  where
    memoMayoi :: Stat -> Integer
    memoMayoi m@(Stat n _ node)
      | node == Z    = 0
      | node == Y    = 1
      | n > 0        = memo ! m' + memo ! m''
      | otherwise    = memo ! m'
      where
        m'  = step m
        m'' = step $ turn m

    memo :: Array Stat Integer
    memo = listArray ((Stat 0 ToY Y), (Stat x ToZ Z)) $ do
      i    <- [0 .. x]
      dir  <- [ToY, ToZ]
      node <- [Y .. Z]
      return . memoMayoi $ Stat i dir node

start :: Int -> Stat
start n = Stat n ToZ B

turn :: Stat -> Stat
turn (Stat n ToY node) = Stat (n - 1) ToZ node
turn (Stat n ToZ node) = Stat (n - 1) ToY node

step :: Stat -> Stat
step (Stat n ToY node) = Stat n ToY $ pred node
step (Stat n ToZ node) = Stat n ToZ $ succ node