日々の流転

λ. Google Code Jam 2010 Qualification Round

問題はそんなに難しい問題ではなかったのだけど、思いの他苦戦してしまった。 次のラウンドには一応進めたけれど、感覚が鈍ってるなぁ……

• Participant Details: sakai ― Code Jam 2010 Statistic

A. Snapper Chain

3問のうち一番苦戦したのがこの問題。 最初に書いたのは以下のようなプログラムで、Smallは簡単に解けるのだけど、Largeの上限のデータとかを生成して食わせると、とても終了しない。

{-# LANGUAGE Rank2Types, ScopedTypeVariables #-}
import Data.Array.ST
import Control.Monad
import Control.Monad.ST
import Text.Printf

f :: forall st. Int -> Int -> ST st Bool
f n k = do
  (power :: STUArray st Int Bool) <- newArray (1,n+1) False
  (state :: STUArray st Int Bool) <- newArray (1,n) False
  let updatePower = do
        writeArray power 1 True
        forM_ [2..n+1] $ \pos -> do
          b1 <- readArray power (pos - 1)
          b2 <- readArray state (pos - 1)
          writeArray power pos (b1 && b2)
      updateState = do
        forM_ [1..n] $ \pos -> do
          isPowered <- readArray power pos 
          when isPowered $ do
            isON <- readArray state pos
            writeArray state pos (not isON)
  updatePower
  forM_ [1..k] $ \_ -> updateState >> updatePower
  readArray power (n+1)

main :: IO ()
main = do
  t <- readLn
  forM_ [(1::Int)..t] $ \i -> do
    [n,k] <- liftM (map read . words) $ getLine
    printf "Case #%d: %s\n" i (if runST (f n k) then "ON" else "OFF")

Largeサイズの入力を扱えるようにと数回プログラムを書き直したが、その途中でトレースを表示して、初めて二進数のインクリメントになっている事に気づいた。 問題文の文章にちょっと騙された。

import Control.Monad
import Text.Printf
import Data.Bits

f :: Int -> Int -> Bool
f n k = and [testBit k i | i<-[0..n-1]]

main :: IO ()
main = do
  t <- readLn
  forM_ [(1::Int)..t] $ \i -> do
    [n,k] <- liftM (map read . words) $ getLine
    printf "Case #%d: %s\n" i (if f n k then "ON" else "OFF")

B. Fair Warning

Bは個人的には3問の中で一番簡単で、特に工夫は必要なかった。

import Control.Monad
import Text.Printf

f :: [Integer] -> Integer
f ts = (t - ((ts !! 0) `mod` t)) `mod` t
  where t = g ts

g :: [Integer] -> Integer
g ts = foldl1 gcd [ti - tj | ti <- ts, tj <- ts, ti > tj]

main :: IO ()
main = do
  c <- readLn
  forM_ [(1::Int)..c] $ \i -> do
    (n:ts) <- liftM (map read . words) $ getLine
    printf "Case #%d: %d\n" i (f ts)

【2010-05-27追記】 Google Code Jam 2010 Qualification Round — Scratch Leaf — MAYAH.JP によれば、上のソースのgは以下のようにすれば十分で、より少ない計算量で出来たらしい。そりゃそうだ。

g :: [Integer] -> Integer
g ts = foldl1 gcd [ti - t0 | ti <- ts', ti /= t0]
  where (t0:ts') = sort ts

C. Theme Park

最初に書いたのはC.hs。 Smallは当然解けるのだけど、甘い見積もりでLargeをダウンロードしてしまったら、時間内に解けなくて撃墜。 ちょっと工夫して、テーブル化して高速なべき乗法を使うようにしたら解けた(C2.hs)。 Largeはちゃんと性能的にも解けると確信してからダウンロードしないと駄目だなぁ。勿体無いことをした。 これは実際に参加してみて初めて感じた点。

【追記】 誰かがこの問題についてTwitterで「鳩ノ巣原理の良い例題」と書いていて*1、そのときは意味が分からなかったけど、後でku-ma-meさんに説明していて、そういう方法もあったと気づいた。