Google Code Jam 2010 - Qualification Round

今年も参加してます。予選だしあまり言うこともないのですが、せっかくなのでコードを晒しときます。
去年のコードと比べると、ゴルフの影響を受けすぎ（悪い意味で）。もうちょっと可読性を大事にする人間だったはずなのですが・・・。
ともあれ Haskell で解けるというのはウレシイ限りです。

A

最初、問題の意味がぜんぜん分かりませんでした（snapper って何だよ！）。分かれば簡単。2 進表記で指定された桁以下が全部 1 かどうか答える。

main=interact$unlines.zipWith(++)["Case #"++shows i": "|i<-[1..]].map(f.map read.words).tail.lines
f[n,k]=["OFF","ON"]!!(0^mod(k+1)(2^n))

B

与えられた数列の周期を求めて、0 以上の最小値を答える。これもまぁ簡単。

main=interact$unlines.zipWith(++)["Case #"++shows i": "|i<-[1..]].map(f.map read.words).tail.lines
f(_:x:ys)=show$mod(-x)$foldl1 gcd[abs$x-y|y<-ys,y/=x]

C

グループ単位でジェットコースターに乗るのを繰り返すとき、何人乗れるか答える。Small はともかく Large で 10^8*1000 ってフツウにやったら終わらないよなぁ、面倒だなぁとか思いながら書いてみたら、やっぱりものすごく面倒でした。なぜこの問題だけ？
人数のリストが途中から循環するので、循環が始まる点を適当に求めて、それ以前／以後で場合分けして求めてます（6 〜 7 行目の a というやつがそれです）。さすがにこれはもっと簡単に書けるのでは。他の人のコードを読みたい。

import Data.List
main = interact $ unlines.zipWith(++)["Case #"++shows i": "|i<-[1..]].f.map(map read.words).tail.lines
f([r,k,n]:g:x) = show a : f x
  where
  -- 求める人数は循環前の部分の人数＋循環部の人数（完全に一周する分）＋循環部の人数（途中まで辿る分）
  a | r>d0 = sum g0 + sum g1*((r-d0)`div`d1) + sum(genericTake((r-d0)`mod`d1)g1)
    | otherwise = sum $ genericTake r g0
  -- d0, d1 は g0, g1 の長さ
  [d0,d1] = map genericLength[g0,g1]
  -- g0, g1 は人数のリストの、循環前の部分と循環部
  [g0,g1] = map(snd.unzip)[g0'',g1'']
  g1'' = b : takeWhile(/=b)g2''
  (g0'',_:g2'') = span(/=b)g''
  -- b は循環部に含まれる点。ここから循環部が始まるとする。
  b = g''?tail g''
  -- リストの循環部に含まれる点を見つける。ウサギとカメのロジック
  (x:xs)?(y:_:ys)
    | x==y = x
    | otherwise = xs?ys
  -- g'' の要素は一度にコースターに乗れる人数（ID つき）
  g'' = (0!0)g'
  -- 一度にコースターに乗れる人数を求めてリストにする。
  (s!m)((i,x):y)
    | s+x>k||m+1>n = (i,s) : (0!0)((i,x):y)
    | otherwise = (s+x)!(m+1) $ y
  -- グループのリスト g に ID を振る
  g' = cycle $ zip[0..]g
f _ = []