POJ Monthly Contest 2009.05.17.

PKU Campus 2009らしい。朝なのはそのせい？

A

(2000×2000以下の格子の街です。右折と直進だけできます。同じところを二度通れません。角から目的地まで何通りの行き方がありますか)
右折回数から上下左右を通る回数が求まるので二項係数で。
[accepted at 03:00:13]

B

(4×4以下の絵を、ペイントの塗りつぶし機能を使いまくって真っ黒にします。最小回数の方法を1つ求めてください)
めんどい探索っぽかったので放置。
[opened]

C

(長方形の建物が20個以下あります。影の方向が決まっています。影な面積を求めてください)
多角形の共通部分ライブラリ作らないとなあ。
[opened]

D

(10^9個以下を4色で塗ります。赤と青緑は偶数個に使います。何通りですか)
最易問その1。4×4行列n乗。
[accepted at 00:27:40]

E

(駒たちがあって、一定範囲に近づくとSniperに銃を打てて、ダメージを与えかつ一定時間停止させられます。Sniperを倒せますか)
greedyでよい。図を見て縦以外に動けないと勝手に勘違いしていたorz
[accepted at 04:36:11 / 1 wrong try]

F

(100個以下の値に対して、どれかを1増やす、どれかを0にする、どれか2つを入れ替えるという操作100回以下、という一連の手順を10^9回以下やります。結果どうなりますか)
最初行列作ってm乗してたらTLEを食らったが、よく考えたら置換で周期を考えれば十分だった。
[accepted at 02:11:57 / 8 wrong tries]

G

(表面積Sで体積最大の円錐を求めてください)
最易問その2。黄金探索した。
[accepted at 00:43:15]

H

(5段以下のピラミッド状に並んだトランプを1枚ずつ消したりします。得点の期待値を求めてください)
適当にメモ化再帰したらTLEがもらえた。これ以上の方法あるのかなあ。
[3 wrong tries]

I

(縦線たちと横線たちと点たちがあります。内部or周上に点を含む正方形はいくつできていますか。縦線数・横線数・点数・座標は1000以下です)
いろいろ解き方はありそう。
自分の方針は、正方形の左下を固定して、どこまで伸ばせば点が入るかを二分探索。点が入る範囲で右上になる場所がいくつあるかは予めDPしておけばよい。これでO(n^2logn)で解ける。
[accepted at 03:25:21 / 3 wrong tries]

Result

6完最下位(18:24:37)の4位。
簡単めだった気がしますが強い人は少なかった気がします。解けるべきなのは解けてよかったです。