提出 #56281873


ソースコード 拡げる

import Control.Monad
import Control.Monad.ST
import Control.Monad.Primitive
import Data.Maybe
import qualified Data.ByteString.Char8 as BS
import Data.List
import Data.Char
import Data.Ord
import Data.Ix
import Data.Bool
import Data.Vector.Unboxed.Base
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import qualified Data.Vector as V
import qualified Data.Vector.Mutable as VM
import Data.Array
import Data.Array.ST
import qualified Data.Sequence as Seq
import qualified Data.Set as Set 
import qualified Data.IntMap as IM
import Data.Graph.Inductive

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine

main = do
    n <- getInt
    s <- getLine
    let abcs = listArray (1, n) $ map f s
            where f 'R' = 'A'
                  f 'P' = 'B'
                  f 'S' = 'C'
    let bnd = ((0, 'A'), (n, 'C')) :: ((Int, Char), (Int, Char))
        zero = minBound :: Int
        starts = [(n, 'A'), (n, 'B'), (n, 'C')] :: [(Int, Char)]
        v0s = [((0, 'A'), 0), ((0, 'B'), 0), ((0, 'C'), 0)] :: [((Int, Char), Int)]
        op1 = max :: Int -> Int -> Int
        op2 = (+) :: Int -> Int -> Int
        subproblems :: (Int, Char) -> [((Int, Char), Int)]
        subproblems (p, c) | c == 'A' && jan 'A' (abcs ! p) == 1 = [((p-1, 'B'), 1), ((p-1, 'C'), 1)]
                           | c == 'A' && jan 'A' (abcs ! p) == 0 = [((p-1, 'B'), 0), ((p-1, 'C'), 0)]
                           | c == 'B' && jan 'B' (abcs ! p) == 1 = [((p-1, 'C'), 1), ((p-1, 'A'), 1)]
                           | c == 'B' && jan 'B' (abcs ! p) == 0 = [((p-1, 'C'), 0), ((p-1, 'A'), 0)]
                           | c == 'C' && jan 'C' (abcs ! p) == 1 = [((p-1, 'A'), 1), ((p-1, 'B'), 1)]
                           | c == 'C' && jan 'C' (abcs ! p) == 0 = [((p-1, 'A'), 0), ((p-1, 'B'), 0)]
                           | otherwise = []
                          where jan 'A' 'C' = 1
                                jan 'B' 'A' = 1
                                jan 'C' 'B' = 1
                                jan a b | a == b = 0
                                        | otherwise = (-1)
    let dparray = dpsolve bnd zero starts v0s op1 op2 subproblems
    print . maximum $ map (dparray !) starts

dpsolve :: forall i e . (Ix i, Eq e) => 
            (i, i)                -- DPテーブルの始点、終点
             -> e                 -- DPテーブルの初期値(op1の零点)
             -> [i]               -- DPの開始の点のリスト
             -> [(i, e)]          -- DPテーブルの停止点(自明な点)
             -> (e -> e -> e)     -- op1 候補の統合演算
             -> (e -> e -> e)     -- op2 候補の算出演算
             -> (i -> [(i, e)])   -- 現在のindexから(小問題のindex,算出に使う値)のリスト
             -> Array i e
dpsolve bnd zero starts v0s op1 op2 subproblems = runSTArray $ do
    memo <- thaw $ accumArray op1 zero bnd v0s :: ST s (STArray s i e)
    forM_ starts $ \start -> go start memo
    return memo
        where
            go p memo = do
                    res <- readArray memo p
                    if res /= zero then return res
                    else do
                        ret <- foldM (\acc (sp, s) -> do
                                         spans <- go sp memo
                                         return $ acc `op1` (s `op2` spans))
                                         zero (subproblems p)
                        writeArray memo p ret
                        return ret

提出情報

提出日時
問題 D - AtCoder Janken 3
ユーザ pel
言語 Haskell (GHC 9.4.5)
得点 400
コード長 3711 Byte
結果 AC
実行時間 112 ms
メモリ 69780 KiB

コンパイルエラー

app/Main.hs:3:1: warning: [-Wunused-imports]
    The import of ‘Control.Monad.Primitive’ is redundant
      except perhaps to import instances from ‘Control.Monad.Primitive’
    To import instances alone, use: import Control.Monad.Primitive()
  |
3 | import Control.Monad.Primitive
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

app/Main.hs:6:1: warning: [-Wunused-imports]
    The import of ‘Data.List’ is redundant
      except perhaps to import instances from ‘Data.List’
    To import instances alone, use: import Data.List()
  |
6 | import Data.List
  | ^^^^^^^^^^^^^^^^

app/Main.hs:7:1: warning: [-Wunused-imports]
    The import of ‘Data.Char’ is redundant
      except perhaps to import instances from ‘Data.Char’
    To import instances alone, use: import Data.Char()
  |
7 | import Data.Char
  | ^^^^^^^^^^^^^^^^

app/Main.hs:8:1: warning: [-Wunused-imports]
    The import of ‘Data.Ord’ is redundant
      except perhaps to import instances from ‘Data.Ord’
    To import instances alone, use: import Data.Ord()
  |
8 | import Data.Ord
  | ^^^^^^^^^^^^^^^

app/Main.hs:10:1: warning: [-Wunused-imports]
    The import of ‘Data.Bool’ is redundant
      except perhaps to import instances from ‘Data.Bool’
    To import instances alone, use: import Data.Bool()
   |
10 | import Data.Bool
   | ^^^^^^^^^^^^^^^^

app/Main.hs:11:1: warning: [-Wunused-imports]
    The import of ‘Data.Vector.Unboxed.Base’ is redundant
      except perhaps to import instances from ‘Data.Vector.Unboxed.Base’
    To import instances alone, use: import Data.Vector.Unboxed.Base()
   |
11 | import Data.Vector.Unboxed.Base
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

app/Main.hs:12:1: warning: [-Wunused-imports]
    The qualified import of ‘Data.Vector.Unboxed’ is redundant
      except perhaps to import instances from ‘Data.Vector.Unboxed’
    To import instances alone, use: import Data.Vector.Unboxed()
   |
12 | import qualified Data.Vector.Unboxed as VU
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

app/Main.hs:13:1: warning: [-Wunused-imports]
    The qualified import of ‘Data.Vector.Unboxed.Mutable’ is redundant
      except perhaps to import instances from ‘Data.Vector.Unboxed.Mutable’
    To import instances alone, use: import Data.Vector.Unboxed.Mutable()
   |
13 | import qualified Data.Vector.Unboxed.Mutable as VUM
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

app/Main.hs:14:1: warning: [-Wunused-imports]
    The qualified import of ‘Data.Vector’ is redundant
      except perhaps to import instances from ‘Data.Vector’
    To import instances alone, use: import Data.Vector()
   |
14 | import qualified Data.Vector as V
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

app/Main.hs:15:1: warning: [-Wunused-imports]
    The qualified import of ‘Data.Vector.Mutable’ is redundant
      except perhaps to import instances from ‘Data.Vector.Mutable’
    To import instances alone, use: import Data.Vector.Mutable()
   |
15 | import qualified Data.Vector.Mutable as VM
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

app/Main.hs:18:1: warning: [-Wunused-imports]
    The qualified import of ‘Data.Sequence’ is redundant
      except perhaps to import instances from ‘Data.Sequence’
    To import instances alone, use: import Data.Sequence()
   |
18 | import qualified Data.Sequence as Seq
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

app/Main.hs:19:1: warning: [-Wunused-imports]
    The qualified import of ‘Data.Set’ is redundant
      except perhaps to import instances from ‘Data.Set’
    To import instances alone, use: import Data.Set()
   |
19 | import qualified Data.Set as Set 
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

app/Main.hs:20:1: warning: [-Wunused-imports]
    The qualified import of ‘Data.IntMap’ is redundant
      except perhaps to import instances from ‘Data.IntMap’
    To import instances alone, use: import Data.IntMap()
   |
20 | import qualified Data.IntMap as IM
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

app/Main.hs:21:1: warning: [-Wunused-imports]
    The import of ‘Data.Graph.Inductive’ is redundant
      except perhaps to import instances from ‘Data.Graph.Inductive’
    To import instances alone, use: import Data.Graph.Inductive()
   |
21 | import Data.Graph.Inductive
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^

app/Main.hs:23:1: warning: [-Wmissing-signatures]
    Top-level binding with no type signature:
      readInt :: BS.ByteString -> Int
   |
23 | readInt = fst . fromJust . BS.readInt
   | ^^^^^^^

app/Main.hs:24:1: warning: [-Wmissing-signatures]
    Top-level binding with no type signature:
      readIntList :: BS.ByteString -> [Int]
   |
24 | readIntList = map readInt . BS.words
   | ^^^^^^^^^^^

app/Main.hs:24:1: warning: [-Wunused-top-binds]
    Defined but not used: ‘readIntList’
   |
24 | readIntList = map readInt . BS.words
   | ^^^^^^^^^^^

app/Main.hs:25:1: warning: [-Wmissing-signatures]
    Top-level binding with no type signature: getInt :: IO Int
   |
25 | getInt = readInt <$> BS.getLine
   | ^^^^^^

app/Main.hs:26:1: warning: [-Wmissing-signatures]
    Top-level binding with no type signature: getIntList :: IO [Int]
   |
26 | getIntList = readIntList <$> BS.getLine
   | ^^^^^^^^^^

app/Main.hs:26:1: warning: [-Wunused-top-binds]
    Defined but not used: ‘getIntList’
   |
26 | getIntList = readIntList <$> BS.getLine
   | ^^^^^^^^^^

app/Main.hs:28:1: warning: [-Wmissing-signatures]
    Top-level binding with no type signature: main :: IO ()
   |
28 | main = do
   | ^^^^

app/Main.hs:32:19: warning: [-Wincomplete-patterns]
    Pattern match(es) are non-exhaustive
    In an equation for ‘f’:
        Patterns of type ‘Char’ not matched:
            p where p is not one of {'S', 'R', 'P'}
   |
32 |             where f 'R' = 'A'
   |                   ^^^^^^^^^^^...

app/Main.hs:42:61: warning: [-Wtype-defaults]
    • Defaulting the type variable ‘a0’ to type ‘Integer’ in the following constraints
        (Eq a0) arising from a use of ‘==’ at app/Main.hs:42:61-62
        (Num a0) arising from a use of ‘jan’ at app/Main.hs:42:42-44
    • In the second argument of ‘(&&)’, namely
        ‘jan 'A' (abcs ! p) == 1’
      In the expression: c == 'A' && jan 'A' (abcs ! p) == 1
      In a stmt of a pattern guard for
                     an equation for ‘subproblems’:
        c == 'A' && jan 'A' (abcs ! p) == 1
   |
42 |         subproblems (p, c) | c == 'A' && jan 'A' (abcs ! p) == 1 = [((p-1, 'B'), 1), ((p-1, 'C'), 1)]
   |                                                             ^^

app/Main.hs:43:61: warning: [-Wtype-defaults]
    • Defaulting the type variable ‘a0’ to type ‘Integer’ in the following constraints
        (Eq a0) arising from a use of ‘==’ at app/Main.hs:43:61-62
        (Num a0) arising from a use of ‘jan’ at app/Main.hs:43:42-44
    • In the second argument of ‘(&&)’, namely
        ‘jan 'A' (abcs ! p) == 0’
      In the expression: c == 'A' && jan 'A' (abcs ! p) == 0
      In a stmt of a pattern guard for
                     an equation for ‘subproblems’:
        c == 'A' && jan 'A' (abcs ! p) == 0
   |
43 |                            | c == 'A' && jan 'A' (abcs ! p) == 0 = [((p-1, 'B'), 0), ((p-1, 'C'), 0)]
   |                                                             ^^

app/Main.hs:44:61: warning: [-Wtype-defaults]
    • Defaulting the type variable ‘a0’ to type ‘Integer’ in the following constraints
        (Eq a0) arising from a use of ‘==’ at app/Main.hs:44:61-62
        (Num a0) arising from a use of ‘jan’ at app/Main.hs:44:42-44
    • In the second argument of ‘(&&)’, namely
        ‘jan 'B' (abcs ! p) == 1’
      In the expression: c == 'B' && jan 'B' (abcs ! p) == 1
      In a stmt of a pattern guard for
                     an equation for ‘subproblems’:
        c == 'B' && jan 'B' (abcs ! p) == 1
   |
44 |                            | c == 'B' && jan 'B' (abcs ! p) == 1 = [((p-1, 'C'), 1), ((p-1, 'A'), 1)]
   |                                                             ^^

app/Main.hs:45:61: warning: [-Wtype-defaults]
    • Defaulting the type variable ‘a0’ to type ‘Integer’ in the following constraints
        (Eq a0) arising from a use of ‘==’ at app/Main.hs:45:61-62
        (Num a0) arising from a use of ‘jan’ at app/Main.hs:45:42-44
    • In the second argument of ‘(&&)’, namely
        ‘jan 'B' (abcs ! p) == 0’
      In the expression: c == 'B' && jan 'B' (abcs ! p) == 0
      In a stmt of a pattern guard for
                     an equation for ‘subproblems’:
        c == 'B' && jan 'B' (abcs ! p) == 0
   |
45 |                            | c == 'B' && jan 'B' (abcs ! p) == 0 = [((p-1, 'C'), 0), ((p-1, 'A'), 0)]
   |                                                             ^^

app/Main.hs:46:61: warning: [-Wtype-defaults]
    • Defaulting the type variable ‘a0’ to type ‘Integer’ in the following constraints
        (Eq a0) arising from a use of ‘==’ at app/Main.hs:46:61-62
        (Num a0) arising from a use of ‘jan’ at app/Main.hs:46:42-44
    • In the second argument of ‘(&&)’, namely
        ‘jan 'C' (abcs ! p) == 1’
      In the expression: c == 'C' && jan 'C' (abcs ! p) == 1
      In a stmt of a pattern guard for
                     an equation for ‘subproblems’:
        c == 'C' && jan 'C' (abcs ! p) == 1
   |
46 |                            | c == 'C' && jan 'C' (abcs ! p) == 1 = [((p-1, 'A'), 1), ((p-1, 'B'), 1)]
   |                                                             ^^

app/Main.hs:47:61: warning: [-Wtype-defaults]
    • Defaulting the type variable ‘a0’ to type ‘Integer’ in the following constraints
        (Eq a0) arising from a use of ‘==’ at app/Main.hs:47:61-62
        (Num a0) arising from a use of ‘jan’ at app/Main.hs:47:42-44
    • In the second argument of ‘(&&)’, namely
        ‘jan 'C' (abcs ! p) == 0’
      In the expression: c == 'C' && jan 'C' (abcs ! p) == 0
      In a stmt of a pattern guard for
                     an equation for ‘subproblems’:
        c == 'C' && jan 'C' (abcs ! p) == 0
   |
47 |                            | c == 'C' && jan 'C' (abcs ! p) == 0 = [((p-1, 'A'), 0), ((p-1, 'B'), 0)]
   |                                                             ^^

app/Main.hs:75:45: warning: [-Wname-shadowing]
    This binding for ‘sp’ shadows the existing binding
      imported from ‘Data.Graph.Inductive’ at app/Main.hs:21:1-27
      (and originally defined in ‘Data.Graph.Inductive.Query.SP’)
   |
75 |                         ret <- foldM (\acc (sp, s) -> do
   |                                             ^^

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 400 / 400
結果
AC × 3
AC × 32
セット名 テストケース
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 01_random_16.txt, 01_random_17.txt, 01_random_18.txt, 01_random_19.txt, 01_random_20.txt, 01_random_21.txt, 01_random_22.txt, 02_handmade_23.txt, 02_handmade_24.txt, 02_handmade_25.txt, 02_handmade_26.txt, 02_handmade_27.txt, 02_handmade_28.txt, 02_handmade_29.txt, 02_handmade_30.txt, 02_handmade_31.txt
ケース名 結果 実行時間 メモリ
00_sample_00.txt AC 1 ms 6764 KiB
00_sample_01.txt AC 1 ms 6692 KiB
00_sample_02.txt AC 1 ms 6796 KiB
01_random_03.txt AC 81 ms 40976 KiB
01_random_04.txt AC 81 ms 41020 KiB
01_random_05.txt AC 112 ms 55176 KiB
01_random_06.txt AC 81 ms 41024 KiB
01_random_07.txt AC 81 ms 41020 KiB
01_random_08.txt AC 112 ms 55388 KiB
01_random_09.txt AC 112 ms 55300 KiB
01_random_10.txt AC 71 ms 41160 KiB
01_random_11.txt AC 81 ms 41108 KiB
01_random_12.txt AC 81 ms 41044 KiB
01_random_13.txt AC 81 ms 40972 KiB
01_random_14.txt AC 71 ms 41192 KiB
01_random_15.txt AC 71 ms 40788 KiB
01_random_16.txt AC 21 ms 17708 KiB
01_random_17.txt AC 51 ms 31160 KiB
01_random_18.txt AC 61 ms 35548 KiB
01_random_19.txt AC 61 ms 36292 KiB
01_random_20.txt AC 81 ms 40844 KiB
01_random_21.txt AC 21 ms 21476 KiB
01_random_22.txt AC 71 ms 38848 KiB
02_handmade_23.txt AC 1 ms 6752 KiB
02_handmade_24.txt AC 1 ms 6756 KiB
02_handmade_25.txt AC 1 ms 6684 KiB
02_handmade_26.txt AC 82 ms 45140 KiB
02_handmade_27.txt AC 103 ms 69780 KiB
02_handmade_28.txt AC 82 ms 45064 KiB
02_handmade_29.txt AC 82 ms 52404 KiB
02_handmade_30.txt AC 82 ms 52304 KiB
02_handmade_31.txt AC 82 ms 45148 KiB