hotpepsiの練習帳

SRM 507 Div2

01:52

Easy (250) CubeAnts 蟻さん集め

問題

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

考察

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

実装

• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_507/CubeAnts.cpp

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

問題

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

考察

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

実装

• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_507/CubeStickers.cpp
• 他の人の実装を見たら、5色をチェックしていないものもあった。これは、ステッカーの枚数が6以上という前提条件を使っているっぽい。

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

問題

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

考察

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

実装 ※終了後解き直した

• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_507/CubeRoll.cpp

解説 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 やや増