お布団宇宙ねこ

にゃーん

HaskellでAOJの問題を解いた(ITP1_7)

AOJ の Introduction to Programming を解いたときのメモです。

前回: HaskellでAOJの問題を解いた(ITP1_6)

今回解いた問題

7_A Grading

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_7_A

import Control.Applicative ((<$>))
import qualified Control.Monad as Monad (when)

main = loopGrading

loopGrading :: IO ()
loopGrading = do
    result <- map (read :: String -> Int) . words <$> getLine
    Monad.when (any (/= (-1)) result) $ do
        putStrLn $ grading result
        loopGrading

grading :: [Int] -> String
grading [m,f,r]
    | m == (-1) || f == (-1) = "F"
    | total >= 80            = "A"
    | total >= 65            = "B"
    | total >= 50 || r >= 50 = "C"
    | total >= 30            = "D"
    | otherwise              = "F"
    where total = m + f

試験の点数によってAやBなどの成績をつけるありふれた問題です。ガードと where 節を使うと綺麗に書ける気がします。

7_B How many ways?

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_7_B

import Control.Applicative ((<$>))
import qualified Control.Monad as Monad (when)

main = do
    nx <- getLine' $ map read . words
    Monad.when (any (/= 0) nx) $ do
        print $ length $ combination nx
        main

getLine' :: (String -> a) -> IO a
getLine' f = f <$> getLine

combination :: [Int] -> [[Int]]
combination [n,x] = [[a,b,c] | a <- [1..n], b <- [a..n], c <- [b..n],
                                a + b + c == x, a /= b, a/= c, b /= c]

組み合わせの問題もリスト内包表記で表現することができます。重複無しにするためには b と c の始めの要素を1つ前の変数の要素から始めることと、それぞれの変数の要素が一致しないように述語を入れることで実現できます。

また今回は getLine で入力を受け取る部分を String -> a の関数を受け取る関数にしてみました。こう書くことで型推論によって (read :: String -> Int) みたいなことをいちいち書かなくても済む...ような気がします(型推論がどこまで面倒を見てくれるのかよくわかっていない)。

7_C Spreadsheet

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_7_C

import Control.Applicative ((<$>))
import qualified Control.Monad as Monad (forM, replicateM)

type Row = [Int]
type Spreadsheet = [Row]

main = do
    [r,c] <- getLine'
    xs <- Monad.replicateM r $ getLine'
    mapM_ (putStrLn . printFormat) =<< newSpreadsheet (c+1) xs

getLine' :: IO [Int]
getLine' = map read . words <$> getLine

printFormat :: Row -> String
printFormat xs = unwords $ show <$> xs

newSpreadsheet :: Int -> Spreadsheet -> IO Spreadsheet
newSpreadsheet n xs = do
    let xs' = zipWith (++) xs $ rowSums xs
    return $ xs' ++ columnSums n xs'

rowSums :: Spreadsheet -> Spreadsheet
rowSums = map $ (:[]) . sum

columnSums :: (Monad m) =>Int -> Spreadsheet -> m Row
columnSums n xs = Monad.forM [0..(n-1)] $ \i -> return $ sum $ map (!! i) xs

入力として与えられるエクセル表のような数列に、各行の最後の列としてその行の合計値を、各行の最後の行としてその列の合計値を追加した表を出力するという問題でした。

rowSums で各行の行の合計値を計算した後に columnSums で各列の列の合計値を計算するようにしています。本当はモナド必要ないのに繰り返しを forM を使って計算させるの違和感しかないので、何か別の良い方法ないですかね...。畳み込みは今回だと与えられたリストに対して処理を行うわけではないため適切ではないと思い使いませんでした。

7_D Matrix Multiplication

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_7_D

import Control.Applicative ((<$>), (<*>))
import qualified Control.Monad as Monad (replicateM)
import qualified Data.List as List (transpose)
import qualified Data.List.Split as Split (chunksOf)

type Row = [Int]
type Matrix = [Row]

main = do
    [n,m,l] <- getLine'
    a <- Monad.replicateM n getLine'
    b <- Monad.replicateM m getLine'
    let result = toMatrix l $ dotProduct <$> a <*> List.transpose b
    mapM_ (putStrLn . printFormat) result

getLine' :: IO [Int]
getLine' = map (read :: String -> Int) . words <$> getLine

printFormat :: Row -> String
printFormat xs = unwords $ show <$> xs

toMatrix :: Int -> [Int] -> Matrix
toMatrix n xs = Split.chunksOf n xs

dotProduct :: Row -> Row -> Int
dotProduct xs ys = sum $ zipWith (*) xs ys

6_D Matrix Vector Multiplication では行列と列ベクトルの積を計算する問題でしたが、今回は行列同士の積を計算する問題です。行列Aと行列Bの積は、行列Aの行と、行列Bの転置行列の列の内積で計算することができます。行列の転置には transpose という便利な関数が Data.List モジュールにあるためそれを使いました。

どうして転置行列を使うことで行列の積が計算できるのかは別途証明する必要がありそうです...。(その辺りの文献が見当たらなかったので)

参考文献

github.com