Google Code jam Japan が開催されるようですね。
練習用の問題が公開されているようなので、腕試しに解いてみました。
問題は以下のとおりです。
https://code.google.com/codejam/contest/dashboard?c=1343486
問題 Snapper はちっちゃな電化製品で、片側に入力プラグ、反対側に出力ソケットがついています。 この出力ソケットには、電球などの電化製品や、他の Snapper の入力プラグを接続することができます。 Snapper は ON か OFF の状態を持っていて、状態が ON で入力プラグから電力を受け取っているときのみ、 出力ソケットに電力が供給されます。 また、あなたが指をパチリと鳴らすと、その破裂音に反応して、 入力プラグから電力を受け取っている Snapper は ON/OFF の状態が切り替わります。 ある日、私は N 個の Snapper を買ってきて、1 個目の Snapper の入力プラグを電源ソケットに接続、 2 個目の Snapper の入力プラグを 1 個目の出力ソケットに接続、といった要領で数珠つなぎにし、 N 個目の Snapper の出力ソケットに電球を取り付けました。 はじめの状態では、Snapper はすべて OFF で、1 個目の Snapper のみに電力が供給され、電球は付いていません。 一回指を鳴らすと、1 個目の Snapper は ON になり、2 個目の Snapper に電力が供給されます。 もう一度指を鳴らすと、1 個目と 2 個目の Snapper の状態が切り替わり、2 個目の Snapper は ON であるものの 電源が供給されていない、という状態になります。 3 回目には、1 個目の状態が切り替わり、 1 個目と 2 個目の両方が ON になります。 もし、ここで 2 個目の出力ソケットに電球が接続されていたとすると、 電球が光ります。 私は指を何時間にもわたって鳴らし続けました。 指を K 回鳴らしたとき、果たして電球は光っているでしょうか？ 電球は仕掛けのないどこにでもあるようなもので、直前の Snapper から電力を供給されているときにのみ光ります。 入力 1 行目にはテストケースの数 T が含まれています。その後ろに T 行が続きます。 それらの行にはそれぞれ 2 つの整数 N と K が含まれています。 出力 各テストケースにつき 1 行、 "Case #X: Y" と出力してください。 ただし、X は 1 から始まるテストケースの番号です。 Y は電球が光っているかどうかで、光っているならば "ON"、消えているならば "OFF" としてください。 制約 1 ? T ? 5000 Small 1 ? N ? 10 0 ? K ? 100 Large 1 ? N ? 30 0 ? K ? 108
解法となるコードです。
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 | {-# OPTIONS_GHC -O2 -optc-O3 -optc-ffast-math -cpp #-} {-# OPTIONS_GHC -funbox-strict-fields -fexcess-precision -monly-3-regs #-} {-# LANGUAGE BangPatterns, OverloadedStrings, ScopedTypeVariables #-} {-# LANGUAGE NoMonomorphismRestriction #-} module Main where import Control.Applicative import Data.List import Text.Printf import Control.Monad splitBy :: (a -> Bool) -> [a] -> [[a]] splitBy p [] = [] splitBy p xs = a : (splitBy p $ dropWhile p $ b) where (a, b) = break p xs split :: String -> [String] split = splitBy (==' ') input = lines <$> readFile "/Users/oskimura/Downloads/A-large-practice.in" -- input = lines <$> getContents f n k = if (k+1) `mod` (2^n) == 0 then "ON" else "OFF" main :: IO () main = do { (count:tests) <- input ; let tests' = (map $ map ((+0) . read)) . (map split) $ tests in writeFile "output.txt" . foldr1 (++) . (zipWith (\x y -> ("Case #"++(show y) ++ ": "++ x ++ "\n"))) ((map (\x -> f (x!!0) (x!!1))) $ tests') $ [1..] } |