Google Code Jam 2011 予選問題を解いてみた - プログラミング上級者を目指して

ようやくGCJ2011の予選の問題を全てHaskellで解けました。
解いた順番に書きます。

C. ビット数

与えられた数字を2つの2進数の和で表す時に、1の数を最大化する問題。
唯一自力で解けた問題です。与えられた数字を2進数に直し、下の位から見ていき、一意的に解が求められます。
問題自身にはあまり関係ないですが、Debug.Traceモジュールのtrace関数を使って

func arg1 arg2 ... = body

のような関数をprintデバッグしたいときには、

func arg1 arg2 ... = trace (出力内容) (func2 arg1 arg2 ...)
func2 arg1 arg2 ... = body

という風にやると簡単に出来ます。

ソースコード

i2B n c
	| n > t = i2B n (c + 1)
	| n == t = 1 : int2Bit (n - t) [2^x | x <- [0..]] (c - 1)
	| otherwise = int2Bit n [2^x | x <- [0..]] (c - 1)
	where t = 2^c

int2Bit n bit c
	| c < 0 = []
	| n >= bit !! c  = 1 : int2Bit (n - bit !! c) bit (c - 1)
	| otherwise = 0 : int2Bit n bit (c - 1)

solve ar n carry
	| n == 0  = 1 - carry
	| ar !! n == 0 = 2 - carry + solve ar (n - 1) 1
	| otherwise = 1 + carry + solve ar (n - 1) carry
ans ar = solve ar ((length ar) - 1) 0

doIt c n 
	| n > 0 = do
	l <- getLine
	putStrLn $ "Case #" ++ show c ++ ": " ++ (show $ ans (i2B (read l) 0) )
	doIt (c + 1) $ n - 1
	| otherwise = return()
	
main = do
	l <- getLine
	doIt 1 (read l)

A. カードシャッフル

カードシャッフルを数回行った際に上からw番目のカードの始めの位置を求める問題。
Largeではカード枚数が10億枚もあるので全てのカードの位置を覚えるのは無理。どうするのか全く分かりませんでしたが、解説によると最後から逆に考えていけば良いとのこと。

リストを作る際に1 : [2, 3]で[1, 2, 3]のリストを作れますが、[2, 3] : 4で[2, 3, 4]のリストは作れないようです。
あと、getLineを使う関数では戻り値を整数とかには出来ないようです。IO関係を使った関数はIO以外を戻り値には出来ないみたいですね。

ソースコード

import Control.Applicative

getArgs str = map (read :: String -> Int) (words str)
makeA str array = ((ar !! 0) , (ar !! 1)) : array
	where ar = map read $ words str

makeCut c ar w n
	| 0 < c = do
		l <- getLine
		makeCut (c - 1) (makeA l ar) w n
	| otherwise = doCut ar w 0 n

doCut ar pos c n
	| c >= length ar  = putStrLn $ "Case #" ++ show n ++ ": " ++ show pos 
	| pos <= snd (ar !! c) = doCut ar (fst (ar !! c) + pos - 1) d n
	| pos < fst (ar !! c) + snd (ar !! c) = doCut ar (pos - snd (ar !! c)) d n
	| otherwise = doCut ar pos d n
	where
		d = c + 1
		
doIt n count
	| count <= n = do
		[m, c, w] <- getArgs <$> getLine
		makeCut c ([] :: [(Int, Int)]) w count
		doIt n $ count + 1
	| otherwise = return()

main = do 
	l <- getLine
	doIt (read l) 1

まず、Mapでkeyに対応するvalueを返す関数lookupの戻り値がvalueの型でないんですね。何故かMaybeモナドに包まれています。
何で？と思って調べてみると、Maybeモナドというのは、簡単に言うと戻り値がない場合も対応できるモナドだそうです。Mapの中に求めるkeyがない場合があるので、lookupはMaybeモナドに包まれているのでしょうか。
Maybe a型をa型にするには、Data.MaybeモジュールのfromJust関数を使います。

次にHaskellはC++やJavaに比べてまだライブラリが少なく、MultiMap(keyの重複を許すmap)がありません（一応外部提供のMultiMapライブラリはあるみたいです）。仕方ないので自分でMapをMultiMapに改造することにしました。
具体的にはあるkeyでmapに新たに入れる時に、そのkeyが既にmapに含まれていたらkeyに1未満の小さい数εを足してmapに入れます。keyの値を見る時はfloor keyとしてkeyの小数点以下を切り捨てにすることでMultiMapと同じ機能に出来ます。

IntegerをDoubleに変換するにはどうすればよいのか？
これはソースコードのi2d関数のように整数にfromIntegral、toRational、fromRationalの順番に関数を
適用すればよいです（多分もっといい方法がありそうですけど・・・）。

Mapに足すεですが、イベントの数 * ε < 1であればよいです。イベントの数は高々コーヒーの種類 * 2なので、ε < 1 / 200 であればよいはずですが、念のために0.0001にしてみました。しかし、これだとなぜかkeyが10^12のときにMapが上手く動かず止まってしまいました。10^12の前では10^(-4)は無視されてしまうんでしょうか？？ε = 0.001にしたら上手く動きました。

しかし、Haskellではこういう複雑なプログラムは型の条件が厳しいので大変です・・・。

C. ビット数

A. カードシャッフル

B. カードシャッフル