Codeforces Beta Round #82 (Div. 2)

Codeforcesに再び参戦。
言語は性懲りもなくHaskell。
今回はそこそことれました。

A:412(00:19)
B:844(00:39)
C:864(01:46)
D,E:No Submit
No Hack

2120 pts 197位
Rating : 1453 -> 1521

Aは書くだけだったからもっと手早く書くべきだった。
完全に取れる問題だっただけに惜しい。
Bもoutdatingな要素をのぞいてソートするだけ。
A、B共に実装早解きゲーでしたね。

Cはgreedyかな……と思って価値／質量の比を計算しようとしたところで、なんだこれ個数制限つきナップサック問題とほぼ同じじゃんと思い直した次第です。

以下にコードの一部を載せます。
一部というのはI/O周りのライブラリが長いからです。今度載せます。
一応説明しておきますと、scanQuatroが４つ組を取得する関数で、scansが指定した回数、引数のI/Oモナドを適用する関数です。
List、Arrayモジュールをインポートしています。

frag [] l = l
frag ((a,b,c,d):xs) l = if a < b then
                            frag xs l
                        else
                            frag ((a-b,b,c,d):xs) ((c,d):l)

eval (a, b) = a+b

maxOfArray i j n m ary max = 
    if j > m then
        if i == n then
            max
        else
            maxOfArray (i+1) 0 n m ary max
    else
        if (eval (ary!(i,j))) > max then
            maxOfArray i (j+1) n m ary (eval (ary!(i,j)))
        else
            maxOfArray i (j+1) n m ary max

solve_ n c0 d0 l = let m = length l in solve n m c0 d0 l

solve n m c0 d0 l = maxOfArray 0 0 n m dp (-1)
    where
      staffs = listArray (1,m) l
      c i = fst (staffs!i)
      d i = snd (staffs!i)
      dp = array ((0,0),(n,m)) [((i,j),f i j)|i<-[0..n],j<-[0..m]]
      f i 0 = (0, (n `div` c0)*d0)
      f i j = (g i j, ((n-i) `div` c0)*d0)
      g i j = if i < (c j) then
                  fst (dp!(i,j-1))
              else
                  max (fst (dp!(i,j-1))) ((fst ((dp!(i-(c j),j-1))) + (d j)))

main = do (n,m,c0,d0) <- scanQuatro :: IO (Int,Int,Int,Int)
          abcd <- scans m (scanQuatro :: IO (Int,Int,Int,Int))
          putAnsLn (solve_ n c0 d0 (frag abcd []))

多分あんまり効率よくないDP。
DPは書き方練習していたのでよかった。多少複雑でも何とかなるもんですね。

次のエントリでCodeforces用のI/Oライブラリを紹介する予定です。

それでは。