Codeforces Beta Round #36 - pes

2回目のCodeforces format。そして初めてのHacked…orz

問題：与えられた01列に出現する1が等間隔に現れてるかを判定する

問題：与えられたn×nの図形を(k-1)回フラクタル展開した結果を出力する

問題：円錐を切り詰めた形状のボウルを順に重ねていったときの高さを出力する

重ねる順にボウルの底面半径r、口径R、高さhが与えられる。
- 1≦r＜R≦10000かつ1≦h≦10000
- ボウルの個数nは3000以下
2つのボウルを重ねるときの位置関係は、
- 重ねたボウルが下のボウルの内部にすっぽり入る
- 重ねたボウルの底面が下のボウルの内部で引っかかる
- 重ねたボウルの側面が、下のボウルの口に引っかかる
- 重ねたボウルの口が内部で引っかかる
- 重ねたボウルが下のボウルに完全にのっかる
とりうる各パターンのうち一番高さが上になるパターンが重なった結果
複数重ねていくときは、
- 重ね済みの各ボウルに対し、重なった結果を計算する
- 計算したもののうち、一番高さが上になるパターンが重なった結果
- 1つのボウルに対して前のボウルを全部みるので全体でO(n^2)
O(n^2)なら間に合うだろうと踏んで提出した

問題：n×mの盤面の左上のマスに駒が置いてあって、2人交互に「1マス下へ」or「1マス右へ」or「下と右にKマスずつ移動」のどれかを選んで駒を動かす．駒が動かせなくなったら負けとするとき、与えられた盤面が先手必勝かを判定する

K、n、mも10億以下とやたら大きいので全探索は無理
Nimに帰着するのかなぁ…とちょっとだけ考えてその方針は諦める
とりあえず小さい範囲で全探索して規則性を探すといういつものパターンに
- kマス間隔くらいで必勝が並んでるように見える
- それ以外は勝ちと負けがチェッカー模様に並んでるように見える
- 必勝列を超えるとチェッカー模様が反転するように見える
良く分からないので見たままに実装し、提出。
…したところ終了間際にHackされて試合終了。
K=1だとチェッカー模様の反転が起こらないとか何とか。ぐぬぬ…。

結果：0:10(480, +0) / 0:26(896, +0) / 1:21(964, +1) / Hacked / -- ，40位
レーティング：1942 -> 1942

実装に時間がかかってしまった問題が多かった気がしますが、
CやDがシステムでごっそり落ちていて順位はいつもくらいでした。
レーティングはこのくらいで横ばいのようです。