Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

Polish Olympiad in Informatics X Stage III - Sums

問題文 : http://main.edu.pl/en/archive/oi/10/sum

問題概要 :
数列 $a_1,\ a_2,\ \cdots,\ a_n$ が与えられる。次のクエリに $k$ 個答えよ。

  • 数 $b_j$ は 非負整数$x_1,\ x_2,\ \cdots,\ x_n$ を用いて $\displaystyle\sum_{i=1}^{n} x_i a_i$ と表せるか?
  • $1 \leqq n \leqq 5000$
  • $1 \leqq a_1 < a_2 < \cdots < a_n \leqq 50000$
  • $1 \leqq k \leqq 10000$
  • $0 \leqq b_j \leqq 10^9$


解法 :
$a_i$ が比較的小さいことを利用した解を考えてみよう。
$a_1$ を法とした世界を考えてみる。
このとき、ある数 $x$ が作れるとすると、当然 $x + c a_1$ ($c$ は非負整数) という数が作れることが分かる。
そこで、 $d[x]\ :\ \text{mod} a_1= x$ の数のうち入力で与えられた整数たちで表現できるもののうちの最小値とする。
すると、この $d$ という配列は

  • 頂点 : $0$ から $a_1 - 1$ までの整数
  • 辺 : 入力で与えられた $n$ 個の整数で、すべての頂点から $n$ 本の辺が出ている。コストは$a_i$で、遷移は $j \rightarrow (j + a_i) \% a_1$

というグラフ上での各頂点への最短コストを与えていることが分かる。よってこのグラフで最短路を求めれば良い。
すると、クエリには$b_j \geqq d[b_j \% a_1 ]$ かを判定すれば $O(1)$ 時間で答えることが出来る。

時間計算量は $O(na_1 \log a_1)$ となる。
$a_1$ がある程度小さくなりそうということに依存している解法なのがつらい。

コード :

#include <bits/stdc++.h>

using namespace std;

typedef long long Int;

const Int INF = 1001001001001001001ll;

typedef pair<Int, int> pint;

//d[x] : mod a[0] = x の数のうち入力で与えられた整数たちで表現できるもののうちの最小値
Int d[50000];

int main()
{
    int n;
    int a[5000];

    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", a + i);

    fill(d, d + a[0], INF);

    priority_queue<pint, vector<pint>, greater<pint> > pq;

    pq.push(pint(0, 0));
    d[0] = 0;
    while (!pq.empty()){
        pint x = pq.top(); pq.pop();
        if (x.first > d[x.second]) continue;
        for (int i = 1; i < n; i++){
            pint nx = pint(x.first + a[i], (x.second + a[i]) % a[0]);
            if (nx.first >= d[nx.second]) continue;
            d[nx.second] = nx.first;
            pq.push(nx);
        }
    }

    int k;
    scanf("%d", &k);

    for (int i = 0; i < k; i++){
        int b;
        scanf("%d", &b);
        if (b >= d[b % a[0]]) printf("TAK\n");
        else printf("NIE\n");
    }

    return (0);
}