配列
ネットサーフィンしていたらCompetitive Programming Advent Calendarのページを見つけまして。やっぱりトップレベルの人たちの考え方はすごいなーと見ていたらチャレンジ問題があったので久々にHaskellでチャレンジしてみました。
アルゴリズムとしては条件が厳しい人から割り当てていけば良さそうです。始めに入力のリストを作ってソートして、条件が厳しい人から条件に当てはまる日付に当てはめます。
ここで、疑問が発生。人を日付に当てはめていくのはどうやって表現すれば良いんだろう?
CやJavaなら日付の配列を作って配列の値を変化させていけばいいけど、確かHaskellって変数とかないよな・・・?
調べたらありました。Data.Array.IOモジュールのIOArrayを使うと、CやJavaの配列のようにインデックスを使って値を読み込んだり値を更新出来る配列を作ることが出来ます(しかもO(1)で読み書き出来、コストも小さいらしいです)。
import Data.List import Data.Array.IO printMax arr c mx | 0 < c = do a <- readArray arr c if (a <= mx) then printMax arr (c - 1) mx else printMax arr (c - 1) a | otherwise = print mx findMin ary arr n p c mn | n <= c = do a <- readArray arr c b <- readArray arr mn if (a < b) then findMin ary arr n p (c - 1) c else findMin ary arr n p (c - 1) mn | otherwise = do b <- readArray arr mn writeArray arr mn (b + 1) dist ary (p - 1) arr addPerson ary p arr = do findMin ary arr (ary !! p) p 25 25 dist ary p arr | 0 <= p = do addPerson ary p arr | otherwise = do printMax arr 25 0 main = do n <- fmap (read :: String -> Int) getLine if 0 < n then do ary <- fmap (map (read :: String -> Int)) (fmap words getLine) arr <- newArray (1,25) 0 :: IO (IOArray Int Int) dist (sort ary) (n - 1) arr main else return()
しかし、Haskellはおそらくこういう値の更新が必要な配列を扱うのはあまり好ましくないんでしょうね・・・。特にHaskellの特徴を活かしていないので、これならC、Javaで書いた方が良さそうです。
未だにHaskellの特徴を活かしたプログラミングがよく分かりません・・・。