Contest Duration: - (local time) (100 minutes) Back to Home

Submission #4704760

Source Code Expand

Copy
```import Data.Int
import Data.List
import Data.Array
import Data.Ix (range)

modulo :: Int64
modulo = 10^9 + 7
addMod, subMod, mulMod :: Int64 -> Int64 -> Int64
addMod x y = (x + y) `rem` modulo
subMod x y = (x - y) `mod` modulo
mulMod x y = (x * y) `rem` modulo
sumMod :: [Int64] -> Int64

data Base = A | C | G | T deriving (Eq,Show,Ord,Enum,Ix)

bases :: [Base]
bases = [A,C,G,T]

baseTripleInterval :: ((Base,Base,Base),(Base,Base,Base))
baseTripleInterval = ((A,A,A),(T,T,T))

baseTripleRange :: [(Base,Base,Base)]
baseTripleRange = range baseTripleInterval

sumArr :: Array (Base,Base,Base) Int64 -> Int64
sumArr = sumMod . elems

-- 出力 a:
--   a ! (s,t,u) : 問題文の条件を満たす長さ 3 の文字列のうち、stuから始まるもの
data3 :: Array (Base,Base,Base) Int64
data3 = array baseTripleInterval
[ (i,val)
| i <- baseTripleRange
, let val | i `elem` [(A,G,C),(G,A,C),(A,C,G)] = 0
| otherwise = 1
]

-- sumArr data3 == 61

-- 入力 a:
--   a ! (s,t,u) : 問題文の条件を満たす長さ k の文字列のうち、stuから始まるもの
-- 出力 a':
--   a' ! (s,t,u) : 問題文の条件を満たす長さ k+1 の文字列のうち、stuから始まるもの
step :: Array (Base,Base,Base) Int64 -> Array (Base,Base,Base) Int64
step arr = let n = sumArr arr -- 問題文の条件を満たす長さ k の文字列の個数
in array baseTripleInterval
[ (i,val)
| i@(s,t,u) <- baseTripleRange
, let val | i `elem` [(A,G,C),(G,A,C),(A,C,G)] = 0
-- 4文字のダメなパターンで、3文字パターンを含まないもの：ATGC, AGTC, AGGC
| i == (A,T,G) = sumMod [arr ! (t,u,v) | v <- [A,G,T]]
| i == (A,G,T) = sumMod [arr ! (t,u,v) | v <- [A,G,T]]
| i == (A,G,G) = sumMod [arr ! (t,u,v) | v <- [A,G,T]]
| otherwise = sumMod [arr ! (t,u,v) | v <- [A,C,G,T]]
]

main = do
print \$ sumArr \$ iterate step data3 !! (n - 3)
```

#### Submission Info

Submission Time 2019-03-25 02:06:35+0900 D - We Like AGC mod_poppo Haskell (GHC 7.10.3) 400 2196 Byte AC 5 ms 1404 KB

#### Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
 AC × 3
 AC × 13
Set Name Test Cases
Sample a01, a02, a03
All a01, a02, a03, b04, b05, b06, b07, b08, b09, b10, b11, b12, b13
Case Name Status Exec Time Memory
a01 AC 1 ms 508 KB
a02 AC 1 ms 508 KB
a03 AC 5 ms 1404 KB
b04 AC 2 ms 508 KB
b05 AC 2 ms 508 KB
b06 AC 2 ms 508 KB
b07 AC 2 ms 636 KB
b08 AC 2 ms 636 KB
b09 AC 3 ms 892 KB
b10 AC 5 ms 1276 KB
b11 AC 5 ms 1404 KB
b12 AC 5 ms 1404 KB
b13 AC 5 ms 1404 KB