Facebook Hacker Cup 2013 Qualification Round

まだジャッジが終わっていないので、間違っていたらごめんなさい

Beautiful strings

解法

ソートするだけ

ソースコード

どっかいった

Balanced Smileys

解法

適当に探索。メモ化してやると、状態数はO(|s|^2)なので余裕で間に合う

ソースコード

map<string, bool> dp;
bool ok_char(char c)
{
    return (isalpha(c) && islower(c)) || c == ' ' || c == ':';
}
bool dfs(const string& s)
{
    if (dp.count(s))
        return dp[s];

    bool res = false;
    if (ok_char(s[0]))
        res |= dfs(s.substr(1));
    if (s.size() >= 2)
    {
        if (ok_char(s[s.size() - 1]))
            res |= dfs(s.substr(0, s.size() - 1));

        if (s.substr(0, 2) == ":)" || s.substr(0, 2) == ":(")
            res |= dfs(s.substr(2));

        if (s[0] == '(')
        {
            for (int i = 1; i < s.size(); ++i)
            {
                if (s[i] == ')')
                    res |= dfs(s.substr(1, i - 1)) && dfs(s.substr(i + 1));
            }
        }
    }

    return dp[s] = res;
}
int main()
{
    dp[""] = true;

    string s;
    getline(cin, s);
    int T = to_T<int>(s);
    for (int case_num = 1; case_num <= T; ++case_num)
    {
        getline(cin, s);

        string res = dfs(s) ? "YES" : "NO";
        printf("Case #%d: %s\n", case_num, res.c_str());
    }
}

Find the Min

解法

k以降の連続したk+1個の要素を見ると、0~kの数がそれぞれちょうど1つしかない。周期k+1になっているので、k~(2*k+1)までの値を求めれば、大きいnの場合でもO(1)で求めることができる。
k~(2*k+1)を求める方法は、愚直にやって全体でO(k^2)でも6分あるので間に合いそうだけど、BITを使うと速く求められる。
ある要素を求めるときに、k個前に含まれる場合に1、含まれない場合に0を割り当てる。そうすると、始めに0となる数を探せばいい。これは二分探索でできる。

ソースコード

template <class T>
class BIT
{
public:
    vector<T> a;
    int n;
    BIT(int n) : n(n), a(n + 1) {}
    BIT() { }

    void add(int i, T x)
    {
	++i;
	assert(i > 0);

	while (i <= n)
	{
	    a[i] += x;
	    i += i & -i;
	}
    }

    T sum(int i) const
    {
        ++i;
        T res = 0;
        while (i > 0)
        {
            res += a[i];
            i -= i & -i;
        }
        return res;
    }

    T range_sum(int low, int high) const { return sum(high) - sum(low - 1); }
    T at(int i) const { return sum(i) - sum(i - 1); }
    void assign(int i, T x) { add(i, x - at(i)); }
};
// precondition: all elements are 0 or 1
int find_first_zero(const BIT<int>& bit)
{
    int low = -1, high = bit.n;
    while (high - low > 1)
    {
        int mid = (low + high) / 2;
        if (bit.sum(mid) == mid + 1)
            low = mid;
        else
            high = mid;
    }
    return high;
}
vector<int> gen(int n, int k, ll a, ll b, ll c, ll r)
{
    vector<int> v(n);
    v[0] = a;
    for (int i = 1; i < k; ++i)
        v[i] = (b * v[i - 1] + c) % r;

    const int mv = 3 * k + 100;
    BIT<int> bit(mv + 100);
    map<int, int> cnt;
    rep(i, k)
    {
        ++cnt[v[i]];
        if (v[i] < mv)
            bit.assign(v[i], 1);
    }

    for (int i = k; i < n; ++i)
    {
        v[i] = find_first_zero(bit);

        int out = v[i - k];
        int in = v[i];
        --cnt[out];
        ++cnt[in];
        if (out < mv && cnt[out] == 0)
            bit.assign(out, 0);
        bit.assign(in, 1);
    }

    return v;
}
int solve(int n, int k, ll a, ll b, ll c, ll r)
{
    const int num = 3 * k + 1000;
    vector<int> v = gen(num, k, a, b, c, r);

    --n;
    const int period = k + 1;
    int rebased_n = n - k;
    int peri = rebased_n % period;
    return v[k + peri];
}
int main()
{
    int T;
    cin >> T;
    for (int case_num = 1; case_num <= T; ++case_num)
    {
        int n, k;
        ll a, b, c, r;
        cin >> n >> k;
        cin >> a >> b >> c >> r;

        int res = solve(n, k, a, b, c, r);
        printf("Case #%d: %d\n", case_num, res);
    }
}