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 をもらってしまった.

AOJ 1333 Beautiful Spacing

解法

二分探索+しゃくとり法.
二分探索は,普通に「スペースの隙間を X にして条件をクリアできるか」でやる.

次にしゃくとり部分.二分探索の過程で与えられた,空けていい間隔を S とする.

先に以下のテーブルを定義しておく.
dp[i] := i 番目の単語を左端にして,その後ろだけ考えた場合にクリアできるか.
更新は後ろからやる.

まず各 i について,「x[i] から x[j] まで一行に詰め込めるような,最大の j 」を考え,R1 とする.
次に,各 i について「x[i] から x[j] まで一行に詰め込んだ時に,Sをクリアできるような最小の j 」を R2 とする.
すると,R2 から R1 の間であれば,どこで一行を終えてもよい.また,位置 p を右端にして区切ってクリアできるかどうかは,dp[p + 1] をみればわかる.
したがって,
dp[i] = (dp[R2 + 1] + ... + dp[R1+1]) > 0
となる.

R1, R2, dp[R2 + 1] + ... + dp[R1 + 1] はすべてしゃくとりで計算できる.
したがって,これで計算量が O(NlogW) にできている.

ただし,最終行だけは右端に文字を置く必要がないと問題文に書かれているので,そこだけ辻褄を合わせる.

ソースコード

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

int main() {
    int W, N;
    while(cin >> W >> N, W) {
        vector<int> x(N), sum(N + 1);
        for(int i = 0; i < N; ++i) {
            cin >> x[i];
            sum[i + 1] = sum[i] + x[i];
        }

        auto check = [&](int space) {
            vector<int> dp(N + 1);
            int limit_r = N, ok_r = N;
            int ok_cnt = 0;
            for(int i = N - 1; i >= 0; --i) {
                while(W - (sum[limit_r] - sum[i]) - (limit_r - i - 1) < 0) {
                    ok_cnt -= dp[limit_r--];
                }
                while(ok_r > limit_r || ok_r - i - 1 > 0 && (W - (sum[ok_r] - sum[i]) + ok_r - i - 2) / (ok_r - i - 1) <= space) {
                    ok_cnt += dp[ok_r--];
                }

                dp[i] = limit_r == N || ok_cnt > 0;
            }

            return dp[0] == 1;
        };

        int lb = 0, ub = W;
        while(ub - lb > 1) {
            const int mid = (ub + lb) / 2;
            if(check(mid)) {
                ub = mid;
            } else {
                lb = mid;
            }
        }

        cout << ub << endl;
    }
}

感想

無限にバグった.
最初 O(NlogNlogW) 解で通るやろと贅沢に書いていたら11secぐらいでTLEしてしまい,泣きながらしゃくとりを書いた.
終わってみればしゃくとりのほうがコードはスッキリしていた.

2014 Yandex.Algorithm Elimination Stage, Round 3 E - Tetrahedron

解法

Standing -> 重心をおろした位置が底面の内部
Unstable -> 重心をおろした位置が底面の周上にある
Falling -> 重心をおろした位置が底面の外部

重心の座標は (a + b + c + d) / 4 なので,あとは底面の三角形と点との内外判定をするだけ.

ソースコード

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

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

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

class segment {
public:
    segment(point p1, point p2)
    : a(p1), b(p2)
    {}

    point a, b;
};

bool isis_sp(segment s, point p) {
    return std::abs(s.a - p) + std::abs(s.b - p) - std::abs(s.b - s.a) < eps;
}


int is_in_polygon(polygon const& poly, point p) {
    const int n = poly.size();
    ld sum = 0;
    for(int i = 0; i < n; ++i) {
        point p1 = poly[i], p2 = poly[(i + 1) % n];
        if(isis_sp(segment(p1, p2), p)) {
            return 0;
        }
        sum += arg((p2 - p) / (p1 - p));
    }
    return std::abs(sum) < pi / 2 ? 2 : 1;
}

int main() {
    vector<double> x(4), y(4), z(4);
    for(int i = 0; i < 4; ++i) {
        cin >> x[i] >> y[i] >> z[i];
    }

    point g(accumulate(begin(x), end(x), 0.0) / 4, accumulate(begin(y), end(y), 0.0) / 4);
    polygon poly;
    for(int i = 0; i < 3; ++i) {
        poly.emplace_back(x[i], y[i]);
    }

    switch(is_in_polygon(poly, g)) {
        case 0: cout << "Unstable" << endl; break;
        case 1: cout << "Standing" << endl; break;
        case 2: cout << "Falling" << endl; break;
        default: assert(false);
    }
}

感想

これ競プロの問題としてどうなの.

2014 Yandex.Algorithm Elimination Stage, Round 3 C - Intervals

解法

しゃくとり法で解いた.
条件を満たさないようなペアの数を数えて,全体から引くことで求める.
しゃくとりの過程で,今現在の区間が overlap しうるので,その分は足すことで重複して引かないようにしている.

条件を満たさないような任意のペア (l, r) が,必ずしゃくとりの過程でカウントされることを証明する必要がある.
カウントされないような動きとしては,今見ている区間の右端が l と r の間にあるのに,左端を狭めるときに l と r の間に入り込んでしまう場合であり,これしかない.
しかし,右端が l と r の間にあり,かつ左端を狭めていく時は,必ず l か l の前で停止する.(l, r) の間に条件を満たすペアが無いことからこれは明らかである.
よって,任意の条件を満たさないペア (l, r) はしゃくとりの過程で必ずカウントされる.

ソースコード

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

using ll = long long;

int main() {
    int n, d;
    scanf("%d %d", &n, &d);
    vector<int> a(n);
    for(int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }

    unordered_map<int, int> cnt;
    int l = 0, r = 0;
    int prev_r = -1;
    ll ans = 1LL * n * (n - 1) / 2;
    while(r < n) {
        while(r < n && cnt[a[r] + d] == 0 && cnt[a[r] - d] == 0) {
            cnt[a[r++]] += 1;
        }
        const ll width = r - l;
        const ll overlap = max(0, prev_r - l);
        ans -= width * (width - 1) / 2;
        ans += overlap * (overlap - 1) / 2;
        while(cnt[a[r] + d] > 0 || cnt[a[r] - d] > 0) {
            cnt[a[l++]] -= 1;
        }
        prev_r = r;
    }

    cout << ans << endl;
}

感想

この解法で解けそうだな~と思って通してしまった….
証明はあとづけである.反省.しゃくとり書く時いつもこんな感じだ….