hotpepsiの練習帳

SRM 551

02:08

Div1 Easy (250) ColorfulChocolates

問題

• 何色かのチョコレートが横一列に並んでいる。
• 交換して同じ色ができるだけ連続で並べたい。
• 交換回数が与えられる。最大の連続数を求める。

方針

• ある色Xを揃えるとき、XかX以外かを考えればよい
• すでに連続しているXは動かさない
• 連続していないXは、交換により1マスだけ動くのと等しい
• つまり追い越さない場合、交換回数=移動距離とみなせる
• 不動点を決める
• 近い距離のやつから集めていく
• 全ての点を不動点にしてみる全探索
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_551/ColorfulChocolates.cpp

Div1 Medium (450) ColorfulWolves

問題

• 毎晩毎に1回、色が変化する狼がいる。
• 各色にはインデックス値が与えられており、その晩に可能な変化のうち最小のインデックス値の色に変化する。
• 色Aから色Bへ変化するテーブルが与えられる。このテーブルは遺伝子操作により、特定の変化をしないようにすることができる。
• 色インデックスゼロからN-1に変化するための最小の遺伝子操作の回数を求める。

方針

• Warshall-Floydでいけるらしい
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_551/ColorfulWolves.cpp

結果

o-- 173.03 + 0 = 173.03pt 446th rating 1202 -> 1233 (+31)

easyは謎コードを書いてしまった。もっと単純な全探索で書けるべき。

mediumは400人くらいAC。さすがdiv1