Hatena::Grouptopcoder

tanakhの日記 このページをアンテナに追加 RSSフィード

 | 

2010-05-10

Google Code Jam 2010 Qual

09:58 | Google Code Jam 2010 Qual - tanakhの日記 を含むブックマーク はてなブックマーク - Google Code Jam 2010 Qual - tanakhの日記 Google Code Jam 2010 Qual - tanakhの日記 のブックマークコメント

Haskellを全世界に広めるというサイモンとの約束を果たすために私は、Haskellのみを用いてトップ25に残らねばならないッ!

とりあえず...

Qualification Roundです。時間が24時間もあるので、どうにでもなります。一応全部通しました。今後のためのテンプレート作成などもぼちぼち考える。

サブミットしたソースなどは下記リンクより。

http://code.google.com/codejam/contest/scoreboard?c=433101#sp=1001

A

一回の操作で、1*0 というパターンが 0*1 に変わる。これは整数のインクリメントに他ならない。ゆえに、K`mod`(2^N) == 2^N-1 かどうかを調べればよい。

import Control.Monad
import Control.Applicative
import Text.Printf

gcjMain f m = do
  n <- readLn
  dat <- replicateM n m
  forM_ (zip [1..n] dat) $ \(i, d) -> do
    printf "Case #%d: %s\n" i (f d)

main = gcjMain solve $ map read . words <$> getLine

solve [n, k]
  | k `mod` 2^n == 2^n-1 = "ON"
  | otherwise = "OFF"

B

なんだか難解な問題文が書いてあるが、要するに、与えられた整数列に同じ数を足して、gcdが最も大きくなるようにすればいいらしい。ただし、入力は50桁ぐらいある。

同じ数を足した後も差は変わらなくて、差もgcdの倍数になっているはずなので、要するに差のgcdをとってやれば良い。

Haskellには使い易い多倍長整数とgcdがあるので、とても楽。

import Control.Monad
import Control.Applicative
import Text.Printf

gcjMain f m = do
  n <- readLn
  dat <- replicateM n m
  forM_ (zip [1..n] dat) $ \(i, d) -> do
    printf "Case #%d: %s\n" i (f d)

main = gcjMain solve $ tail . map read . words <$> getLine

solve (x:xs) = show ((x+g-1)`div`g*g-x :: Integer) where
  g = abs $ foldl1 gcd $ filter (/=0) $ map (x-) xs

C

入力がやや大きいので、ちょっと怯む。全部回すのは流石にまずそうだ(実際のところ、普通に回せてしまうようだが…)。仮にできたとしても、Haskellでリストを用いた実装は不可能だし、O(1)でアクセスできる配列を用いるのも面倒くさい(これは練習しておかねばならないが)。

ループを検出して、ループを一気に進めてやれば良いかなと思って実装する。実装が意外と面倒くさい。Haskellでリストを書き換えながらループをするとか、Haskellらしからぬ気もする。というふうに書いているところで、もっと綺麗でかつ速い方法を思いついた。

n回先にどこに行くのかというのは、n/2回でどこに行くのかを計算すればそこから求まるので、結局ベクトルに対して高速な累乗のようなことをしてやれば一発で求まるのである。計算量はO(NlogR)。下記コードではリストを用いているのでO(N^2logR)になっている。

import Control.Monad
import Control.Applicative
import Text.Printf

gcjMain f m = do
  n <- readLn
  dat <- replicateM n m
  forM_ (zip [1..n] dat) $ \(i, d) -> do
    printf "Case #%d: %s\n" i (f d)

main = gcjMain solve $ do
  [r, k, n] <- map read . words <$> getLine
  gs <- map read . words <$> getLine
  return (r :: Int, k, gs)

solve (r, k, gs) = show $ snd . head $ mult incs r where
  n = length gs
    
  mult v n
    | n == 1 = v
    | n `mod` 2 == 0 = vadd v2 v2
    | otherwise = vadd (vadd v2 v2) v
      where
        v2 = mult v (n`div`2)
        
  vadd v1 v2 =
    [ (diff+ndiff, inc+ninc)
    | (i, (diff, inc)) <- zip [0..] v1
    , let ni = (i + diff) `mod` n , let (ndiff, ninc) = v2 !! ni ]
    
  incs = [ takek $ take n (drop i (gs++gs)) | i <- [0..n - 1]]
  takek gs = last $ takeWhile ((<=k).snd) $ scanl (\(c, a) e -> (c+1, a+e)) (0, 0) gs

TigerTiger2011/07/22 18:56Never would have thunk I would find this so idnipsensable.

rzutdarzutda2011/07/22 22:277qr6HB <a href="http://nkwdcmmrjgjo.com/">nkwdcmmrjgjo</a>

gmwkdoytpflgmwkdoytpfl2011/07/23 21:54sPXoEP , [url=http://ogopvlokvewo.com/]ogopvlokvewo[/url], [link=http://xwvscoubkmxr.com/]xwvscoubkmxr[/link], http://cnqtnbcjusgw.com/

kgdzzukgdzzu2011/07/25 20:40bTNxd1 <a href="http://atdblfahscal.com/">atdblfahscal</a>

dkyomfdaendkyomfdaen2011/07/26 00:49XyOs8q , [url=http://hoyqrsyjstup.com/]hoyqrsyjstup[/url], [link=http://jnkvmrbexcza.com/]jnkvmrbexcza[/link], http://pfqbfhemeijo.com/

トラックバック - http://topcoder.g.hatena.ne.jp/tanakh/20100510
 |