Hatena::Grouptopcoder

ぷろこんメモ用紙

 | 

2013-02-10

Atcoder Regular Contest #012

00:15

競技プログラミングってバグ混入すると一撃死でつらいですね.

そういう時は,Haskellみたいな間違えにくい言語を使うと楽になるんじゃないかなと妄想したのでARCでやってみました.

とりあえず詰まったら Hoogle http://www.haskell.org/hoogle/ を見ると良いです.

あとfromIntegralとかreadとかはイディオムなので覚える.

いわゆるprintfデバッグには Data.Trace が便利です.

(参考: http://itpro.nikkeibp.co.jp/article/COLUMN/20071204/288630/ )

あまりHaskell力高くないので,変なことをやってるかも.

A 週末

文字列の比較するだけ.

Data.List.elemIndexを使うと,リストから一致する要素の場所が取れる.

import Data.List

workdays :: [String]
workdays = ["Monday", "Tuesday", "Wednesday", "Thursday", "Friday"]

main :: IO ()
main = do
    line <- getLine
    let remain = case elemIndex line workdays of
               Just idx -> 5 - idx
               Nothing -> 0
    putStrLn $ show remain

B アキレスと亀

高橋君がL動くのにかかった時間 * v_b が次の間隔になる.

これを N 回繰り返せばよい.

一行に数値が並んでるのを名前つけて取り出す方法が分からず,苦し紛れにarrayに突っ込んで書いた.

名前ないと流石に不便な気がするけど,どう書くのがベストなんだろうか…….

あと,浮動小数をshowで文字列化すると指数表記になるので注意.

最初はHoogleで出てきたshowFFloatという関数を使って頑張っていたけど,そういえばprintfがあるってλカ娘4に書いてあったなと思い出した.

import Data.Array
import Text.Printf

solve :: Int -> Double -> Double -> Double -> Double
solve n va vb l | n == 0 = l
                | otherwise = solve (n-1) va vb (vb * l / va)
main :: IO ()
main = do
    line <- getLine
    let arr = listArray (0,3) $ map (read::String->Int) $ words line :: Array Int Int
    printf "%.10f\n" $ solve (arr!0) (fromIntegral $ arr!1) (fromIntegral $ arr!2) (fromIntegral $ arr!3)

C 五目並べチェッカー

石が並んでいる個数の判定を書くのにものすごく手間取って,時間内に書き終わらなかった.

まあ,それがなくても場合分けしまくる方針しか考えてなかったので,どっちにしろ落ちていた気がする…….

最後に着手したのがxかoかをまず判定して,最後に打った石がどれかを決めるのがうまいやり方らしい.

以下,その方針で書いたコード*1

入力はIOArrayを使って1文字ずつ読んでいく.

(参考: http://d.hatena.ne.jp/eiel/20120217 )

次に石の個数を数えて,明らかにおかしいならそこで終わり.

石の数が正常なら最後に打ったのがどちらかを確認し,最後に打たれた石を決めに行く.

Haskellだと,線形な数値の列挙はリスト表記で書けてしまうので,座標の列挙が楽で良いですね.

あと,diag2Listのsを最初0..36にしていてバグった.

型チェックがあってもこういうのには無力ですね…….

import Control.Monad
import Data.Array.IO
import Data.Array.IArray
import Debug.Trace

type IOField = IOArray (Int,Int) Char
type Field = Array (Int,Int) Char

countField :: Field -> (Int,Int)
countField field = foldl accum (0,0) [(r,c) | r <- [0..18], c <- [0..18]]
    where
        accum (on,xn) pos = 
            let ch = field!pos
            in if ch == 'o' then (on+1,xn)
                            else if ch == 'x' then (on,xn+1)
                                              else (on,xn)

checkWin :: Char -> Field -> Bool
checkWin color field = (checkWin' rowList) || 
                       (checkWin' colList) || 
                       (checkWin' diag1List) || 
                       (checkWin' diag2List)
    where
        checkWin' (l:ls) = 
            let seq = maximum $ scanl accum 0 l
                win = seq >= 5
            in if win then True
                      else checkWin' ls
        checkWin' _ = False
        accum cur pos = if field!pos == color then cur+1
                                              else 0
        rowList = [[(r,c) | c <- [0..18]] | r <- [0..18]]
        colList = [[(r,c) | r <- [0..18]] | c <- [0..18]]
        diag1List = [[(r,c) | r <- [0..18], c <- [0..18], r+c == s] | s <- [0..36]]
        diag2List = [[(r,c) | r <- [0..18], c <- [0..18], r-c == s] | s <- [-18..18]]

checkRemoved :: (Int,Int) -> Field -> Bool
checkRemoved pos field = 
    let newField = field // [(pos, '.')]
    in not $ checkWin (field!pos) newField

checkLastTurn :: Char -> Field -> Bool
checkLastTurn turn field = or $ map checkAt [(r,c) | r <- [0..18], c <- [0..18]]
    where
        checkAt pos =
            let ch = field!pos
            in if ch == turn then checkRemoved pos field
                             else False

isValid :: Field -> Bool
isValid field = let (on,xn) = countField field
                in if on < xn || on >= xn+2
                      then False
                      else let turn = if on == xn
                                         then 'x'
                                         else 'o'
                           in (on+xn == 0) || (notWin (opposite turn) field && checkLastTurn turn field)
    where
        notWin color field = not $ checkWin color field
        opposite 'x' = 'o'
        opposite 'o' = 'x'

main :: IO ()
main = do
    field <- newArray ((0,0),(18,18)) '.' :: IO IOField
    forM_ [0..18] $ \r -> do
        forM_ [0..18] $ \c -> do
            ch <- getChar
            writeArray field (r,c) ch
        getChar
    f <- freeze field
    putStrLn $ if isValid f
                  then "YES"
                  else "NO"

*1:最初に書いたコードは捨てているので,かなり考え方も整理された後のものであることに注意.

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/osa_k/20130210
 |