hotpepsiの練習帳

SRM 531 Div2

03:09

Easy (250) UnsortedSequence

問題

• N個の配列がある。
• 辞書順で、ソートされたものの次のものを求める。

方針

• ソートして、後ろから見ていって違う要素があったらそれと交換
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_531/UnsortedSequence.cpp

Medium (600) NoRepeatPlaylist

問題

• N種類の曲がある。
• P曲からなるプレイリストを作りたい。
• 同じ曲は間隔Mだけ空ける必要がある。
• 何通りのプレイリストが作れるかを求める。

方針

• 解けない...
• kusanoさんの解が短くてすごい
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_531/NoRepeatPlaylist.cpp

Hard (950) KingdomReorganization

問題

• 未着手→復習
• 王国にN個の都市があり、そのうちのいくつかは道路で結ばれている。
• ある都市とある都市の道路を作るコストと壊すコストが与えられる。
• 任意の都市間の経路を一つのみにするための最小のコストを求める。

方針

• 蟻本の最小全域木のプリム法ほぼそのまんま
• priority_queue + union find木
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_531/KingdomReorganization.cpp

結果

239.06 204th rating 1133 -> 1152

easy、next_permutationは気づかなかった。そんなに時間かかってないのでまあいいやという感じ。

mediumが解けないのは困ったもんだ。解けないけどこれは良い問題。