hotpepsiの練習帳

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