Hatena::Grouptopcoder

TopCoder煮ブログ

本家ブログはこっち → http://d.hatena.ne.jp/nitoyon/

2008-10-29

SRM423 DIV1

| 11:56 | SRM423 DIV1 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM423 DIV1 - TopCoder煮ブログ

撃沈。むずい。

15141459

0点だからしかたなし。

TheTower

題意がつかめず撃沈。普通に解いても爆発するので、何らかの工夫が必要なんだろうが思いつかん。

TheEasyChase

素直に書いてみたが何らかのバグがあり撃沈。たぶん、バグがなくても時間内に終了しなかったと思われる。

(追記) 結果がでたあとに、同じ room 内の人に適当に自分が考えた Test case(盤面が20x20で適度に追いかけっこが発生するもの)を与えると撃沈した。ダメもとで乱発すればよかったのかもしれん。

TheBeautifulBoard

一瞬見たが諦め。

TheTower (SRM423 DIV1 Easy)

| 00:35 | TheTower (SRM423 DIV1 Easy) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - TheTower (SRM423 DIV1 Easy) - TopCoder煮ブログ

chokudai さんに教えてもらったあとにじっくり考えて理解。

気付けば簡単なんだが・・・。

  1. x, y を独立に考えられる
    • マンハッタン距離なので、点が集まる座標は x と y を別々に考えてよい。
    • 以下の 2. では x 座標を求めることを考える(例0のパターン)。
  2. 集まる先の x 座標は n 個の点の x 座標のうちのどれかだと考えてよい
    • 例えば、2個の点だと、x0~x1 の間の全ての x 座標がありうる
    • 例えば、3個の点だと、x0 < x1 < x2 だとすると、最終的な座標は x1 以外にはありえない
      • x1 + 1 と x1 までの移動距離の違いを考えてみると分かりよい。
      • x1 に比べて、x1 + 1 は点0、点1 の2つが余計に1つ右に動き、その分、点2 の移動分が1つ減る。よって、x1 + 1 は x1 までに比べて、1つ移動量が多い。
      • 同様に、x1 に比べて、x1 - 1 は1つ移動量が多い
    • このように、必ずどれか1つの x 座標か、隣接する2つの x 座標の間に集まる(必ずしも中央の点に集まるわけではなさそう)
    • だから、n 個の点の x 座標のうちのどれかだと考えてよい(間になる場合はその両端のどちらかだと考えて無視していい)
  3. n 個の点の x, y を全て組み合わせた n^2 通りの座標について調べればよい
    • n 個の中から i 個の全ての組み合わせに対して移動距離を求めるのは大変
    • 魔法の作戦がある!
      • n 個の点のそれぞれと最終地点の距離を調べてソートする
      • ソート結果の最初の2つを足したものは、min(nC2の点から最終地点までの距離の和)である
      • 最初の3つを足したものは…以下同じ
  4. n^2 通りについて最小の移動距離が求まるので、その全ての点のうち最小のものを返せばよい

これを3分台で解ける人がいるのが理解できない……。