競プロ AOJ Haskell

オンラインジャッジを使って体で覚えるHaskell入門 パート6

Haskell完全初心者向けにHaskellを理論ではなく実際にAizu Online Judgeの問題を解きながら体で覚えようというHaskell入門シリーズの第6弾です。
Feb. 13, 2020, 3:31 p.m.

この記事の対象読者と目的

この記事は、Haskell完全初心者向けにHaskellを理論ではなく実際にAizu Online Judgeの問題を解きながら体で覚えようというHaskell入門シリーズの第6弾です。

前回までの内容はこちら。

オンラインジャッジを使って体で覚えるHaskell入門 パート5

目次

ITP1_9_A - カウント

問題

ある単語の文章中の出現頻度をカウントする問題です。

https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/all/ITP1_9_A

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
import Data.List
import Data.Char

main = interact $ show' . solve . read'
  where
    show' x = (show x) ++ "\n"
    solve (word, words) = count word words 0
    count word [] acc = acc
    count word (x:xs) acc | word == x = count word xs (acc + 1)
                          | otherwise = count word xs acc
      where l = length word
    read' = f . lines
      where f (x:xs) = ([toLower c | c <- x], words [toLower c | c <- (unlines xs)])

以前toLowerを使用した際はすでに小文字のものには適用できないという先入観がありわざわざ場合分けしていましたがそれは不要でした。
toLowerはもともと小文字の場合には何もせずにそのままで返してくれるそうです。

あとは新しい要素は特にありません。

ITP1_9_B - シャッフル

問題

文字列を切り離して前後を入れ替えて結合する操作を繰り返して出来る最終的な文字列を答える問題です。

https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/all/ITP1_9_B

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
import Data.List
import Data.Char

main = interact $ show' . solve [] . read'
  where
    show' = unlines . reverse
    solve acc [] = acc
    solve acc (s:n:xs) = solve ((solveOne init' s):acc) tail'
      where
        (init', tail') = splitAt (readInt n) xs
        solveOne [] s = s
        solveOne (y:ys) s = solveOne ys (st ++ sh)
          where (sh, st) = splitAt (readInt y) s
    read' = takeWhile (/= "-") . lines
    readInt = read :: String -> Int

ITP1_9_C - カードゲーム

問題

2人の人が文字列を出し合って辞書順で遅い方が勝ちというゲームをします。
最終的な2人のスコアを計算する問題です。

https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/all/ITP1_9_C

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
import Data.List
import Data.Char
import Text.Printf

main = interact $ show' . solve . read'
  where
    show' xs = (unwords [showA xs, showB xs]) ++ "\n"
    showA = show . sum
    showB = show . sum . flip
    solve [] = []
    solve ([a, b]:xs) | a == b    = 1:(solve xs)
                      | a <  b    = 0:(solve xs)
                      | otherwise = 3:(solve xs)
    flip = map flipOne
      where flipOne x | x == 0 = 3
                      | x == 3 = 0
                      | otherwise = 1
    read' = map words . tail . lines :: String -> [[String]]

プレイヤーが2人しかいないので、プレイヤーAの得点リストが分かればBの得点リストも分かります。
solveでプレイヤーAを計算してshow'でAの得点を合計し、Bの得点を求め合計して出力しています。

Haskell的に新しいところは特にありません。

ITP1_9_D - 文字列変換

問題

文字列を複数の命令に従って切ったり入れ替えたり繋げたりする問題です。

https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/all/ITP1_9_D

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import Data.List

main = do
  str <- getLine
  _ <- getLine
  getContents >>= process str . lines
  where
    process acc [] = return ()
    process acc (x:xs)
      | cmd == "print" = do
        print' params acc
        process acc xs
      | cmd == "reverse" = do
        process (reverse' params acc) xs
      | cmd == "replace" = do
        process (replace' params acc) xs
      where (cmd:params) = words x
    print' [a, b] xs = putStrLn $ slice a' b' xs
      where
        a' = read a :: Int
        b' = read b :: Int
    reverse' [a, b] str = (take a' str) ++ (reverse $ slice a' b' str) ++ (drop (b'+1) str)
      where
        a' = read a :: Int
        b' = read b :: Int
    replace' [a, b, p] str = (take a' str) ++ p ++ (drop (b'+1) str)
      where
        a' = read a :: Int
        b' = read b :: Int
    read' = lines
    slice from to xs = take (to - from + 1) (drop from xs)

今回リストを範囲でくり抜くような処理(最近の他の言語でいうとスライス)だったので調べてみましたが標準関数としては無さそうでした。
ここまでHaskellをやってきてHaskellには基本的に関数だけが用意されていてそれを組み合わせて作れるような関数はあえて用意していない印象です。
そこでsliceを自分で定義しましたが、リストを先頭n要素で切り取るtake n lst関数と、リストのn以降を切り抜くdrop n lst関数を使って簡単に定義できました。

1つハマったのは、いつもの調子でputStrLn $ slice a' b' xsの部分を関数合成でputStrLn . slice $ ...と書きたかったのですが、sliceの型をString型を返すようにしてもどうにもコンパイルエラーで結局諦めました。

ITP1_10_A - 距離

問題

与えられた2点間の距離を求める問題です。

https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/all/ITP1_10_A

解答

1
2
3
4
5
6
7
8
import Data.List
import Data.Char
import Text.Printf

main = interact $ show . solve . read'
  where
    solve [p1x, p1y, p2x, p2y] = sqrt $ (p2x - p1x) ** 2 + (p2y - p1y) ** 2
    read' = map read . words :: String -> [Double]

実数を扱う問題は久しぶりですね。
今回は登場する数が全て実数だったのでreadDoubleで型推論させるだけで簡単に実数を扱えました。
新しい関数としてsqrtが出てきました。
これはほとんどの言語にあるものと同じように使うことが出来ました。

ITP1_10_B - 三角形

問題

三角形の二辺とその間の角が与えられるので、残りの辺の長さ、面積、高さを求める問題です。

https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/all/ITP1_10_B

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
import Text.Printf

main = getLine >>= show' . solve . read'
  where
    show' (a, b, c) = putStrLn $ printf "%.9f %.9f %.9f" a b c
    solve [a, b, cDeg] = (area, len, height)
      where
        height = 2 * area / a
        len = a + b + c
        area = a * b * (sin cRad) / 2
        c = sqrt $ (a ** 2) + (b ** 2) - 2 * a * b * (cos cRad)
        cRad = (2 * pi * cDeg) / 360
    read' = map read . words :: String -> [Double]

高校数学のような問題です。
正弦定理と余弦定理の公式そのままです。
Haskell的に新しい要素は特にありません。

ITP1_10_C - 標準偏差

問題

標準偏差を求める問題です。

https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/all/ITP1_10_C

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
import Text.Printf

main = interact $ show' . solve . read'
  where
    show' = unlines . map (printf "%.9f")
    solve [] = []
    solve (x:y:xs) = (solveRow (x ++ y)):(solve xs)
    solveRow (n:xs) = sqrt $ sigma / n
      where
        sigma = sum [(x - avg)**2 | x <- xs]
        avg = (sum xs) / n
    read' = map (map read . words) . init . lines :: String -> [[Double]]

標準偏差(分散)の公式は、

$$\sigma^2 = \displaystyle \sum_{x \in X}{(x - m)^2}/|X|$$

$m$は$X$の平均値です。

Haskellでは数式をトップダウンで書き下していけるので楽しいですね。

ITP1_10_D - ミンコフスキー距離

問題

2つのベクトルについていくつかの距離を求める問題です。

https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/all/ITP1_10_D

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
import Text.Printf

main = interact $ show' . solve . read'
  where
    show' = unlines . map (printf "%.9f")
    solve xs = [minkovsky 1 xs, minkovsky 2 xs, minkovsky 3 xs, minkovsky (-1) xs]
    minkovsky p [a, b] = (g $ zipWith f a b) ** (1 / p')
      where
        f x y = (abs (x - y)) ** p'
        g | p == -1 = foldr1 max
          | otherwise = sum
        p' | p == -1 = 1
           | otherwise = p
    read' = map (map read . words) . tail . lines :: String -> [[Double]]

ミンコフスキー距離という1つの数式を見事に1つの関数で表現出来ました。
$p = \infty$はp = -1で表現しています。

Haskell的にはfoldr1が新しい関数です。
foldr1は単位元不要でリストを集計してくれる関数です。

単位元というのは、リストのどの要素に関数を適用してもその要素が返ってくるような値です。
例えば、+という関数であればリスト内のどんな整数も0+しても変化しません。

ただのfoldrだとfoldr -INFTY max xsというように-INFTYという単位元を与える手間がありましたが、foldr1の場合は不要です。
リスト内の最大値を求める関数はfoldr1 maxというように書けます。