Hatena::Grouptopcoder

hotpepsiの練習帳

2014-05-05

SRM 613

| 00:53

Div1 Easy (250) TaroFriends

問題

  • 猫がN匹いる
  • それぞれの猫の位置が一次元の座標で与えられる
  • 太郎が合図をしたら、全ての猫が右か左にXだけ動く
  • 最も左と最も右の猫の距離の最小値を求める

方針

結果

o-- 239.87pt 152nd/727 rating 1209 -> 1354 (+145)

ソートしたら簡単になる系。

悩まなかった。あとちょっとで240点。


http://togetter.com/li/645181

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

2014-04-16

SRM 608

| 00:38

Div1 Easy (300) MysticAndCandies

問題

  • N個の箱がある
  • それぞれの箱にはキャンディーがlow[i]~high[i]個入っている
  • キャンディーは全部でC個
  • X個以上食べるには何箱あければよいか

方針

結果

x-- 0pt 389th/741 rating 1242 -> 1227 (-15)

十分条件ではさむのって典型ぽいけど割と解けない。


http://togetter.com/li/626507

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

2014-04-11

SRM 605

| 02:36

Div1 Easy (250) AlienAndHamburgers

問題

  • エイリアンのFredは地球を滅ぼす前にハンバーガーを食べておくことにした
  • 種類とおいしさの配列が与えられる
  • 満足度は種類の数×おいしさの合計である
  • 満足度の最大値を求める

方針

  • 貪欲っぽい
  • (種類,おいしさの降順)でソート
  • ひとつずつ見ていき、同じ種類かつおいしさが正ならまとめる
  • まとめたあと、おいしさでソート
  • おいしさが正なら必ず増加する
  • おいしさが負で、総量が増加しないなら、次のを食べても増加することはない
  • おいしい順に食べて、食べても増えないならやめる
  • Passed System Test
  • https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_605/AlienAndHamburgers.cpp

結果

o-- 180.04pt 303rd/658 rating 1228 -> 1294 (+66)

ちゃんと解けた。


http://togetter.com/li/618981

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

2014-02-23

SRM 598

| 23:15

Div1 Easy (250) BinPacking

問題

  • 制限重量が300の容器がいくつかある
  • 重さ100以上300以下の品物がいくつか与えられる
  • 必要な容器の最小の個数を求める

方針

Div1 Medium (550) FoxAndFencing

問題

  • 1直線状の升目があり2人でゲームを行う
  • 二つの駒を距離d離して配置する
  • それぞれの速度と射程が与えられる
  • それぞれが最善手でプレイするときの勝者を求める

方針

  • (a)1手目で決まる(b)2手目で決まる(c)それ以外、に場合わけ
  • (c)は、速い方が勝者の候補
  • Challenge Succeeded
  • 自分のターン終了時、相手が1歩動いても相手の射程内にぎりぎり入らない状態でいる必要があるが、相手は最大限離れるので、自分の速度 > (相手の速度×2+射程差) が必要条件
  • https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_598/FoxAndFencing.cpp

Div2 Easy (250) ErasingCharacters

問題

  • 誕生日に文字列をもらった
  • 長すぎるので、連続する2文字を削除していくことにした
  • 最終的に得られる文字列を求める

方針

結果

ox- 211.32pt 212nd/484 rating 1400 -> 1439 (+39)

easyはまあまあ良かった。このmediumが解けないのは痛い。

SRMでも誕生日プレゼントが文字列に。

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