# Typical DP Contest

## Submission #5417737

### Source codeソースコード

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

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

main = do
_ <- getLine
as <- map read . words <\$> getLine
bs <- map read . words <\$> getLine
print \$ evalDP run Map.empty\$ (Sunuke, (as, bs))

run :: DP Game Point
run = dp \$ \g@(trn, stc) -> do
memo <- get
let moves = getMoves stc
if isEmpty stc
then return 0
else if trn == Sunuke
then return \$ maximum [p'+ evalDP run memo (Sumeke, s') | (s', p') <- moves]
else return \$ minimum [0 + evalDP run memo (Sunuke, s') | (s', p') <- moves]

isEmpty :: Stack -> Bool
isEmpty (as, bs) = null as && null bs

getMoves :: Stack -> [(Stack, Point)]
getMoves ([]  , []  ) = []
getMoves (a:as, []  ) = [((as, []), a)]
getMoves ([]  , b:bs) = [(([], bs), b)]
getMoves (a:as, b:bs) = [((as, b:bs), a), ((a:as, bs), b)]

-- DP
type Memo a b = Map.Map a b
type DP a b = a -> State (Memo a b) b

dp :: Ord a => DP a b -> DP a b
dp f x = do
memo <- gets (Map.lookup x)
case memo of
Just y  -> return y
Nothing -> do
y <- f x
modify (Map.insert x y)
return y

evalDP :: DP a b -> Memo a b -> a -> b
evalDP f m x = evalState (f x) m

evalDPAll :: DP a b -> [a] -> [b]
evalDPAll f xs = evalState (sequence (map f xs)) Map.empty

-- 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 - ゲーム yk 2019/05/16 10:48:46 +0000 Haskell (GHC 7.10.3) TLE 0 2376 Byte ms -

### 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 AC 47 ms 1020 KB 01 TLE 02 TLE 90 AC 1 ms 508 KB 91 AC 2 ms 764 KB