hotpepsiの練習帳

SRM 561

01:49

Div1 Easy (250) ICPCBalloons

問題

• コンテストを開催し、M個の問題を出題した。
• 正解者には風船を配る。
• 風船の色は問題毎に全て異なっている必要がある。
• 風船のサイズはMとLの二種類あり、同じ問題では同じサイズの風船を配る必要がある。
• 風船は別の色に塗ることができるが、サイズは変更できない。
• 風船を塗りなおす回数を求める。

方針

• サイズが2種類あるのでメモ化が思いつかない
• 問題に割り当てるサイズをどっちにするか悩む
• 制約条件を見直したら問題数が最大15
• MとLの全パターンは最大32768通りなので列挙できそう
• 塗りなおしを最小化するには...
• どこかに割り当てたあとは、全部塗りなおし
• 個数の多い風船から順番に、回答の多い問題に割り当てれば良いっぽい
• 問題A,B,C、風船P,Q,Rが降順に並んでいるとき、A->P、B->Q、C->Rに割り当てる
• 風船の種類と問題数の少ないほうでループして、余りは全て塗りなおし
• 提出
• デバッグコードが残ってて再提出
• Passed System Test
• (終了後解き直し)
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_561/ICPCBalloons.cpp

結果

o-- 75.05pt 369th rating 1232 -> 1268 (+36)

時間かかりすぎ＆再提出だが、方針が合ってたのは良かった。塗り直し分も分配してしまったがそれは不要だった。