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