ちょっと好き

solution

$\Pi_i A_i \le 10^{100}$を使って大きいものと小さいものに分ける。半分全列挙。$10^k + 2^{100/k}$で抑えられる感じ。

$A_i \ge 10^k$なものの個数を考える。$k = 5$としよう。 そのようなものは高々$20$個。$2^{20} = 1.0 \times 10^6$なので列挙可能。 残りの$80$個について、どれも$A_i \le 10^5$という仮定を得ているので、$O(N \times \max_i A_i)$の重みで潰す列挙が$80 \times 10^5 = 8.0 \times 10^6$で間に合う。 これらで半分全列挙にすればよい。

implementation

経路は直接保持して間に合う。 最後に使ったやつだけ保存するようにしてもよい。

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <unordered_map>
#include <functional>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) y) { return (f)(begin(y), end(y), ## __VA_ARGS__); })(x)
typedef long long ll;
using namespace std;
int main() {
    int n; ll x; cin >> n >> x;
    vector<ll> a(n); repeat (i,n) cin >> a[i];
    vector<int> rank(n); whole(iota, rank, 0);
    whole(sort, rank, [&](int i, int j) { return a[i] < a[j]; });
    const ll limit = 1e5;
    unordered_map<int,vector<int> > low;
    low[0] = vector<int>();
    int i = 0;
    for (; i < n and a[rank[i]] < limit; ++ i) {
        unordered_map<int,vector<int> > prv = low;
        for (auto & it : prv) {
            it.second.push_back(rank[i]);
            low[it.first + a[rank[i]]] = it.second;
        }
    }
    vector<int> high; ll acc = 0;
    function<bool (int)> dfs = [&](int i) {
        if (i >= n) return false;
        if (dfs(i+1)) return true;
        acc += a[rank[i]];
        high.push_back(rank[i]);
        if (low.count(x - acc)) return true;
        if (dfs(i+1)) return true;
        high.pop_back();
        acc -= a[rank[i]];
        return false;
    };
    if (low.count(x) or dfs(i)) {
        string ans(n, 'x');
        for (int j : low[x - acc]) ans[j] = 'o';
        for (int j : high)         ans[j] = 'o';
        cout << ans << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}
  • Thu Jan 5 19:20:00 JST 2017
    • CEしてたので修正