Submission #50893982

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import Control.Monad
import qualified Data.ByteString.Char8 as BS
import Data.Char
import Data.List
import Data.Array.Unboxed
import Data.Bits
main :: IO ()
main = do
  [n] <- bsGetLnInts
  ss <- replicateM n $ do
    l <- BS.getLine
    return $ if isLower $ BS.last l then l else BS.init l
  let ans = abc343g n ss
  print ans
bsGetLnInts :: IO [Int]
bsGetLnInts = unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
abc343g :: Int -> [BS.ByteString] -> Int
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

import Control.Monad
import qualified Data.ByteString.Char8 as BS
import Data.Char
import Data.List

import Data.Array.Unboxed
import Data.Bits

main :: IO ()
main = do
  [n] <- bsGetLnInts
  ss <- replicateM n $ do
    l <- BS.getLine
    return $ if isLower $ BS.last l then l else BS.init l
  let ans = abc343g n ss
  print ans

bsGetLnInts :: IO [Int]
bsGetLnInts = unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine

abc343g :: Int -> [BS.ByteString] -> Int
abc343g n ss = kick `seq` minimum [lens ! (pred $ 2 ^ succ nn, i) | i <- [0..nn]]
  where
-- 文字列どうしの重なり量を計測 ovs ! (i,j) Sjの末尾とSiの先頭の重なる長さ
    ovs :: UArray (Int,Int) Int
    ovs = listArray ((1,1),(n,n))
          [ if i == j then BS.length si else kmpSearch si sj t
          | (si,i) <- zip ss [1..], let t = kmpTable si
          , (sj,j) <- zip ss [1..]
          ]
-- 埋まってしまう（同一を含む）文字列を除去した、扱うべき背番号のリスト
    is = foldl' instep [1..n] [1..n]
    instep js i = if any prop js then delete i js else js
      where
        prop j = i /= j && ovs ! (i,j) == ovs ! (i,i)
-- 本当に扱う相手に絞った情報にする 0 始まりにもする
    nn = pred $ length is
    uf = listArray (0, nn) is :: UArray Int Int
    uovs i j = ovs ! (uf ! i, uf ! j)
-- TSPで最短文字列長を求める
    bnds = ((1,0), (pred $ 2 ^ succ nn, nn)) -- ビット集合, 末尾の番号
    lens = listArray bnds $ map lenF $ range bnds :: Array (Int,Int) Int
    lenF (bs, i)
      | not $ testBit bs i = maxBound  -- bsにiがない
      | popCount bs == 1 = uovs i i    -- iのみのとき、iの長さ
      | otherwise = uovs i i + minimum -- iの手前jを総当たりで、jまでの長さ+iの長さ-重なり長 の最小値
        [ lens ! (bs1, j) - uovs i j
        | let bs1 = clearBit bs i
        , j <- [0..nn], testBit bs1 j
        ]
    kick = foldl' kstep () $ range bnds
    kstep st i = lens ! i `seq` ()

kmpSearch :: BS.ByteString -> BS.ByteString -> UArray Int Int -> Int
kmpSearch pat text tbl = loop 0 0
  where
    plen = BS.length pat
    tlen = BS.length text
    loop m i
      | i == plen = i -- パターンを全て照合できた
      | m + i == tlen = i -- パターン途中でテキスト終端に到達した
      | BS.index pat i == BS.index text (m + i) = loop m (succ i) -- 次の文字へ
      | otherwise = loop (m + i - ti) (if i > 0 then ti else 0) -- リセット
      where
        ti = tbl ! i

kmpTable :: BS.ByteString -> UArray Int Int
kmpTable pat = tbl
  where
    plen = BS.length pat
    tbllist = -1 : 0 : loop 2 0
    tbl = listArray (0, pred plen) tbllist
    loop i j
      | i == plen = []
      | cond1 = j1 : loop (succ i) j1
      | j > 0 = loop i (tbllist !! j)
      | otherwise = j : loop (succ i) j
      where
        cond1 = BS.index pat (pred i) == BS.index pat j
        j1 = succ j

Submission Info

Compile Error

app/Main.hs:28:31: warning: [-Wtype-defaults]
    • Defaulting the type variable ‘a0’ to type ‘Integer’ in the following constraints
        (Num a0) arising from the literal ‘1’ at app/Main.hs:28:31
        (Enum a0)
          arising from the arithmetic sequence ‘1 .. ’
          at app/Main.hs:28:30-34
        (Eq a0) arising from a use of ‘==’ at app/Main.hs:27:18-19
    • In the expression: 1
      In the second argument of ‘zip’, namely ‘[1 .. ]’
      In the expression: zip ss [1 .. ]
   |
28 |           | (si,i) <- zip ss [1..], let t = kmpTable si
   |                               ^

app/Main.hs:52:11: warning: [-Wunused-matches]
    Defined but not used: ‘st’
   |
52 |     kstep st i = lens ! i `seq` ()
   |           ^^

Judge Result