Haskellで競プロの問題を解いてみる

軽く自己紹介

僕(@kaicho8636)は普段、C++, Pythonで色々しながらHaskellを勉強中なのですが、言語の制約が緩いプロコンとかで使えないかなぁと思ってこの記事を書きました。

今回使うサイト

AIZU ONLINE JUDGE β

Problems & Solutions

第1問

JOI-Trial 0582

　三角形の形は辺の長さで決まる． 順番に３つの正整数が与えられたとき， 辺の長さがそれらの値と一致する三角形が存在するかどうかを調べ， 存在するなら鋭角三角形，直角三角形，鈍角三角形のいずれかを判定し， 次の入力へ進む． 三角形が存在しないとき， それまでに入力された，三角形，直角三角形，鋭角三角形，鈍角三角形の 個数を空白で区切って出力し， それ以降の入力は無視して終了する． 入力の中には必ず三角形が存在しないようなものがある と仮定してよい. 入力の行数は判らないが各行には３つの正整数が空白で区切って書かれている． ただし，各整数は100 以下とする.

出力ファイルにおいては， 出力の最後の行にも改行コードを入れること．

僕の回答

0582.hs

import Data.List
import Control.Applicative

data Tri = NotT | SharpT | RightT | DullT

typeOfTri :: [Int] -> Tri
typeOfTri [a, b, c]
  | c > a+b = NotT
  | x == LT = SharpT
  | x == EQ = RightT
  | x == GT = DullT
  where x = compare (b*b+a*a) (c*c)

loop :: Int -> Int -> Int -> Int -> IO ()
loop a b c d = do
  tri <- sort . fmap read . words <$> getLine :: IO [Int]
  case typeOfTri tri of
    NotT   -> putStrLn . unwords $ show <$> [a, b, c, d] 
    SharpT -> loop (a+1) b c (d+1)
    RightT -> loop (a+1) (b+1) c d
    DullT  -> loop (a+1) b (c+1) d

main :: IO ()
main = loop 0 0 0 0

う〜ん、結構数学的思考も求めてきますね…

第2問

JOI-Trial 0583

　入力ファイルの１行目に正整数 n が書いてあり， ２行目には半角空白文字１つを区切りとして， n 個の正整数が書いてある． n は 2 または 3 であり， ２行目に書かれているどの整数も値は 108 以下である． これら２個または３個の数の公約数をすべて求め， 小さい方から順に1行に1個ずつ出力せよ． 自明な公約数（「１」）も出力すること．

出力ファイルにおいては， 出力の最後行にも改行コードを入れること．

僕の回答

0583.hs

import Data.List
import Control.Applicative
import Control.Monad

getDivisor :: Int -> [Int]
getDivisor n = [m | m <- [1..n], n `mod` m == 0]

getCommon :: [Int] -> [Int] -> [Int]
getCommon xs ys = [x | x <- xs, y <- ys, x == y]

main :: IO ()
main = do
  getLine
  xs <- fmap read . words <$> getLine :: IO [Int]
  let cds = foldr1 getCommon $ fmap getDivisor xs
  putStr . unlines $ show <$> cds

こっちは割と問題自体は簡単ですね。
効率を追求するならStateモナドとか使ったほうがいいのかな？
最後に改行いれたら怒られました。
改行コードとか大嘘じゃん…

まとめ

Haskellでもある程度競プロはできる。

まとめ'

Haskeller少なスギィ…