読者です 読者をやめる 読者になる 読者になる

真面目なノート

こまめにその日の進捗などをメモしておく。

早起きしました ζ*'ヮ')ζ

8:30くらいに起きた

早い。とてもえらい、です。

Haskell、はしゅけぅ。

今日も今日とてAOJをやった。
今まで競技プログラミングというものを触ってこなかったので、遅ればせながら、これで少しは勉強できたら良いなとも思っている。

List Of 3 Top Hills

1819
2003
876
2840
1723
1673
3776
2848
1592
922

こういう感じで数字が渡されるのに対して、降順にソートして上から3つを返す。

3776
2848
2840

Pythonだと、

mountains = []
for i in range(10):
    mountains.append(int(input()))
for m in sorted(mountains)[-1:-4:-1]:
    print(m)

forを二度も回してしまったので、少し不格好に見える。 Haskellはこんな感じ?

import Control.Monad
import Data.List

main = do
  s <- replicateM 10 (readLn :: IO Int)
  mapM_ print $ take 3 $ reverse $ sort s

main = do でちょっと手続き型っぽくなってる。よくないのかな。
forを回さなくていいのはスマートで好き。

この問題とか、ジャンルみると高校生用の問題って書いてあった。
もう少し難しそうなのにチャレンジしよう。
個人的に気になるのが参照透過性のせいで動的計画法のような状態更新を伴うようなアルゴリズムは使いにくいのではないかということなのだけれど、Stateモナドを使ってなんとかするんだろうか。

DPL_1 A

コイン問題 | 動的計画法 | Aizu Online Judge

これ。
最初は動的計画法の表を管理するためのクラスをちゃんとつくったのだけれど、そういうのなしで次みたいに行を走査していけば良いのだ。

from itertools import product

value, variety = map(int, input().split())
coins = list(map(int, input().split()))
dp = [float("inf") for _ in range(value + 1)]
dp[0] = 0
for (c,j) in product(coins,list(range(value + 1))):
    if c <= j:
        dp[j] = min(dp[j], dp[j - c] + 1)
    else:
        dp[j] = dp[j]
print(dp[value])

に対して、Haskell
Haskell動的計画法を解決する方法としては、Arrayを用いる方法とStateモナドを用いる方法があるらしい。
Arrayを用いる方法が非常にエレガントなので、それをやってみた。
参考。

Arrayで動的計画法 - Journal InTime(2011-12-23)

こんな感じになった。

import Data.Array
import Control.Monad

readS :: String -> Int
readS s = read s::Int

zeroOrPlus :: Int -> Int
zeroOrPlus value
    | value < 0 = 0
    | otherwise = value

solveDP::[String] -> Int
solveDP [status, coins] = let
  [value, variety] = map readS (words status)
  coin = map readS (words coins)
  matrix = array ((0,0),(value, variety)) $
       [((0,0),0)] ++
       [((x,0),500) | x <- [1..value]] ++
       [((0,y),0) | y <- [1..variety]] ++
       [((x,y), matrix!(x,y-1))
       |  y <- [1..variety], x <- [1..min value (coin!!(y-1) - 1)]] ++
       [((x,y), min (matrix!(x,y-1)) (matrix!(x-coin!!(y-1),y) + 1))
       | y <- [1..variety], x <- [zeroOrPlus (coin!!(y-1))..value]]
  in last $ elems matrix

main = do
  [status, coins] <- replicateM 2 getLine
  print $ solveDP [status, coins]

表の各要素の値を記述するだけなので、結構良い。エレガントな感じがする。
しかしながら、これを提出するとテストケースの途中でメモリ使いすぎだよ!と言われてacceptしてもらえなかった……
どうも遅延評価で何度も計算するとか、いろいろ問題がありそう。
そこら辺を考えるとやはりStateモナドを使うべきか。
また今度書きなおそう。

Unity(五月祭)

C#からシェルコマンドを叩くというか、popen的な事をするのがどうも予想外に面倒臭そうなのでアセットにあったjavascriptのランタイムを埋め込む方向でいこうと思う。
面倒くさいぞ。

雑記

下半身のトレーニング、した。
写真の模写してたやつに色つけた。
やっぱり色つけが下手。練習しないとですね。
次はイラストの模写→風景写真の模写→オリジナルみたいな感じでいこう。