TopCoder SRM 465 - simezi

なんだか久しぶりな気のするSRM.
今回こそは1問目を早く解くぞと意気込んで臨んだ。ダメだったけど。

Easy

200-600-900セットらしい。一完ゲーの予感がしつつ問題文を読む。

塔をn個の格子点の候補の中から2つを選んで、それぞれの塔の中心がその格子点になるように立てる。
塔は正方形の形をしていてその向きは自由であるが、一辺の長さは自然数であり二つの塔が重なってはいけない。
このとき塔の辺の長さの組み合わせの場合の数を求めよ。

結局二つの正方形の辺が平行なときが辺が最大になりうる時だから、
中心間の距離をDとするとa+b≦Dを満たす自然数の個数を数えればいいのか。

えーと、aを1にするとbがD-1通りで2だとD-2通りでー……だからD*(D-1)/2通り？
書く。がりがり。
あれサンプル合わない。なんでだろ。ソース見直す。おかしくないなあ。
あ、a+b≦Dじゃなくてa/2+b/2≦Dじゃん。修正して……intのoverflowもおこらないし大丈夫だな。Submit。

Medium

Easyで時間食ってしまったorz
なんだかPKU演習の成果全然出てないなあ……むしろ問題解きつかれて思考鈍ってるような……などと考えつつ問題文を読む。

基地と発電所があって、これらをミサイルを打って破壊したい。基地につながる発電所すべてか基地自体をつぶすと基地の人が全部死ぬ（そんなこと書いてあったか不明）。
敵を全員殺すのにかかる最小のエネルギーを求めよ。

ん、なんか二部グラフっぽい。要するに頂点に重みのある最小辺カバー問題？
あれー重みがない場合を確かICPCゼミでやったような気がするんだけど、頂点に重みあるなんてどうしたらいいんだろ……

考える。全然わからない。NP困難じゃないのかこれ（←違う）
もうランダムケースでも作っておこう。フローじゃなくて探索してるっぽい子が居たら投げてやれ。

ランダムででかいケースを適当につくる。作った。テストに入れてみる。
ミサイル発射基地の座標に重複があるとか言われた。乱数を大きくする。あ、おｋ。

残り10分くらいだったので諦めてStandingをぼーっと眺めたり。

Hard

Unopen

Challenge

なんか探索っぽい気がするの居た！さっきの適当なのを投げてみる。
ちゃんと答え返してきた……

諦めて250の問題でおかしいの探す。
サンプルが親切だったからあんまりChallengeはないだろうなーと思ってたら予想に反してChallenge多めだった。皆どういうケースでミスってるんだろ。

結局撃墜できないまま終了。

Result

250はシステムテスト通った。撃墜1ミスで255位。
Div2に落ちるかなあとか思ってたらレート上昇だと……

どうも演習の成果が現れなかった感じで残念だった。
明日のCodeforcesも頑張ろう……！