No Change - nojimaの日記

久しぶりに日記を書いてみる。サークルの友達から次の問題を教えてもらった。

Sphere Online Judge (SPOJ) - Problem NOCHANGE

整数 k, x 及び v_i (i=1,..,k) が与えられるので、

$\sum_{i=1}^k a_i v_i = x$
$a_1 \ge a_2 \ge ... \ge a_k \ge 0$

を満たす整数 a_i (i=1,..,k) が存在するかどうかをYES, NOで答える問題。1≦k≦5, 1≦x,v_i≦100000.

以下解答。

最初、1≦k≦5, 1≦x≦100000の範囲でk,xに関する動的計画法(というかメモ化DFS)を使って解く方法でAcceptedをもらったけど、友達曰くもっと高速な方法があるらしいので、その方法を紹介。

もし、yという値を作ることができたとする、つまり

$\sum_{i=1}^k a_i v_i = y$
$a_1 \ge a_2 \ge ... \ge a_k \ge 0$

となる a_1,..,a_k が存在したとすると、y + v_1, y + v_1 + v_2, ..., y + v_1 + v_2 + ... + v_k という値も無条件にすべて作ることができる。

よって、0からxまでの整数を頂点とし、有向辺(y, y+Σv_i)を持つグラフを考え、このグラフに0からxまでの経路が存在するかどうかという問題に帰着できる。

有向辺は数字の小さい頂点から大きい頂点にしか伸びていないことを考えると次のようなコードが書ける。オーダーはO(kx).

#include <stdio.h>

bool ok[100001] = {true};

int main()
{
  int x, k, v[6];
  scanf("%d%d", &x, &k);
  v[k] = 1000000;
  for (int i = 0; i < k; ++i)
    scanf("%d", &v[i]);
  for (int j = 0; j <= x; ++j)
    if (ok[j])
      for (int i = 0, sum = v[0]; j+sum <= x; sum += v[++i])
        ok[j+sum] = true;
  puts(ok[x] ? "YES" : "NO");
}