The First KMCMonthly Contest

KMCoder

ICPC夏合宿の問題。5時間10問。
以下、通せたものは通した順に、自分がやったこととかです。
詳しい解説はwataさんのところ(http://d.hatena.ne.jp/wata_orz/20090922)とかを参照してください。

E

MPは移動コストに入れてしまえばよい。状態はHW×2^8で持って、1秒かかる動作のコストを1+popcountみたいにする
81/1

G

マンハッタン距離なのでX+Y,X-Y,-X+Y,-X-Yの4つを考えればよい。
直線たちとクエリたちをソートしておけば、それ以降はdequeを使って線形で解ける。
不等号の向きを間違えたりして混乱した。
100/4

J

実はやるだけだった
118/1

D

後ろからやれば終わり
182/0

I

与えられた場所のうち、縦に繋がっている連結成分を頂点、横・斜めに繋がっている関係を辺として平面的グラフを作れば、その穴の数を求めることになるので、Eulerの公式で求まる。
見事に非連結を忘れてWAをもらったｗ
205/1


以下コンテスト中解けなかったものたち

F

部分和たちから2つを選んだときのXORを最大にしましょうという問題。
後ろから見てBITでも使えばN×log(2^20)で終わる。
ひたすらバグっていた

A

似たのをよくやっているのにさっぱりだった

B

勉強になった

C

フローじゃね？と思ったがよくわからなくなったので放置していた

H

見たことがあったがそもそも解けていないうえに複数解判定までしないといけないので放置していた

Results

5完で2位。
EとかIとかが人気なくてsubmitしたのすら自分だけでした。
しかしこの結果だけ見ると1位の人とチーム組めばいいじゃんと頻繁に言われるのも仕方ない感じですね。