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\lbrack x \rbrack \ :\bmod a_1= x の数のうち入力で与えられた整数たちで表現できるもののうちの最小値とする。
すると、この d という配列は

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

というグラフ上での各頂点への最短コストを与えていることが分かる。よってこのグラフで最短路を求めれば良い。
すると、クエリには b_j \geqq d\lbrack b_j \% a_1 \rbrack かを判定すれば 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);
}