hotpepsiの練習帳

SRM 623

02:04

Div1 Easy (300) UniformBoard

問題

• N×Nの升目がある
• それぞれの升目は空きか、りんごか梨が入っている
• 1手で、任意の果物を別の空きに移動することができる
• 最大K手移動できるとき、りんごのみからなる長方形の最大の面積を求める

方針

• Nが20以下なので、位置と大きさについて全探索できそう
• 長方形が全てAで埋まっていればOK
• 埋まっていないときについて考えると、内側にも外側にも空きがなければ詰み
• 長方形の内側に空きがあるとき、外側には余分なAが必要で、1手かかる
• 長方形の外側だけに空きがあるとき、内側のPを出して外側のAを入れることができ、2手必要
• 内側に空きとPがあるケースは、外に2つ以上Aが必要で、まずAを内側に移動させて外側に空きを作るので、結局のところ、空きはコスト1、Pはコスト2で、空きの位置は気にしなくていい
• どこかに1つ以上の空きがあり、かつ、Aの総個数が長方形のぶんだけあり、かつ、移動コスト以下ならOK
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_623/UniformBoard.cpp

結果

o-- 160.95pts 286th/488 rating 1472 -> 1478 (+6)

判定条件を整理するのに時間がかかった。

最近ようやくdiv1easyの正解率が50%を超えてきた。

http://togetter.com/li/676233