結果

問題 No.43 野球の試合
コンテスト
ユーザー ducktail
提出日時 2018-07-13 20:31:02
言語 Haskell
(9.10.1)
結果
AC  
実行時間 8 ms / 5,000 ms
コード長 956 bytes
コンパイル時間 6,873 ms
コンパイル使用メモリ 201,728 KB
実行使用メモリ 8,320 KB
最終ジャッジ日時 2024-10-09 05:06:31
合計ジャッジ時間 7,223 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 7
権限があれば一括ダウンロードができます
コンパイルメッセージ
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.Applicative ((<$>))
import Control.Monad (replicateM)
import Data.List (partition, foldl', nub)
import Data.Vector.Unboxed (Vector, (!), (//))
import qualified Data.Vector.Unboxed as V

main :: IO ()
main = do
  n <- readLn
  solve n <$> replicateM n getLine >>= print

solve :: Int -> [String] -> Int
solve n ss = search pv uks
  where pis = do
          i <- [0..n-2]
          j <- [i+1..n-1]
          case ss !! i !! j of
           'o' -> return (i, 1)
           'x' -> return (j, 1)
           _ -> []
        pv = V.accum (+) (V.replicate n 0) pis :: Vector Int
        uks = do
          i <- [0..n-2]
          j <- [i+1..n-1]
          if ss !! i !! j == '-' then return (i, j) else []
        rnk v = (+1) . length . nub $ foldl' (\xs i -> if v ! i > v ! 0 then (v ! i):xs else xs) [] [1..n-1]
        search v [] = rnk v
        search v ((i,j):rs) = min (search (V.accum (+) v [(i,1)]) rs) (search (V.accum (+) v [(j,1)]) rs)
0