HaskellでCodeforcesに参戦してきた

昨夜あったCodeforces Div2 #79に参戦してきました。使用言語はHaskell。
SRMではC++なので、案の定いろいろと苦労しました。

基本的にこれから、SRMはC++で、CodeforcesはHaskellで参戦しようと思ってます。

A:Accepted
B:Accepted
C,D,E:(未送信)

954 pts
Non-rated -> 1453

まあ、初参加なんでこんなもんでいいかなと。
でも次はA,B,C通しての1200ptsくらい狙いたいですね。

以下、解いた問題について軽く方針を。

Aは
（１）衣服の番号をインデックスとし、それとマッチする衣服のリストを値として持つ配列を作成。
（２）衣服iについて、iにマッチする服jと、jにマッチする服kを上で作った配列を用いて取得し、kにiがマッチしたらそれら３つの価格の和を求める。
（３）全ての衣服の全ての(i,j,k)の組み合わせに対し価格を求め、最安値を返す。

割と早く思いつけたけど実装に手間取りました。
入れ替えた対応関係も考慮に入れないといけないということに気づかず一回プレテストで落とされました。

Bは
（１）数字を文字列として頭から読み込み、１桁読みこむごとに足していく
（２）１ケタになるまで（１）をくりかえす。

こっちのがはるかにAより簡単でした。
TLEが心配でしたが無事通りました。

以下コード。

import Array

getIntPairs :: IO (Int,Int)
getIntPairs = do ns <- getLine
                 return (make_pair [(read n::Int)|n<-(words ns)])
                        where
                          make_pair (x:y:_) = (x,y)
                          make_pair _ = (0,0)

getInts :: IO [Int]
getInts = do ns <- getLine
             return [(read n::Int)|n<-(words ns)]

getPairLines :: Int -> IO [(Int,Int)]
getPairLines n = if n > 0 then
                     do l <- getIntPairs
                        ls <- getPairLines (n-1)
                        return (l:ls)
                 else
                     return []

putAnsLn :: (Show a) => a -> IO ()
putAnsLn ans = putStrLn (show ans)

include x [] = False
include x (l:ls) = if x==l then True else include x ls

mins m [] = m
mins m (x:xs) = if m>x then mins x xs else mins m xs

loop_find n ms = filter (\(j,k) -> include n (ms!k)&&n/=j&&n/=k ) [(j,k)|j<-(ms!n),k<-(ms!j)]

solve n m a uv = solve_rec 100000000 [1..n]
    where
      solve_rec ans [] = if ans==100000000 then -1 else ans
      solve_rec ans (i:is) = solve_rec (mins ans [prices!i + prices!j + prices!k|(j,k)<-loops]) is
          where
            loops = loop_find i matchings
            prices = array (1,n) (zip [1..n] a)
            matchings = make_matching (array (1,n) [(i,[])|i<-[1..n]]) uv
                where
                  make_matching ary [] = ary
                  make_matching ary ((u,v):uvs) = make_matching ((ary//[(u,v:(ary!u))])//[(v,u:(ary!v))]) uvs
                         

main = do (n,m) <- getIntPairs
          a <- getInts
          uv <- getPairLines m
          putAnsLn (solve n m a uv)

import Char
import List

putAnsLn :: (Show a) => a -> IO ()
putAnsLn ans = putStrLn (show ans)

digitsum [] s = s
digitsum (n:ns) s = digitsum ns (s + (ord n) - 48)

solve n ans = if (length n) == 1 then
                  ans
              else
                  solve (show (digitsum n 0)) (ans+1)

main = do n <- getLine
          putAnsLn (solve n 0)

こうして見比べてもやっぱBのほうが簡単……というよりAの実装にモタつきすぎました。
これからもうちょっと頑張ってみようと思ってます。

それではﾉｼ