Google Code Jam Round 1B

前回の続き。
http://code.google.com/codejam/contest/dashboard?c=agdjb2RlamFtchALEghjb250ZXN0cxin2QUM

Smallを三つ一問三十分ペースで出して終了。
一応次には進めるようですが、あまりにも厳しい…。

A

格子点上に点がいっぱいあって、そのうち三つを頂点とする三角形のうち
重心が格子点にあるものの数を求めよ。点の数は100000個。と言う問題。
重心が別の点に乗っているものの数、と条件を読み違えてて、
こんなもんどうやって解くんじゃろって思いながらとりあえずSmall向けコード書いてたら
答えが合わなくて、うんうんうなりながら問題を読み直したら
やっと気づいた。そのままBに。

B

ある区間の数を、p以上の共通の素因数を持つ数同士を同一グループとする操作を行うと、
いくつのグループに分かれるか、と言う問題。区間の幅は10^6以下で、数の絶対値は10^12以下。
問題の解読が難しくて、途中まで公約数がp以下と思っていてそのままSmall向けコード書いてて、
これまた全然合わんなあと思いつつ問題を読み返して間違いに気づく。
読み間違いに気づいたときにそんなら普通にLarge通るコードかけるなあと思ったけど、
目先の10ptを優先する。

C

カードがK枚あって、上から一枚ずつ取り出して下に回していくのだけど、
1枚目、次にそこから数えて2枚目、そこから数えて3枚目、そこから数えて...のカードは
下に回さずに捨てていく。最初上からdi枚目にあったカードは何回目に捨てられますか?
Kは100万まで。


なぜLargeを通さなかった。
Data.Sequenceを使うだけじゃないか。
なんでだ…なんでだ…
馬鹿過ぎる…
自分のふがいなさに失望…

{-# LANGUAGE BangPatterns #-}

import Control.Monad
import Data.List
import qualified Data.Sequence as S
import qualified Data.Map as M
import Text.Printf

gcjMain m = do
  c <- readLn
  forM_ [1..c] $ \i -> do
    printf "Case #%d: " (i::Int)
    m

main = gcjMain $ do
  k <- readLn
  _:ds <- liftM (map read . words) getLine :: IO [Int]
  let s = S.fromList [1..k]
  let ps = go k 0 0 s
  let mm = M.fromList $ filter (\(x,_) -> x`elem`ds) ps
  putStrLn $ unwords $ map show $ map (\i -> mm M.! i) ds

go !k !i !pos s
  | k==i = []
  | otherwise =
    let ix = (pos+i)`mod`(k-i) in
    (S.index s ix,i+1) : go k (i+1) ix (S.take ix s S.>< S.drop (ix+1) s)


そんなことを考えもせず、その時はC++でSmallを通すせこいコードをかいて、
しょうもないバグを入れまくり、
せこくSmallを通して満足。
35ptというのに日和ったか。


それから残った時間でBのlargeを解くのを書いてたのだけど、
バグ三昧で通らず…。
なにをやっているのだか…。
Aは終わった後に考えたら、3で割ったあまりで分類するだけだということに気づいた。
先こっちやるべきだったなあ。


うーん、しかし何ともパッとしない結果であった。
ちょっと前では考えられないほどコードにバグも入れてしまうし。
年齢による衰えかなあ。