hotpepsiの練習帳

SRM 557

03:31

Div1 Easy (250) FoxAndMountainEasy

問題

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

方針

• 高さは0以上という制約を踏まえてシミュレーション
• なんとか提出、AC
• (解き直し)
• h0からシミュレーションしてみて、途中もし負になったら、先頭にシーケンスUを追加する
• 長さが足りないか、残りの偶奇が合っていなければ不能
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_557/FoxAndMountainEasy.cpp

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ずつ与えて順番に倒す。
• 受けるダメージの総和を求める。

方針

• 全体の経過秒を加算していく
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_557/GreatFairyWar.cpp

Div2 Medium (550) IncubatorEasy

問題

• div1でN<=10

方針

• 全探索
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_557/IncubatorEasy.cpp

結果

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

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