Planning Rolling Blackouts / ICPC Domestic 2011

[ 問題 ]

Planning Rolling Blackouts | Aizu Online Judge

ICPC Domestic 2011 の E 問題。AOJ-ICPC では450点。

[ 考察 ]

グループ分けが再帰的なので再帰でどうにかできそう → あるグループをさらにグループ分けしていったときにできるグループ数の最大値を、適当なところで一回分けたときにできるグループの部分問題に帰着させる。

 1つの深さごとに最大62通りに分岐。深さは大体最大で 10 なので、愚直にやると62^10 で間に合わず。→ 町の数はそこまで多くないのでメモ化再帰をする。

 最初は予備力の扱い方が分からず、再帰関数を2つ書こうと思ったんですが、再帰関数の戻り値 pair にしてその second に予備力を載せておく → 漸化式の上では分けた2つのうちの小さい方をとる、でグループ数の最大値の探索といっしょに探索できる。(pairの比較方法を考えると、最大化したいパラメータが2つあってそれぞれ優先度が違うなら、優先度が高い方をfirstに入れて、低い方をsecondに入れるとうまくいくみたいな感じ)

[ 実装 ]

大まかな方針はメモ化再帰で全探索。

 計算量を減らすために、予め二次元累積和は用意しておく。あと地域全体の消費電力(Σc_ij)ももっておく。

 再帰関数は、引数に今考えている区画の左上の座標と右下の座標をとる。戻り値はpairで、その区画のグループ分けの最大数と、そのときの最大予備力。

 構造としては、まずその区画全体の消費電力が一定未満であるときは、その区画で停電をしたときの最大抑制需要が大きくなりすぎるので不適。そうでないとき、その区画のすべてのグループ分けの方法を全探索する。そのためには適当な場所での一回の分割でできた2区画をそれぞれ再帰関数に入れればいい。

[ コード ]

AIZU ONLINE JUDGE: Code Review