結果

問題 No.515 典型LCP
ユーザー aimyaimy
提出日時 2017-05-06 00:11:58
言語 Haskell
(9.10.1)
結果
MLE  
実行時間 -
コード長 530 bytes
コンパイル時間 2,522 ms
コンパイル使用メモリ 170,624 KB
実行使用メモリ 991,260 KB
最終ジャッジ日時 2024-09-14 09:36:21
合計ジャッジ時間 8,414 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other MLE * 1 -- * 14
権限があれば一括ダウンロードができます
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.8.2/environments/default
[1 of 2] Compiling Main             ( Main.hs, Main.o )
[2 of 2] Linking a.out

ソースコード

diff # 

import Control.Monad
import Data.List

main = do
 n <- readLn
 ss <- replicateM n getLine
 [m,x,d] <- map read . words <$> getLine
 print $ lcp n m x d ss

lcp n m x d ss = sum $ map lcp' (seed n m x d)
 where lcp' (i,j) = length $ takeWhile id $ zipWith (==) (ss!!(i-1)) (ss!!(j-1))

seed n m x d = reverse $ snd $ foldl makeq (x,[]) [1..m]
 where
  makeq (x', acc) k = ((x' + d) `mod` (n * (n - 1)), (i',j'):acc)
   where
    i = (x' `div` (n - 1)) + 1
    j = (x' `mod` (n - 1)) + 1
    [i',j'] = if i>j then [j,i] else [i,j+1]
0