Hatena::Grouptopcoder

hotpepsiの練習帳

2012-11-02

SRM 557

03:31

Div1 Easy (250) FoxAndMountainEasy

問題

  • スタート地点の高さがh0で終点の高さがhnの登山路がある。
  • 登山路はなだらかで±1の高低差からなる。
  • 部分的なアップダウンの情報が与えられる。
  • 登山路が成り立つかどうかを求める。

方針

Div1 Medium (550) Incubator

問題

  • インキュベーターが少女と契約する。
  • 少女は契約すると魔法少女となり、自分が守りたい少女を守る。
  • 誰かに守られた少女もまた、自分が守りたい少女を守る。
  • 守られていない魔法少女の最大人数を求める。

方針

  • (終了後)
  • LayCurseさんのところとか色々読む
  • 少女Aを魔法少女にしたとき、最終的に保護されることになる全少女は、ワーシャルフロイドで求める(少女iが少女kを保護し、かつ、少女kが少女jを保護するなら、少女iは少女jを保護することになる)
  • 保護者から被保護者へ辺を張る
  • 被保護者をなるべく生じさせないようにする=相互につながっていない集合を求める=典型問題(Dilworthの定理)らしい
  • https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_557/Incubator.cpp

Div2 Easy (250) GreatFairyWar

問題

  • N匹の妖精を倒したい。
  • 倒されていない妖精は毎秒ダメージを与えてくる。
  • 妖精にダメージを1ずつ与えて順番に倒す。
  • 受けるダメージの総和を求める。

方針

Div2 Medium (550) IncubatorEasy

問題

  • div1でN<=10

方針

結果

o-- 144.32pt 343rd rating 1319 -> 1378

mediumはいまいち理解してない

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