MEMORANDUM CEDRETABRI

ARS LONGA VITA BREVIS

AtCoder Regular Contest 017 の C 問題

C - 無駄なものが嫌いな人

また古い問題を持ち出してきたなぁ、と思うかもしれない。まぁそうなんだ。
今、 ARC のA問題とB問題を毎日解く、みたいなことをやっていて、解けるならC問題まで解くようにしている。

このC問題、今まで僕は半分全列挙の問題をあまり解いたことがなく、解いてみて面白いと感じたので、丁寧に考えてみることにした。

概要

{N} 個の品物がある。それぞれの重さは {w_i} である。合計が {X} になるような組み合わせは何通りか。

1\leq N\leq32 \\ 1\leq X\leq10^{9} \\ 1\leq w_i\leq5\times10^{7}

何を考えたか

まず制約を見てぱっと思いつくことは、

  • {X} が大きい
  • {N} はやたら小さい

ということだろうか。

問題文にはナップサック問題っぽいことが書いてあるが、この {X} のサイズだと動的計画法では難しそう、という予感がある（でも1回試しちゃった）。

というわけで、 {N} が小さい点に着目してみる。小さいとは言っても {32} なので、組み合わせを全列挙するのは難しそう（ {2^{32}=4294967296} ）。そう、全部列挙するなら……。

というわけで、半分全列挙が出てくる。

半分全列挙

典型テクニックの1つだと認識している。
対象を半分に分け、それぞれの中で全列挙して、その後でそれぞれの要素を突き合わせるような手法である。

例えば今回の問題。 {2^{32}} は非常に大きい数になってしまうのだが、その半分の {16} 個の組み合わせを全列挙するだけなら、 {2^{16}=65536} ですむ。なので、まず半分ずつ全部の組み合わせを試した後、それぞれのグループから1つずつ取り出して合計が {X} になる組み合わせを数え上げれば良い。最後に突き合わせる処理に二分探索を用いることで、計算量を抑えることができるのがポイント。

二分探索

上に挙げたように、最後に組み合わせを数える際に愚直にやってしまうと、結局 {2^{N}} かかってしまう。しかし、合計が {X} になればいいのだから、ソートした後に二分探索をすることで {O(2^\frac{N}{2}log2^\frac{N}{2})=O(N\times2^{\frac{N}{2}-1})} の計算量ですませることができる（この時、同じ数値が複数個出てくる場合を考えなければいけないので注意）。

二分探索はあらゆる場面で役に立つのだ。

ハッシュテーブル

この記事を書いている間に気付いたのだが、合計がきっちり {X} になる場合のみ数えればいいのだから、別にソートして二分探索しなくても、ハッシュテーブルに突っ込んでしまえばいい。

これで全体の処理はかなり簡単になる。

実装

実際のコードはこんな感じ。

import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric, std.bigint;

long[32] WS;

void main()
{
    auto nx = readln.split.to!(int[]);
    auto N = nx[0];
    long X = nx[1];
    foreach (i; 0..N) WS[i] = readln.chomp.to!long;

    auto ns = [0L], nss = [0L];
    foreach (i; 0..N/2) {
        foreach (j; 0..ns.length) ns ~= ns[j] + WS[i];
    }
    foreach (i; N/2..N) {
        foreach (j; 0..nss.length) nss ~= nss[j] + WS[i];
    }
    int[long] ND;
    foreach (n; nss) {
        if (n in ND) {
            ++ND[n];
        } else {
            ND[n] = 1;
        }
    }

    int res;
    foreach (n; ns) {
        auto x = X - n;
        if (x in ND) {
            res += ND[x];
        }
    }

    writeln(res);
}

Ruby でも実装してみた。かなり簡潔に書ける。

n, x = gets.split.map(&:to_i)
ws = n.times.map { gets.to_i }

def zr ws
  ws.reduce([0]) { |ns, w|
    ns[0...ns.length].each do |n|
      ns << w + n
    end
    ns
  }
end

ns = zr ws[0...n/2]
nd = zr(ws[n/2..-1]).reduce(Hash.new { 0 }) { |nd, n| nd[n] += 1 and nd }

puts(ns.reduce(0) { |a, n| a + nd[x - n] })

感想

最初やった時は「半分全列挙と二分探索との組み合わせで解けるの、応用っぽくてカッコいい」と思ったのだが、よく考えてみたら二分探索は不要だった（解説では二分探索の利用に触れていたけど）。

半分全探索がかなり綺麗に嵌る問題に見えるので、練習にはとても良かったと思う。