ABC430C Truck Driver
AtCoder 国には「トラック運転手は$ A分以上運転する際には$ B分以上の休憩を取らなければならない」というルールがあります。
$ a, bからなる長さ$ Nの文字列$ Sと正整数$ A, Bが与えられます。以下の条件を全て満たす整数組$ (l,r)の個数を求めてください。
$ 1≤l≤r≤N
$ Sの$ l文字目から$ r文字目までに含まれる$ aの個数が$ A以上
$ Sの$ l文字目から$ r文字目までに含まれる$ bの個数が$ B未満
「430休憩」とABC 430にちなんだ問題かな？
尺取り法を応用する問題かなぁ。
位置を整数に符号化して考えるのが便利ではあるけれど、かなり苦手。
（要するに Array の使い方がヘタってことなんだな ^^;）
code:haskell
type I = String
type O = Int
type Dom = (Int,Int,Int,I)
type Codom = O
type Solver = Dom -> Codom
solve :: Solver
solve = \ case
(n,a,b,s) -> case findIndex (pa . fst) ss of
Nothing -> 0
Just posa0 -> case findIndex (pb . snd) ss of
Nothing -> iter 0 1 posa0 (succ n)
Just posb0 -> iter 0 1 posa0 posb0
where
pa = (a <=)
pb = (b <=)
ss = scanl' phi (0,0) s where
phi (x,y) = \ case
'a' -> (succ x, y)
_ -> (x, succ y)
iter c l posa posb = if
| n < l -> c
| 0 < diff -> case aa ! l of
'a' -> case newposa of
[] -> c'
posa':_ -> iter c' (succ l) posa' posb
_ -> case newposb of
[] -> iter c' (succ l) posa (succ n)
posb':_ -> iter c' (succ l) posa posb'
| otherwise -> case aa ! l of
'a' -> case newposa of
[] -> c
posa':_ -> iter c (succ l) posa' posb
_ -> case newposb of
[] -> iter c (succ l) posa (succ n)
posb':_ -> iter c (succ l) posa posb'
where
diff = posb - posa
c' = c + diff
aa = listArray (1,n) s
decode :: I -> Dom
decode = \ case
n,a,b:s:_ -> (read n, read a, read b, s) _ -> invalid $ "toDom: " ++ show @Int __LINE__
encode :: Codom -> O
encode = \ case
r -> r
main :: IO ()
main = B.interact (detokenize . encode . solve . decode . entokenize)
WA をだしまくって、ようやく辿りついた。