hotpepsiの練習帳

SRM 568

03:25

Div1 Easy (250) BallsSeparating

問題

• N個の箱がある。
• それぞれの箱には3色のボールがそれぞれ1個以上入っている。
• ボールを1個ずつ移動して、それぞれの箱のボールを1色以下にしたい。
• 最小の操作回数を求める。

方針

• 色の数よりも箱の数の方が少ない場合、不可能
• なので最初に色の数を数える(が、これは無駄だった。制約より、箱が3未満なら不能)
• 1色以下にすればよいが、0色にするのは無駄
• 数が一番多い色を残して全て移動すればよい
• とりあえず単純にやる
• sample3で死
• 同じ色に偏るとだめ
• 少なくとも1色について1つの置き場所は必要
• 3色の置き場所の組み合わせを全部試せばよさそう
• 書いた
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_568/BallsSeparating.cpp

結果

o-- 127.53pt 474th/723 rating 1309 -> 1322

mediumが難しくてeasy早解きな回。微増。

途中の無駄が多くて遅かった。