Polish Olympiad in Informatics X Stage III - Sums
問題文 : http://main.edu.pl/en/archive/oi/10/sum
問題概要 :
数列 が与えられる。次のクエリに 個答えよ。
- 数 は 非負整数 を用いて と表せるか?
解法 :
が比較的小さいことを利用した解を考えてみよう。
を法とした世界を考えてみる。
このとき、ある数 が作れるとすると、当然 ( は非負整数) という数が作れることが分かる。
そこで、 の数のうち入力で与えられた整数たちで表現できるもののうちの最小値とする。
すると、この という配列は
- 頂点 : から までの整数
- 辺 : 入力で与えられた 個の整数で、すべての頂点から 本の辺が出ている。コストはで、遷移は
というグラフ上での各頂点への最短コストを与えていることが分かる。よってこのグラフで最短路を求めれば良い。
すると、クエリには かを判定すれば 時間で答えることが出来る。
時間計算量は となる。
がある程度小さくなりそうということに依存している解法なのがつらい。
コード :
#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); }