hotpepsiの練習帳

SRM 660

22:44

https://competitiveprogramming.info/topcoder/srm/round/16463/div/1

Div1 Easy (250) Coversta

問題

• N×Mのセルが与えられる
• 各セルはスコアを持つ
• 任意の2つのセルにステーションを建設する
• ステーションは、建設した位置を中心に、特定のパターンでセルを覆う
• 1つ以上のステーションで覆われたセルの合計スコアの最大値を求める

方針

• 全探索
• 死
• (終了後)
• 一つ目を全ての場所に置いてみる
• スコアの降順でソート
• 良いスコアの先頭100個と、ほかの全ての場所を試す(K^2程度しか重複しないので枝狩りして良いらしい)
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_660/Coversta.cpp

結果

x-- +1 208th/474 rating 1285 -> 1351 (+66)

xが上下方向なのがやや罠。良いものから順にやる、というのは思いつくべき。

重複して数えているのを落とすことができた。

http://togetter.com/li/830675