Typical DP Contest

Submission #5411082

Source codeソースコード

import qualified Control.Monad as M
import qualified Data.List as L
import Data.Maybe (fromJust)

data Turn = Sunuke | Sumeke deriving (Show, Eq)
type Point = Int
type Stack = ([Int], [Int])
type Game = State (Turn, Stack, Point) Point

main = do
    _ <- getLine
    as <- map read . words <$> getLine
    bs <- map read . words <$> getLine
    print $ evalState run (Sunuke, (rSort as, rSort bs), 0)

rSort = L.sortBy (flip compare)

run :: Game
run = do
    (trn, stc, p) <- get
    let (stc', p') = pop stc
    if p' == Nothing
        then return $ p
        else if trn == Sunuke
            then return $ evalState run (Sumeke, stc', p + fromJust p')
            else return $ evalState run (Sunuke, stc', p)

pop :: Stack -> (Stack, Maybe Point)
pop ([]  , []  ) = (([], []), Nothing)
pop (a:as, []  ) = (([], []), Just a)
pop ([]  , b:bs) = (([], []), Just b)
pop (a:as, b:bs) = if a > b
    then ((as, b:bs), Just a)
    else ((a:as, bs), Just b)


-- State.hs

newtype State s x = State { runState :: s -> (x, s) }

instance Functor (State s) where
    fmap = M.liftM

instance Applicative (State s) where
    pure x = State $ \s -> (x, s)
    (<*>) = M.ap

instance Monad (State s) where
    m >>= k = State $ \s ->
        let (x, s0) = runState m s
        in runState (k x) s0

get :: (State s) s
get = State $ \s -> (s, s)

put :: s -> (State s) ()
put s = State $ \_ -> ((), s)

state :: (s -> (a, s)) -> (State s) a
state f = do
    s <- get
    let (a, s') = f s
    put s'
    return a

modify :: (s -> s) -> (State s) ()
modify f = get >>= put . f

gets :: (s -> a) -> (State s) a
gets f = get >>= return . f

evalState :: State s x -> s -> x
evalState = (fst .) . runState

execState :: State s x -> s -> s
execState = (snd .) . runState

Submission

Task問題 B - ゲーム
User nameユーザ名 yk
Created time投稿日時
Language言語 Haskell (GHC 7.10.3)
Status状態 WA
Score得点 0
Source lengthソースコード長 1836 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
All 0 / 3 00,01,02,90,91

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00 WA
01 WA
02 WA
90 AC 1 ms 508 KB
91 WA