Software Design 2021年3月号「パズルで鍛えるアルゴリズム力」第8回をHaskellで実装してみる

software-design-202103-dp.hs

-- https://myuon.github.io/posts/haskell-atcoder/ を参考にしつつ競プロっぽい書き方にできないか試す

{-# LANGUAGE Strict #-}

module Main where

import qualified Data.ByteString.Char8 as BS
import qualified Data.Vector.Unboxed as VU

checkMax :: BS.ByteString -> BS.ByteString -> VU.Vector Int -> Int -> Int -> Int -> Int -> Int
checkMax l1 l2 v w h x y
  | y >= h = v VU.! (VU.length v - 1)
  | otherwise =
    let nx = if x > 0 then max (v VU.! (y * w + x)) (v VU.! (y * w + (x - 1))) else 0
        ny = if y > 0 then max (v VU.! (y * w + x)) (v VU.! ((y - 1) * w + x)) else 0
        nxny = if x > 0 && y > 0 && ((l1 `BS.index` (x - 1)) == (l2 `BS.index` (y - 1))) then max (v VU.! (y * w + x)) (v VU.! ((y - 1) * w + (x - 1)) + 1) else 0
     in if (x + 1) >= w
          then checkMax l1 l2 (v VU.// [(y * w + x, maximum [nx, ny, nxny])]) w h 0 (y + 1)
          else checkMax l1 l2 (v VU.// [(y * w + x, maximum [nx, ny, nxny])]) w h (x + 1) y

main :: IO ()
main = do
  line1 <- BS.getLine
  line2 <- BS.getLine

  let v = VU.replicate ((BS.length line1 + 1) * (BS.length line2 + 1)) 0

  print $ checkMax line1 line2 v (BS.length line1 + 1) (BS.length line2 + 1) 0 0