Google Code Jam 2009 Round2 C （メモ）

マッチングで解けるのね．
そんなの思いつきません．

解けないまま，終るのはシャクなので，Haskellで書いてみた．

import Control.Monad
import Text.Printf
import Data.Array
import Data.Graph.Inductive

-- main part

main = do
  (t:_) <- getList :: IO [Int]
  forM_ [1..t] $ \i -> do
         (n:_) <- getList
         cs <- replicateM n getList :: IO [[Int]]
         printf "Case #%d: %d\n" i $ solve n cs

graph :: (Ord a, Graph gr, Num t) => Int -> [[a]] -> gr () t
graph n cs = mkGraph nodes (edges ++ dummyEdges)
    where nodes = [(i, ()) | i <- [0..2*n+1]]
          edges = [(i,n+j,1) | i <- [0..n-1], j <- [0..n-1], (cs!!i) `above` (cs!!j)]
          dummyEdges = [(2*n,i,1) | i <- [0..n-1]] ++ [(i,2*n+1,1) | i <- [n..2*n-1]]
          above xs ys = and $ zipWith (<) xs ys

solve :: (Ord a) => Int -> [[a]] -> Int
solve n cs = n - maxFlow (graph n cs :: Gr () Int) (2*n) (2*n+1)

-- output and input function

getList :: Read a => IO [a]
getList = liftM (map read.words) getLine

実行時間が少し遅い気もするが気にしない．
2部グラフのマッチング→最大流
と経由．

あ，ちなみに次へは残念ながら進めませんでした．おおかたの予想通りです．