🐛

Haskellでしゃくとり法を攻略する

2023/02/16に公開

Haskell

はじめに

しゃくとり法とは、数列や文字列などの連続部分列に関する問題を効率的に解くためのアルゴリズムです。しゃくとり法では、通常、左端と右端の2つのポインタを用意して、条件を満たす最大（または最小）の部分列を探索します。なるべく、コードの再利用性や可読性を重視して、ライブラリ化していきます。
結論から言うと、(二項演算、逆演算、単位元)という構造で抽象化できます。

自分自身、今後も使いそうなので、勉強の記録でつけているスクラップから記事にまとめます。

ライブラリの特徴

バグの温床である添え字は使わない
代数構造で柔軟性をもたせる

ライブラリで使うパラメータ

左端 l から右端 r までの部分列 A[l…r] を考えます。この部分列が条件 p を満たすかどうかを調べます。

また、
右端rを右へ動かした時（伸ばした時）の res の更新方法 op
左端lを右へ動かした時（縮めた時）の res の更新方法 invOp
左端lと右端rが同じ時(長さが0の時)の res の初期値 identity
を定義します。

以上の4つ （p, op, invOp, identity） を与えることで、任意の問題へ適用可能なしゃくとり法を実装していこうと思います。
各 $A_{i}$ に対して、 $f(A_{i}) = length_{i}$ を求めます。

条件pの制約

条件pもなんでもいいわけではなく、
ある区間が「条件p」を満たすなら、それに含まれる任意の区間も「条件p」を満たす
という制約があります。単純に言えば、尺取虫が途中でちぎれてはダメということです。

なので、1つ目の例の(<=k,*,div,1)に関しても、数列が自然数だからこそ成り立っており、数列の中に0.1や-1などが紛れ込んでいたら、しゃくとり法は使えません。
２つ目の例の(<=k,+,-,0)に関しても同様で、数列が非負整数では適用できますが、-1など整数の数列だった場合は使えません。

shakutori :: (a -> b -> Bool) -- 条件 p
         -> (b -> a -> b) -- 右端を伸ばす演算 op
         -> (b -> a -> b) -- 左端を縮める演算 invOp
         -> b -- 初期値 identity
         -> [a] -- 入力リスト as
         -> [Int] -- 条件を満たす部分列の長さのリスト
shakutori p op invOp identity as = go as as 0 identity
  where
    -- 右端が空になったら、左端を1つ縮める
    go lls@(l:ls) [] len res = len : (go ls [] (len-1) (invOp res l))
    go lls@(l:ls) rrs@(r:rs) len res
      -- 条件 p を満たすなら、右端を1つ伸ばす
      | p r res = go lls rs (len + 1) (op res r)
      -- 長さが0であれば、スキップする
      | len == 0 = 0:(go ls rs 0 identity)
      -- 条件 p を満たさないなら、左端を1つ縮める
      | otherwise =  len : (go ls rrs (len-1) (invOp res l))
    go _ _ _ _ = []

具体例

shakutori (\r res -> res *r <= k) (*) div 1 as

shakutori (\r res -> res + r <= k) (+) (-) 0 as

shakutori (\r res -> res < r) max (\res l -> if res == l then minBound else res) minBound as

shakutori (\r res -> r + res <=k ) (+) (-) 0  $  zipWith (-) (tail as) as

shakutori (\r res ->not (S.member r res)) (flip S.insert) (flip S.delete) S.empty as

shakutori (\r a -> a+r == a.|.r) (+) (-) 0 as

DPは別記事、ModIntはスクラップを参照。下記のas'を使って、DP。

let as' = shakutori (\r res -> not (S.member r res)) (flip S.insert) (flip S.delete) as

supplement :: (Array Int Int, Int, Int) -> DPProblem Int (ModInt 1000000007)
supplement (as,n,m) = DPProblem {
  start = n,
  getRange = (-1, n),
  isTrivial = \i-> case i of
    -1 -> Just (-1)
    0 -> Just 0
    1 -> Just 1
    _ -> Nothing,
  subproblems = \i -> [(2, i - 1), (-1, i-as ! i-1)]
}

はじめに

ライブラリの特徴

ライブラリで使うパラメータ

具体例

Discussion