hotpepsiの練習帳

SRM 596

math | 23:26

Div2 Easy (250) FoxAndSightseeing

問題

• N個の都市の位置が与えられる
• 一つだけ飛ばしてN-1個の都市を順番に観光したい
• 移動距離の最小値を求める

方針

• 全て試す
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_596/FoxAndSightseeing.cpp

Div2 Medium (500) ColorfulRoad

問題

• RかGかBの升目がある
• R→G→Bの順に進まなければならない
• 移動コストは距離の二乗
• 左端から右端に移動するコストの合計の最小値を求める

方針

• 到達可能な場所についてコストを更新するDP
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_596/ColorfulRoad.cpp

Div2 Hard (1000) SparseFactorialDiv2

問題

• F(n) = (n - 0^2) * (n - 1^2) * (n - 2^2) * (n - 3^2) * ... * (n - k^2) とする
• 除数Pが与えられる。(ただしPは素数)
• lo以上hi以下のnについて、Pで割り切れるF(n)の個数を求める

方針

• F(n)はk+1個の項からなる。いくつか列挙して眺めてみた
• Pが素数なので、項同士の掛け算でPの倍数になるケースを考えなくてよい
• a番目の項をn-a^2=xとして、1からxまででPの倍数になるものはx÷P個ある
• aを1ずつ増やしていき全列挙する。aは2乗で増えていくのでせいぜい数十回列挙するだけ
• ただし、それまでに列挙したaと同じものは数えない。同じとは、n-a^2の余りが同じもの(P^a≡P^bのとき、Pの倍数になる位相が同じなので重複する)
• 倍数の個数を求める関数をG(n)とするとG(hi)-G(lo-1)が答え
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_596/SparseFactorialDiv2.cpp

Div1 Easy (250) IncrementAndDoubling

問題

• 要素数がNの配列が与えられる
• どれかの要素を+1するか、全ての要素を2倍にすることができる
• 初期値を0として、その配列と同じにするまでの最小の手数を求める

方針

• 1を足すより倍にするほうが効率的なので、最小限必要な数だけ足して倍にするはず
• 逆に0に戻すことを考える
• 2で割り切れない場合は1をひく
• その他は2で割る
• 全てゼロになったら終了
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_596/IncrementAndDoubling.cpp

結果

ooo 241.53 + 426.74 + 617.78 = 1286.05pt 8th/1153 rating 1088 -> 1236 (+148)

hardが通ると気持ちがいいですね。