No Need / ABC056

[ 問題 ]

D: No Need - AtCoder Beginner Contest 056 | AtCoder

[ 本文 ]

コンテストに参加したときは解けなかった問題。

競プロ初めたばっかりだったからしょうがない(ほんまか)。

AtCoder の問題は丁寧な editorial があるので別に解説とか書かなくていいんじゃないかと思ったんですが、

それに載ってない解法で実装してたのでやっぱり書きます(そもそも備忘録的なブログなので、実用性とか考えてなかった)。

まずは解説通りに問題文を言い換える。つまり「カード i を含まずに総和が K - a[i] 以上 K 未満になるような集合を作れるa[i]を探し」ます。

まずサイズKの配列dpを用意する。この中には、総和がj (0 ≦ j< K)にできるような集合の個数を入れます。作り方としては、a[i] を一個ずつみていって j - a[i] ≧ 0 なら dp[j] += dp[j - a[i]] って言う感じで更新していく(このとき j を小さい方から見てくと自分自身での更新の影響を受けてしまうので j は大きい方から見ていく)。

これで K 以下に数について、総和がその値になる集合の数がわかるようになります。

ただ求めたい集合には カード i を含まないという制限がついてるので、このままではうまくいきません。

そこで、 「k ≧ a[i] のとき、総和が k になる集合のうち カードi を含まないのものの数は、集合の全体から総和がk - a[i] になる集合のうちのカード i を含まないものの数を引いたもの。k < a[i] のときは、すべてカード i を含まない集合(当たり前)」という性質を利用してDPをします。(証明としてはまず、カード i を含んでいる総和が k になる集合の集合をA として、さらにカード i を含まずに総和が k - a[i] になる集合の集合をBとします。すると、Aの元について、その集合からカード i をとったもの(これは総和が k - a[i] になるので B の元)を対応付ける写像f : A → Bを考えます。ちょっと考えるとこれが全単射なのが分かって、|A| = |B| となるので

DP走査がO(K)で、たかだかN回のDPをするので全体だとO(N * K)になります。(ただ多分模範解答のO(N * K)のやつよりちょっと遅い)

[ コード ]

Submission #1337159 - AtCoder Beginner Contest 056 | AtCoder

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