Hatena::Grouptopcoder

hotpepsiの練習帳

2014-05-11

SRM 616

| 23:09

Div1 Easy (250) WakingUp

問題

  • Alexの眠さをSとする
  • 毎分眠さはD増加する
  • N個のアラームがあり、開始時刻、間隔、ボリュームが与えられる
  • アラームが鳴ると眠さがボリュームのぶんだけ減る
  • 眠さが0以下になると起きる
  • 初期値Sのうち、起きることができる最大値を求める
  • 任意のSで起きることができるなら-1

方針

  • 変化には周期性がある。periodのLCMになるはず
  • 増える一方の場合には最初から0でないと起きられない
  • S=0からシミュレーションして、最小値を符号反転したものが答え
  • Failed System Test
  • 最初と次の2520(1..10のLCM)分でシミュレーションをしてみて、最小値が低くなっていれば、任意の数で起きられる
  • そうでなければ、最小値を符号反転したものが答え
  • https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_616/WakingUp.cpp

Div2 Hard (1000) TwoLLogo

問題

  • LL株式会社は、ロゴをデザインしようとしている
  • N×Mの升目の中に二つのLを含む必要がある
  • それぞれの升目は白か黒に塗られている
  • 白い部分にLを二つ配置する組み合わせの総数を求める

方針

  • 各座標のLの縦棒(上方向)と横棒(右方向)の最大の長さを求めておく
  • 最初に置くほうの座標、上の長さ、横の長さ、あとに置くほうの座標で全探索 O(N^6)
  • 後置のL字の組み合わせ(縦棒×横棒=組み合わせ数)を足していく
  • ただし、自分より上か、同じ高さで自分より右にあるものにすることで、同じ組み合わせを一回だけ数えるようにする
  • 前置の縦棒に後置の横棒がふれる可能性があるときは、前置より左に置くときに、横幅の組み合わせを制限する
  • https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_616/TwoLLogo.cpp

結果

x-- +2 0+100pt = 100pt 348/816th rating 1477 -> 1513 (+36)

周期とシミュレーションという問題はあまりないパターン。

0点だが一生懸命写経したら2年ぶりに黄色になれた。

復習が追いついたらdiv1 mediumに挑戦していきたい。


http://togetter.com/li/653487

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20140511

2014-05-08

SRM 615

| 02:33

Div1 Easy (250) AmebaDiv1

問題

  • アメーバのモンテカルロは、自分と全く同じ重さのゼリーだけを食べる
  • ゼリーを食べると体重が2倍になる
  • ゼリーの重さが出現順に与えられる
  • モンテカルロが到達しない重さの組み合わせの総数を求める

方針

  • ゼリーに含まれない大きさだったときは何も食べないので無関係
  • ということはゼリーに含まれる大きさだけを考えればいい
  • 元々の大きさがaだったとき、最終的にa*2^nになるので、aが到達しない候補となる
  • a*1/2のゼリーが含まれているとaになることがあり、それを候補から除外する
  • まずゼリーに含まれる大きさにそれぞれについてシミュレーションしておく
  • ゼリーに含まれる大きさのうち、到達しないものを数える
  • Passed System Test
  • https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_615/AmebaDiv1.cpp

結果

o-- 211.75pt 323/727th rating 1439 -> 1477 (+38)

落ち着いて解けた。なかなか良い点数。

乱数は出てこなかった。


http://togetter.com/li/650989

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20140508