Hatena::Grouptopcoder

hotpepsiの練習帳

2011-05-29

SRM 507 Div2

01:52

Easy (250) CubeAnts 蟻さん集め

問題

  • 蟻の位置がvector<int>で与えられる
  • 蟻の移動時間を返す

考察

  • maxを求める
  • 距離は静的配列で持っておけばOK

実装

Medium (500) CubeStickers サイコロ色塗り

問題

  • 六面体を、色が隣り合わないようにステッカーを貼る

考察

  • 反対側なら同じ色が使える
  • 色の種類 + 2つ以上ある色 の合計が6以上ならOK

実装

Hard (1000) CubeRoll サイコロ転がし

問題

  • n^2マス単位で動かすことができるすごろく

考察

  • わからなかったので、小さい数のとき総当りするコードを書いたが、時間内には間に合わず

実装 ※終了後解き直した

解説 https://topcoder-g-hatena-ne-jp.jag-icpc.org/ir5/20110529 を読んだ。素晴らしい!

開始点startから終点endまでの距離をrとしたとき、

  • 範囲が無限の場合
    • (x+1)^2 - x^2 = 2x+1 つまりrが3以上の任意の奇数であれば2でいける
    • (x+2)^2 - x^2 = 4x+4 つまりrが4の倍数であれば2でいける
    • rが4の倍数でない偶数の場合、a^2+b^2の可能性があるので、rの範囲で全探索する
    • ただし最大でも3
  • 範囲が有限(つまり下限と上限の穴がある)の場合
    • 全探索する
    • 最大値は不明

結果

oo- 237.63+394.43

落ち着いて解けたので、EasyとMediumが通った。rating 964 → 1030 やや増

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20110529