Codeforces Round #176 (Div.1) E. Ladies' Shop

解法

FFT
まず,答えの集合から生成できる任意の重さは,ある2個以下のカバンを使って(同じカバンを2つでもいい)作ることができる.
なぜなら,もしある重さを p1 + p2 + p3 で生成したとする.もちろん p3 は与えられたカバンに含まれているはずである.また,p1 + p2 も同様に,与えられたカバンに含まれているはずである.そうでなければ集合の選び方に矛盾する.

したがって,問題を言い換えると,
「与えられたかばんの重さからちょうど2つ(同じものを選んで良い)選んで作れる重さの集合が,与えられたかばんの集合の部分集合であることを判定し,さらにその集合を生成する最小の元の個数を求めよ」
となる.
これはFFTで計算できる.第 a[i] 項を1としてそれ以外を0とする多項式 P をつくり,FFT で P^2 を求めれば良いからである.
また,答えの集合に含めなければならない重さは,P^2 のうち係数が0 かつ かばんにその重さが含まれているものである.
このために,Pの第0項は場合の数を求めるときとはうってかわって0にして置かなければならない.

ソースコード

// convolution は略
// data_type := complex<double>;

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    vector<int> a(n);
    vector<data_type> p(m + 1);
    unordered_set<int> s;
    for(int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
        p[a[i]] = data_type(1, 0);
        s.insert(a[i]);
    }
    auto p2 = convolution(p, p);

    vector<int> ans;
    bool ok = true;
    for(int i = 0; i <= m; ++i) {
        const int c = real(p2[i]) + 0.1;
        if(c == 0) {
            if(s.count(i) == 1) ans.push_back(i);
            continue;
        }
        ok &= s.count(i);
    }
    if(ok) {
        printf("YES\n%d\n", (int)ans.size());
        for(int i = 0; i < (int)ans.size(); ++i) {
            if(i != 0) printf(" ");
            printf("%d", ans[i]);
        }
        printf("\n");
    } else {
        printf("NO\n");
    }
}

感想

入出力が重いので注意.
自分のFFTはお世辞にも早いとは言えないので,TLEしてしまった.scanf/printf すると通る.

AOJ 2703 Dice Stamp

解法

明らかに全てのサイコロを使うのが最適.
あとは,後ろから見るbitDPで解く.
これは,最後に使うサイコロから決めていくと,その直前に使うサイコロによる得点が,今まで使ったサイコロでカバーされていない座標での得点と確定するからである.
前から見ると,今のサイコロが得た得点が最後まで残っているかを判断するのが厳しい.(追記 よく考えたら使ってないやつで被るところは得点に加えない、とやれば同じなので後ろからやらなくていいですね。後ろからのほうが楽だとは思うけど…)

サイコロ転がす部分は4方向しか無いのでそんなに辛くない.

計算量は一番重いところで O(2^n * n * |rot|) となり(ふつうのset とか使うと log つくけど),テストケースが 40 個あるとすると少し怪しいが AOJ のサーバーは速いので通る.

早くしたいなら,val[x][y] みたいに座標の値が小さいのを利用して2次元配列で管理すると良さそう.

ソースコード

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

enum {
    LEFT, RIGHT, FRONT, BACK, DOWN, UP
};

class dice {
public:
    dice(vector<int> score) : score(score) { assert(score.size() == 6); }

    void roll(char dir) {
        assert(dir == 'L' || dir == 'R' || dir == 'B' || dir == 'F');
        vector<int> nscore = score;
        if(dir == 'L') {
            nscore[LEFT] = score[UP];
            nscore[UP] = score[RIGHT];
            nscore[RIGHT] = score[DOWN];
            nscore[DOWN] = score[LEFT];
        } else if(dir == 'R') {
            nscore[RIGHT] = score[UP];
            nscore[UP] = score[LEFT];
            nscore[LEFT] = score[DOWN];
            nscore[DOWN] = score[RIGHT];
        } else if(dir == 'F') {
            nscore[FRONT] = score[UP];
            nscore[UP] = score[BACK];
            nscore[BACK] = score[DOWN];
            nscore[DOWN] = score[FRONT];
        } else {
            nscore[BACK] = score[UP];
            nscore[UP] = score[FRONT];
            nscore[FRONT] = score[DOWN];
            nscore[DOWN] = score[BACK];
        }
        score = move(nscore);
    }

    int get_value(int dir) const {
        return score[dir];
    }

private:
    vector<int> score;
};

int main() {
    const string dirs = "LRFB";
    constexpr int dx[4] = {-1, 1, 0, 0};
    constexpr int dy[4] = {0, 0, -1, 1};
    int n;
    while(cin >> n, n) {
        // (x, y -> value);
        using traj = map<pii, int>;
        vector<traj> trajs;
        for(int i = 0; i < n; ++i) {
            int x, y;
            cin >> x >> y;
            vector<int> score(6);
            for(int j = 0; j < 6; ++j) {
                cin >> score[j];
            }
            string rot;
            cin >> rot;
            dice d(score);
            traj t;
            t[make_pair(x, y)] = d.get_value(DOWN);
            for(char to : rot) {
                int dir = dirs.find(to);
                x += dx[dir], y += dy[dir];
                d.roll(to);
                t[make_pair(x, y)] = d.get_value(DOWN);
            }
            trajs.push_back(move(t));
        }

        vector<int> dp(1 << n);
        for(int S = 0; S < (1 << n); ++S) {
            set<pii> used;
            for(int i = 0; i < n; ++i) {
                if(S & (1 << i)) {
                    for(auto& p : trajs[i]) {
                        used.insert(p.first);
                    }
                }
            }
            for(int i = 0; i < n; ++i) {
                if(S & (1 << i)) continue;
                map<pii, int> new_values;
                for(auto& p : trajs[i]) {
                    if(used.count(p.first)) continue;
                    new_values[p.first] = p.second;
                }
                int value = 0;
                for(auto& p : new_values) {
                    value += p.second;
                }
                dp[S | (1 << i)] = max(dp[S | (1 << i)], dp[S] + value);
            }
        }

        cout << dp.back() << endl;
    }
}

感想

8sec 制限だと高速化をサボりがち.

AOJ 2572 Venn Diagram

解法

頑張って実装するだけ.
円の半径は入力からすぐわかる.
2つの円の距離を二分探索で求めたら,でかい方を左下隅に配置.
小さいほうは [0, pi/2] でどの角度に置くとよいかを判定.計算したくないので二分探索もどきでサボる.
最後にはみ出ないか確認して終わり.

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ld = long double;
using point = complex<ld>;

constexpr ld eps = 1e-5;
constexpr ld pi = acos(-1.0);

struct circle {
    circle(point p, ld r) : p(p), r(r) {}
    point p;
    ld r;
};

vector<point> is_cc(circle const& c1, circle const& c2) {
    vector<point> res;
    ld d = abs(c1.p - c2.p);
    ld rc = (d * d + c1.r * c1.r - c2.r * c2.r) / (2 * d);
    ld dfr = c1.r * c1.r - rc * rc;
    if(abs(dfr) < eps) {
        dfr = 0;
    } else if(dfr < 0) {
        return res;
    }

    ld rs = sqrt(dfr);
    point diff = (c2.p - c1.p) / d;
    res.push_back(c1.p + diff * point(rc, rs));
    if(dfr != 0) {
        res.push_back(c1.p + diff * point(rc, -rs));
    }
    return res;
}

// assert: c1 is left position
ld intersect_area(circle c1, circle c2) {
    const ld d = abs(c1.p - c2.p);
    if(d >= c1.r + c2.r - eps) return 0;
    if(c1.r < c2.r) swap(c1.r, c2.r);
    if(d < eps) return (c2.r * c2.r * pi);

    auto ps = is_cc(c1, c2);
    assert(!ps.empty());

    ld rad1 = abs(arg(ps[0] - c1.p));
    ld S = c1.r * c1.r * rad1 - 0.5 * c1.r * c1.r * sin(2 * rad1);
    ld rad2 = pi - abs(arg(ps[0] - c2.p));
    S += c2.r * c2.r * rad2 - 0.5 * c2.r * c2.r * sin(2 * rad2);
    return S;
}

int main() {
    cout << fixed << setprecision(10);

    ld w, h, a, b, ab;
    while(cin >> w >> h >> a >> b >> ab) {
        if(w == 0) break;

        const ld ra = sqrt(a / pi);
        const ld rb = sqrt(b / pi);

        if(min(w, h) < ra * 2 || min(w, h) < rb * 2) {
            cout << "impossible" << endl;
            continue;
        }

        circle c1(point(0, 0), ra);
        ld d = 0;
        { // calc dist
            ld lb = abs(ra - rb), ub = ra + rb;
            for(int loop = 0; loop < 100; ++loop) {
                const ld mid = (ub + lb) / 2;
                circle c2(point(mid, 0), rb);
                if(intersect_area(c1, c2) + eps < ab) {
                    ub = mid;
                } else {
                    lb = mid;
                }
            }

            d = lb;
        }
        // check
        bool swapped = ra < rb;
        c1.r = swapped ? rb : ra;
        c1.p = point(c1.r, c1.r);
        circle c2(point(c1.r + d, c1.r), swapped ? ra : rb);
        assert(abs(intersect_area(c1, c2) - ab) < 2 * eps);
        {
            ld lb = 0, ub = pi / 2;
            for(int loop = 0; loop < 60; ++loop) {
                const ld mid = (lb + ub) / 2;
                c2.p = c1.p + point(cos(mid) * d, sin(mid) * d);
                if(imag(c2.p) + c2.r > h + eps || real(c2.p) - c2.r < -eps) {
                    ub = mid;
                } else if(real(c2.p) + c2.r > w + eps || imag(c2.p) - c2.r < -eps) {
                    lb = mid;
                } else {
                    break;
                }
            }
        }

        if(imag(c2.p) + c2.r <= h + eps && real(c2.p) + c2.r <= w + eps
           && imag(c2.p) - c2.r >= -eps && real(c2.p) - c2.r >= -eps) {
            if(swapped) swap(c1, c2);
            cout << real(c1.p) << ' ' << imag(c1.p) << ' ' << c1.r << ' ';
            cout << real(c2.p) << ' ' << imag(c2.p) << ' ' << c2.r << endl;
        } else {
            cout << "impossible" << endl;
        }
    }
}

感想

こういうのを15分ぐらいで通せるようにならないとなあという感じ.

AOJ 1252 Confusing Login Names

解法

以下の4パターン全部試すだけ.

  • swap しない(単に編集距離の問題)
  • 1回swapしたあと編集距離
  • 2回swap
  • 消した後 swap

最悪 200(200-1)/2 * 16 * (16 * 16) なので,まあ適当にやると 2sec ぐらいで通る.

#include <bits/stdc++.h>
using namespace std;

constexpr int inf = 1e9;

int levenshtein_distance(string s1, string s2) {
    const int n = s1.size(), m = s2.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, inf));
    for(int i = 0; i <= n; ++i) dp[i][0] = i;
    for(int j = 0; j <= m; ++j) dp[0][j] = j;
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            dp[i][j] = min({dp[i][j],
                            dp[i - 1][j] + 1,
                            dp[i][j - 1] + 1,
                            dp[i - 1][j - 1] + (s1[i - 1] != s2[j - 1])});
        }
    }
    return dp[n][m];
}

int main() {
    int n;
    while(cin >> n, n) {
        int d;
        cin >> d;
        vector<string> name(n);
        for(int i = 0; i < n; ++i) {
            cin >> name[i];
        }

        vector<string> ans;
        for(int i = 0; i < n; ++i) {
            for(int j = i + 1; j < n; ++j) {
                auto s1 = name[i], s2 = name[j];
                if(s1.size() < s2.size()) swap(s1, s2);
                const int m = s1.size();

                int min_d = levenshtein_distance(s1, s2);

                // swap -> levenshtein
                for(int k = 0; k + 1 < m; ++k) {
                    swap(s1[k], s1[k + 1]);
                    min_d = min(min_d, levenshtein_distance(s1, s2) + 1);
                    swap(s1[k], s1[k + 1]);
                }

                // swap -> swap
                for(int k = 0; k + 1 < m && min_d >= 3; ++k) {
                    swap(s1[k], s1[k + 1]);
                    for(int l = 0; l + 1 < m; ++l) {
                        swap(s1[l], s1[l + 1]);
                        if(s1 == s2) min_d = 2;
                        swap(s1[l], s1[l + 1]);
                    }
                    swap(s1[k], s1[k + 1]);
                }

                // delete -> swap
                for(int k = 0; k < m && min_d >= 3; ++k) {
                    auto ss1 = (k == 0 ? string("") : s1.substr(0, k)) + (k + 1 == m ? string("") : s1.substr(k + 1));
                    for(int l = 0; l + 1 < m - 1; ++l) {
                        swap(ss1[l], ss1[l + 1]);
                        if(ss1 == s2) min_d = 2;
                        swap(ss1[l], ss1[l + 1]);
                    }
                }

                if(min_d <= d) {
                    ans.push_back(min(name[i], name[j]) + "," + max(name[i], name[j]));
                }
            }
        }

        sort(begin(ans), end(ans));
        for(auto x : ans) {
            cout << x << endl;
        }
        cout << ans.size() << endl;
    }
}

Helvetic Coding Contest 2018 E2. Guard Duty (medium)

解説

わからなかったので上位陣のコードから解法を得た.
とりあえずソートして隣接項の差を作ると,以下の問題になる.

n - 1 要素からなる数列から,k 個えらんでその和を最小化せよ.ただし,隣接2要素を取ってはならない.

基本は貪欲的に取っていく.つまりコストが小さい方から順に取る.
ここで,取ったやつの隣をどう扱うか考えるのだが,頭のいいやり方がある.
それは,今現在選んだ要素と,それに隣接している要素の集合の集合(集合の集合という表現であっている)を1つの整数値にまとめて set で管理するというものである.
たとえば,初期状態から考えると,それは n - 1 要素からなる集合となる(各集合は1つの要素からなる).
この時 a[i] を選択したとすると,集合から a[i - 1], a[i], a[i + 1] を削除して新たに a[i - 1] + a[i + 1] - a[i] を追加する.そして,仮に次に a[i - 1] + a[i + 1] - a[i] の要素を選択するとするなら,それは a[i - 1] と a[i + 1] を選択したのを同じ状態になる.
したがって,この貪欲アルゴリズムを k 回行えば,最適解が求まる.

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

constexpr ll inf = 1e18;

int main() {
    int k, n;
    cin >> k >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    sort(begin(a), end(a));

    set<pair<ll, ll>> index_value, value_index;
    for(int i = 0; i + 1 < n; ++i) {
        index_value.emplace(i, a[i + 1] - a[i]);
        value_index.emplace(a[i + 1] - a[i], i);
    }
    index_value.emplace(-1, inf);
    index_value.emplace(n, inf);
    value_index.emplace(inf, -1);
    value_index.emplace(inf, n);

    ll res = 0;
    for(int lp = 0; lp < k; ++lp) {
        int v, l, r;
        ll val, lval, rval;
        tie(val, v) = *begin(value_index);
        auto it = index_value.lower_bound(make_pair(v, val));
        tie(l, lval) = *prev(it);
        tie(r, rval) = *next(it);

        index_value.erase(make_pair(v, val));
        index_value.erase(make_pair(l, lval));
        index_value.erase(make_pair(r, rval));
        value_index.erase(make_pair(val, v));
        value_index.erase(make_pair(lval, l));
        value_index.erase(make_pair(rval, r));
        index_value.emplace(v, lval + rval - val);
        value_index.emplace(lval + rval - val, v);
        res += val;
    }

    cout << res << endl;
}

感想

これめっちゃ頭いい….思いつけたら気持ちいいだろうなあ.
賢い人は自明とかいうんだろうな….

AOJ 1371 Infallibly Crack Perplexing Cryptarithm

解法

現れうる文字は高々8種類しかない.
なので各文字に対して何を割り当てるか全探索して構文解析するだけ.

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ret_type = double;
constexpr ret_type eps = 1e-8;

ret_type expr(string const& s, int& p);
ret_type term(string const& s, int& p);
ret_type factor(string const& s, int& p);
ret_type number(string const& s, int& p);

ret_type expr(string const& s, int& p) {
    ret_type val = term(s, p);
    while(p < (int)s.size() && (s[p] == '+' || s[p] == '-')) {
        if(s[p] == '-') {
            val -= term(s, ++p);
        } else {
            val += term(s, ++p);
        }
    }
    return val;
}

ret_type term(string const& s, int& p) {
    ret_type val = factor(s, p);
    while(p < (int)s.size() && s[p] == '*') {
        val *= factor(s, ++p);
    }
    return val;
}

ret_type factor(string const& s, int& p) {
    if(s[p] == '-') {
        return -factor(s, ++p);
    } else if(s[p] == '(') {
        ret_type res = expr(s, ++p);
        if(p >= (int)s.size() || s[p] != ')') throw std::logic_error("");
        ++p;
        return res;
    } else if(isdigit(s[p])) {
        return number(s, p);
    } else {
        throw std::logic_error("");
    }
}

ret_type number(string const& s, int& p) {
    if(s[p] != '0' && s[p] != '1') throw std::logic_error("");
    if(p + 1 < (int)s.size() && s[p] == '0' && isdigit(s[p + 1])) throw std::logic_error("");

    ret_type res = 0;
    while(p < (int)s.size() && isdigit(s[p])) {
        res *= 2;
        res += (s[p++] == '1');
    }
    return res;
}

int main() {
    string s;
    cin >> s;
    const int n = s.size();
    vector<char> cs;
    for(auto c : s) {
        if(isalpha(c)) {
            cs.push_back(c);
        }
    }
    sort(begin(cs), end(cs));
    cs.erase(unique(begin(cs), end(cs)), end(cs));

    vector<char> v = {'0', '1', '+', '-', '*', '=', '(', ')'};
    sort(begin(v), end(v));

    if(cs.size() > v.size()) {
        cout << 0 << endl;
        return 0;
    }

    int ans = 0;
    set<string> checked;
    do {
        string t;
        for(auto c : s) {
            if(isalpha(c)) {
                t += v[find(begin(cs), end(cs), c) - begin(cs)];
            } else {
                t += c;
            }
        }
        if(count(begin(t), end(t), '=') != 1) continue;
        int lp = 0, rp = find(begin(t), end(t), '=') - begin(t) + 1;
        if(rp == 1 || rp == n || checked.count(t) == 1) continue;

        checked.insert(t);

        try {
            auto lval = expr(t, lp), rval = expr(t, rp);
            if(t[lp] == '=' && rp == n && abs(lval - rval) < eps) {
                ans += 1;
            }
        } catch(...) {
            continue;
        }
    } while(next_permutation(begin(v), end(v)));

    cout << ans << endl;
}

感想

これぞやるだけ問題って感じがする.
ret_type = double になってるのは,01しか現れないけどけど10進数解釈をするんだと勘違いして(しかもそれでサンプルが全部合う),31桁も来ると困るなあと思ったからです.普通に int で良い.

AOJ 1351 Flipping Parentheses

解法

StarrySkyTree + 二分探索で通した.

( を +1, ) を -1 として累積和をStarrySkyTree上で管理する.
文字列が balanced であることと,累積和上の最小値が 0 以上であり,かつ末尾の値が0であることは同値である.

さて,与えられた位置をとりあえず反転して考える.

( -> ) に反転した場合,明らかに反転後最も左に現れる ) の位置が答えになる(証明も簡単).

) -> ( に反転した場合が問題である.
ある位置の ( を ) に反転できる条件は,それ以降の累積和の値の最小値が2以上であることに気がつけば,二分探索で求めるだけになる.

計算量は O(N(logN)^2) となる.

ソースコード

#include <bits/stdc++.h>
using namespace std;

constexpr int inf = 1e9;

class starry_sky_tree {
public:
    starry_sky_tree(int n_)
    : n(expand(n_)), data(n * 2, 0), lazy(n * 2, 0)
    {}

    void add(int l, int r, int val) {
        l += n, r += n;
        const int left = l, right = r;
        while(l != r) {
            if(l & 1) {
                lazy[l] += val;
                data[l++] += val;
            }
            if(r & 1) {
                lazy[--r] += val;
                data[r] += val;
            }
            l /= 2, r /= 2;
        }
        l = left, r = right - 1;
        while(l /= 2, r /= 2) {
            data[l] = min(data[l * 2], data[l * 2 + 1]) + lazy[l];
            data[r] = min(data[r * 2], data[r * 2 + 1]) + lazy[r];
        }
    }

    int query(int l, int r) const {
        l += n, r += n;
        int res1 = inf, res2 = inf;
        while(l != r) {
            if(l & 1) res1 = min(res1, data[l++]);
            if(r & 1) res2 = min(res2, data[--r]);
            l /= 2, r /= 2;
            res1 += lazy[l - 1];
            res2 += lazy[r];
        }
        --l;
        while(l /= 2, r /= 2) {
            res1 += lazy[l];
            res2 += lazy[r];
        }
        return min(res1, res2);
    }

private:
    int expand(int n) {
        return n == 1 ? n : expand((n + 1) / 2) * 2;
    }

private:
    const int n;
    vector<int> data, lazy;
};

int main() {
    int N, Q;
    string s;
    cin >> N >> Q >> s;

    starry_sky_tree sum(N);
    set<int> right_paren;
    for(int i = 0; i < N; ++i) {
        if(s[i] == '(') {
            sum.add(i, N, 1);
        } else {
            sum.add(i, N, -1);
            right_paren.insert(i);
        }
    }

    while(Q--) {
        int q;
        cin >> q;
        q--;

        int ans = q;
        if(s[q] == '(') {
            sum.add(q, N, -2);
            right_paren.insert(q);
            ans = *right_paren.begin();
            right_paren.erase(ans);
            sum.add(ans, N, 2);
        } else {
            sum.add(q, N, 2);
            int lb = 0, ub = N - 1;
            while(ub - lb > 1) {
                const int mid = (lb + ub) / 2;
                if(sum.query(mid, N) >= 2) {
                    ub = mid;
                } else {
                    lb = mid;
                }
            }
            ans = ub;
            sum.add(ans, N, -2);
            right_paren.erase(q);
            right_paren.insert(ans);
        }
        swap(s[q], s[ans]);

        cout << ans + 1 << endl;
    }
}

感想

swap(s[q], s[ans]) を書き忘れて WA をもらってしまった.