AOJ 1362 Do Geese See God?

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1362

問題概要

文字列 S を部分列（部分文字列ではない）に持つような最小の長さの回文の集合の中で，辞書順 k 番目のものを求めよ．
・制約
1 <= |S| <= 2000
1 <= k <= 10^18

解法

区間DPをやります．作れる文字列の数 + 辞書順最小構築が必要なので，DPかなあという推測は立つと思います．

まず，問題を2つの部分に分けます．

1. 最小の文字列の長さを求める
2. 作ることのできる回文のパターン数

最小の文字列の長さは，以下の dp で求められます．
len[i][j] := S[i, j] を部分列にもつような回文の最小長さ
右端と左端が一致していない場合，最小の回文を構成するのであれば，そのどちらかを挿入することになります．一致していれば，明らかに挿入する必要はありません．これを元に漸化式を立てます．

作ることのできる回文のパターン数も，以下の dp で求められます．
dp[i][j] := S[i, j] を部分列にもつような最小長さの回文の種類数
この計算には len[i][j] を用います．S[i] と S[j] が等しい場合，最小長さにするので dp[i + 1][j - 1] が答えです．S[i] と S[j] が異なる場合，S[i] と S[j] のどちらかを挿入することになりますが，len[i + 1][j] と len[i][j - 1] の値の大小によって，どちらを挿入するべきか判定できます．（もちろん小さくなる方を挿入する．）
挿入するほうが決まれば，そのときの dp[i + 1][j] または dp[i][j - 1] の値を加算します．

dp[0][n - 1] < K なら答えはありません．

最後に構築パートですが，これはいつものやつなので雑に書きます．
S[l] == S[r] ならその文字を使うことが確定します．
S[l] != S[r] なら，短くなるほうを選びます．どちらをえらんでも同じ長さを達成できるなら小さい方を使いたいですが，K を超えないギリギリに向かうように選ぶ必要もあります．

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
constexpr int INF = 1e9;
constexpr ll INFLL = 1e18;
 
ll add(ll& a, ll b) {
    return a = min(a + b, INFLL * 2);
}
 
int main() {
    string S;
    ll K;
    cin >> S >> K;
    int const n = S.size();
    vector<vector<int>> len(n, vector<int>(n, INF));
    for(int i = n - 1; i >= 0; --i) {
        len[i][i] = 1;
        for(int j = i + 1; j < n; ++j) {
            if(S[i] == S[j]) {
                len[i][j] = (i + 1 == j ? 2 : len[i + 1][j - 1] + 2);
            }
            len[i][j] = min(len[i][j], min(len[i + 1][j], len[i][j - 1]) + 2);
        }
    }
    vector<vector<ll>> dp(n, vector<ll>(n));
    for(int i = n - 1; i >= 0; --i) {
        dp[i][i] = 1;
        for(int j = i + 1; j < n; ++j) {
            if(S[i] == S[j]) {
                add(dp[i][j], (i + 1 == j ? 1 : dp[i + 1][j - 1]));
            } else {
                int min_len = min(len[i + 1][j], len[i][j - 1]);
                if(len[i + 1][j] == min_len) {
                    add(dp[i][j], dp[i + 1][j]);
                }
                if(len[i][j - 1] == min_len) {
                    add(dp[i][j], dp[i][j - 1]);
                }
            }
        }
    }
 
    if(dp[0][n - 1] < K) {
        cout << "NONE" << endl;
        return 0;
    }
 
    ll t = 1;
    string l_ans;
    int l = 0, r = n - 1;
    while(l < r) {
        if(S[l] == S[r]) {
            l_ans += S[l++];
            r--;
        } else {
            if(len[l + 1][r] < len[l][r - 1]) {
                l_ans += S[l++];
            } else if(len[l + 1][r] > len[l][r - 1]) {
                l_ans += S[r--];
            } else {
                ll t2 = t + (S[l] < S[r] ? dp[l + 1][r] : dp[l][r - 1]);
                if(t2 > K && S[l] < S[r] || t2 <= K && S[l] > S[r]) {
                    l_ans += S[l++];
                } else {
                    l_ans += S[r--];
                }
                if(t2 <= K) {
                    t = t2;
                }
            }
        }
    }
    auto r_ans = l_ans;
    reverse(begin(r_ans), end(r_ans));
    if(l == r) {
        l_ans += S[l];
    }
    cout << l_ans + r_ans << endl;
}

感想

こういう問題は苦手．

AGC001 C - Shorten Diameter

問題文

https://agc001.contest.atcoder.jp/tasks/agc001_c

解法

解説と（ちょっとだけ）違ったので一応書いておきます．
まずBFSで全点対最短路を求めておいて，頂点 v から K より離れた頂点の数を sz[v] とします．
あとは sz[v] の大きい方から貪欲に削除していきます． v を消した時，関係のある w に対して sz[w] の値をデクリメントすれば良いです．
これは O(N^2) でできます．

ソースコード

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

using ll = long long;

constexpr int INF = 1e9;

vector<int> bfs(vector<vector<int>> const& g, int s) {
    int const n = g.size();
    vector<int> d(n, INF);
    d[s] = 0;
    queue<int> que;
    que.push(s);
    while(!que.empty()) {
        int v = que.front();
        que.pop();
        for(auto to : g[v]) {
            if(d[to] != INF) {
                continue;
            }
            d[to] = d[v] + 1;
            que.push(to);
        }
    }
    return d;
}

int main() {
    int N, K;
    cin >> N >> K;
    vector<vector<int>> g(N);
    for(int i = 0; i < N - 1; ++i) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    vector<vector<int>> vs(N);
    vector<int> sz(N);
    for(int i = 0; i < N; ++i) {
        auto d = bfs(g, i);
        for(int j = 0; j < N; ++j) {
            if(d[j] > K) {
                vs[i].push_back(j);
                sz[i]++;
            }
        }
    }

    int res = 0;
    while(true) {
        auto it = max_element(sz.begin(), sz.end());
        if(*it == 0) {
            break;
        }
        int v = it - sz.begin();
        sz[v] = 0;
        for(auto w : vs[v]) {
            sz[w]--;
        }
        vs[v].clear();
        res++;
    }
    cout << res << endl;
}

感想

証明してないけど，sz[v] が K より大きいものをできるだけ一気に減らしたいわけで，それはつまり sz[v] が大きい方を消せばデクリメントが一気にできるから嬉しいよね，みたいな．

Codeforces Round #407 (Div. 2) D. Weird journey

問題文

http://codeforces.com/contest/789/problem/D

解法

まず，同じ辺を2回通るパスという時点でオイラーツアーが思い浮かびます．
自己辺を考えるのはめんどうなので，とりあえずない場合を考えると，条件を満たすパスがあるかどうかは，「一度のDFSによって辿れる頂点の次数の総和が，辺の個数 m の2倍になっている」ことと同値である（よね？）とわかります．
この時，隣接する任意の2つの辺について，それら2つを1回だけ通り，その他の辺を2回通るパスが明らかに存在します．
なので，この隣接する2辺のペアを適当に求めます（1つの頂点に着目して，出てる辺から2つ選べば良いです）．
最後に自己辺ですが，まあ実験すればすぐわかるんですけど，こいつらは自由に使えます．
なので，最後に 自己辺の数 * (自己辺を除くその他の辺) + (自己辺から2つ選ぶ選び方) を足してやれば解けます．

ソースコード

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

using ll = long long;
using pii = pair<int, int>;

using graph = vector<vector<int>>;

int dfs(graph const& g, int v, int p, vector<bool>& used) {
    int res = g[v].size();
    used[v] = true;
    for(auto to : g[v]) {
        if(to == p || used[to]) {
            continue;
        }
        res += dfs(g, to, v, used);
    }
    return res;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    graph g(n);
    int root = -1;
    vector<vector<int>> v(n);
    int self_cnt = 0;
    for(int i = 0; i < m; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        a--; b--;
        root = a;
        if(a == b) {
            g[a].push_back(a);
            self_cnt++;
        } else {
            g[a].push_back(b);
            g[b].push_back(a);
            v[a].push_back(i);
            v[b].push_back(i);
        }
    }

    vector<bool> used(n);
    if(dfs(g, root, -1, used) + self_cnt != 2 * m) {
        printf("0\n");
    } else {
        ll res = 0;
        for(auto x : v) {
            if(x.size() != 0) {
                res += x.size() * (x.size() - 1) / 2;
            }
        }
        res += self_cnt * (m - self_cnt);
        res += self_cnt * (self_cnt - 1) / 2;
        printf("%lld\n", res);
    }
}

感想

あくまで辺を頂点と見たグラフが連結であればよいので，頂点自体が連結である必要はないです（罠）．
あと入力が 10^6 だったのを忘れて cin で TLE 食らってしまった．

Codeforces Round #404 (Div.2) E. Anton and Permutation

問題文

http://codeforces.com/contest/785/problem/E

解法

平方分割 + 2次元BITで解いた．[0...m] x [0...n] で二次元．m は n / sqrt(n)．
l[i] から r[i] の間に完全に含まれているブロックは BIT 上で計算し，端っこの部分は生で持っている配列を使って計算する．
bit.sum(lb, a, rb, b) とすると lb から rb - 1 までのブロックにおける [a..b) の数を求められる．

計算量は O(Q * (sqrt(N) + log^2(N)))．

ソースコード

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

using ll = long long;

template <typename T>
class fenwick_tree2d {
public:
    fenwick_tree2d(int h, int w)
        : H(h), W(w), dat(H, std::vector<T>(W))
    {}

    void add(int i, int j, T value) {
        for(; i < H; i |= i + 1) {
            int jj = j;
            for(; jj < W; jj |= jj + 1) {
                dat[i][jj] += value;
            }
        }
    }

    // [0..i] x [0..j]
    T sum(int i, int j) const {
        T res = 0;
        for(; i >= 0; i = (i & (i + 1)) - 1) {
            int jj = j;
            for(; jj >= 0; jj = (jj & (jj + 1)) - 1) {
                res += dat[i][jj];
            }
        }
        return res;
    }

    // [i1...i2) x [j1...j2)
    T sum(int i1, int j1, int i2, int j2) const {
        return sum(i2 - 1, j2 - 1) - sum(i1 - 1, j2 - 1) - sum(i2 - 1, j1 - 1) + sum(i1 - 1, j1 - 1);
    }

private:
    int const H, W;
    std::vector<std::vector<T>> dat;
};

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> l(q), r(q);
    for(int i = 0; i < q; ++i) {
        cin >> l[i] >> r[i];
        l[i]--; r[i]--;
        if(l[i] > r[i]) {
            swap(l[i], r[i]);
        }
    }

    vector<int> a(n);
    for(int i = 0; i < n; ++i) {
        a[i] = i;
    }
    int const B = sqrt(n) + 1;
    fenwick_tree2d<int> bit(n / B + 1, n);
    for(int i = 0; i < n; ++i) {
        bit.add(i / B, i, 1);
    }

    ll inv = 0;
    for(int i = 0; i < q; ++i) {
        if(l[i] != r[i]) {
            int lb = l[i] / B, rb = r[i] / B;
            if(lb + 1 < rb) {
                int l_lt = bit.sum(lb + 1, 0, rb, a[l[i]]);
                int l_gt = bit.sum(lb + 1, a[l[i]] + 1, rb, n);
                int r_lt = bit.sum(lb + 1, 0, rb, a[r[i]]);
                int r_gt = bit.sum(lb + 1, a[r[i]] + 1, rb, n);
                inv += l_gt - l_lt + r_lt - r_gt;
            }
            if(lb == rb) {
                for(int j = l[i] + 1; j < r[i]; ++j) {
                    inv += (a[l[i]] < a[j] ? 1 : -1) + (a[r[i]] < a[j] ? -1 : 1);
                }
            } else {
                for(int j = l[i] + 1; j < (lb + 1) * B; ++j) {
                    inv += (a[l[i]] < a[j] ? 1 : -1) + (a[r[i]] < a[j] ? -1 : 1);
                }
                for(int j = rb * B; j < r[i]; ++j) {
                    inv += (a[l[i]] < a[j] ? 1 : -1) + (a[r[i]] < a[j] ? -1 : 1);
                }
            }
            inv += (a[l[i]] < a[r[i]] ? 1 : -1);

            bit.add(l[i] / B, a[l[i]], -1);
            bit.add(r[i] / B, a[r[i]], -1);
            swap(a[l[i]], a[r[i]]);
            bit.add(l[i] / B, a[l[i]], 1);
            bit.add(r[i] / B, a[r[i]], 1);
        }
        cout << inv << endl;
    }
}

感想

メモリもTLEも怖すぎる．

Codeforces Round #404 (Div.2) D. Anton and School - 2

問題文

http://codeforces.com/contest/785/problem/D

解法

条件に合う部分列の，一番右端の "(" の位置を総当りして計算します．
その位置から左に（その位置自体も含めて）"(" が $x$ 個あり，右に ")" が $y$ 個ある時，求める答えは $\displaystyle \sum_{i = 1}^{\min (x, y)}({_{x-1}C_{i-1}} \times {_yC_i})$ となります．簡単のため $x < y$ の時を考えます．
右辺の各 i についての式 $_{x-1}C_{i-1} \times _yC_i$ が意味するものを考えます．式変形して，$_{x-1}C_{x-i} \times _yC_i$ としておきます．
これは $x - 1$ 人からなるグループから $x - i$ 人を選び，$y$ 人からなるグループから $i$ 人を選ぶ組み合わせに対応します．つまり，$x - 1 + y$ 人から $x$ 人を選ぶ方法のうち，$x - 1$ 人の方から $x - i$ 人を選ぶときの組み合わせに対応します．
すると，$i$ を $1$ から $x$ まで動かした時，$x - 1 + y$ 人から $x$ 人を選ぶ方法すべてを網羅することになります．よって，
$\displaystyle \sum_{i = 1}^{x}({_{x-1}C_{i-1}} \times {_yC_i}) = _{x+y-1}C_x$
が成り立ち，求めたい値を O(1) で求めることができます．（前計算は必要です．）

・おまけ
ちょっと一般化すると
$\displaystyle \sum_{i=0}^z{_xC_i}{_yC_{z-i}} = _{x+y}C_{z}~ (z \leq x)$
で，$z = x$ とすれば
$\displaystyle \sum_{i=0}^x{_xC_i}{_yC_i} = _{x+y}C_{x}$

ソースコード

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

using ll = long long;

// modulo は略

const int MOD = 1000000007;
using mod = modulo<MOD, true>;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    vector<int> left(n + 1), right(n + 1);
    for(int i = 0; i < n; ++i) {
        left[i + 1] = left[i] + (s[i] == '(');
        right[n - i - 1] = right[n - i] + (s[n - i - 1] == ')');
    }
    mod res = 0;
    for(int i = 1; i <= n; ++i) {
        if(s[i - 1] != '(') {
            continue;
        }
        if(right[i] != 0) {
            res += comb<MOD>(left[i] + right[i] - 1, left[i]);
        }
    }
    cout << (ll)res << endl;
}

感想

式はすぐ出て来るが，変形で詰まった．

Codeforces ECR #31 F. Anti-Palindromize

問題文

http://codeforces.com/contest/884/problem/F

解法

最小費用流で解ける．
まず，各アルファベットに対応する26個の頂点と，N / 2 個からなる文字列の前半（ないし後半）に対応する頂点をもつグラフをつくる．
それぞれのアルファベットから，文字列の各位置に対して辺を張る．
以下ではアルファベットの頂点番号を N / 2 + (c - 'a') とする．
頂点 N / 2 + (c - 'a') から頂点 i (0 <= i < N / 2) にフローが流れることを，S[i] または S[N - 1 - i] にアルファベット c を配置するということに対応付ける．
こうする時，辺のコストは max(S[i] == c ? b[i] : 0, S[N - 1 - i] == c ? b[N - 1 - i] : 0) とすることができる．
もちろん容量は1である．
source からは各アルファベットに対して辺を張り，コストは0，容量はそれぞれのアルファベットの出現数とする．
また，文字列の各位置に対応する頂点から sink に辺を張るのだが，これはコスト0，容量2としておく．
以上のように辺をはると，同じ頂点 i (0 <= i < N / 2) に対して同じ文字は割り当てられず，それぞれの頂点にちょうど2個のアルファベットを割り当てることができる．

ソースコード

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

using ll = long long;

using weight = int;

constexpr int INF = 1e9;

struct edge {
    int to, cap;
    weight cost;
    int rev;
};

using edges = std::vector<edge>;
using graph = std::vector<edges>;

void add_edge(graph& g, int from, int to, int cap, weight cost) {
    g[from].push_back(edge{to, cap, cost, (int)g[to].size()});
    g[to].push_back(edge{from, 0, -cost, (int)g[from].size()-1});
}

weight min_cost_flow(graph& g, int s, int t, weight f) {
    using P = std::pair<weight, int>;
    weight res = 0;
    std::vector<weight> h(g.size(), 0);
    std::vector<weight> dist(g.size());
    std::vector<int> prevv(g.size()), preve(g.size());
    while(f > 0) {
        std::priority_queue<P, std::vector<P>, std::greater<P>> que;
        std::fill(dist.begin(), dist.end(), INF);
        dist[s] = 0;
        que.push(P{dist[s], s});
        while(!que.empty()) {
            P p = que.top(); que.pop();
            int v = p.second;
            if(dist[v] < p.first) {
                continue;
            }
            for(int i = 0; i < (int)g[v].size(); ++i) {
                edge& e = g[v][i];
                if(e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) {
                    dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
                    prevv[e.to] = v;
                    preve[e.to] = i;
                    que.push(P{dist[e.to], e.to});
                }
            }
        }
        if(dist[t] == INF) {
            return -1;
        }
        for(int v = 0; v < (int)g.size(); ++v) {
            h[v] += dist[v];
        }

        weight d = f;
        for(int v = t; v != s; v = prevv[v]) {
            d = min(d, g[prevv[v]][preve[v]].cap);
        }
        f -= d;
        res += d * h[t];
        for(int v = t; v != s; v = prevv[v]) {
            edge& e = g[prevv[v]][preve[v]];
            e.cap -= d;
            g[v][e.rev].cap += d;
        }
    }
    return res;
}


int main() {
    int N;
    string S;
    cin >> N >> S;
    vector<int> b(N);
    for(int i = 0; i < N; ++i) {
        cin >> b[i];
    }
    vector<int> cnt(26);
    for(auto c : S) {
        cnt[c - 'a']++;
    }

    graph g(N / 2 + 26 + 2);
    int const source = N / 2 + 26;
    int const sink = source + 1;
    for(int i = 0; i < 26; ++i) {
        add_edge(g, source, N / 2 + i, cnt[i], 0);
    }
    for(int i = 0; i < N / 2; ++i) {
        add_edge(g, i, sink, 2, 0);
        for(int j = 0; j < 26; ++j) {
            int cost = 0;
            if(S[i] - 'a' == j) {
                cost = max(cost, b[i]);
            }
            if(S[N - 1 - i] - 'a' == j) {
                cost = max(cost, b[N - 1 - i]);
            }
            add_edge(g, N / 2 + j, i, 1, -cost);
        }
    }

    cout << -min_cost_flow(g, source, sink, N) << endl;
}

AOJ 2294 Entangled with Lottery

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2294

解法

ゴールから見るDPでやります．

dp[i][j][k] := 高さ (H から) i まで見た時に，位置 j にいて，それまでに猫が k 本引いているような確率

とします．
高さ 1 から i までに，うさぎがすでに引いている本数を m とすると，猫が引ける高さは残り i - m 箇所です．
今見ている高さがすでにうさぎによって線が引かれていれば，単純に swap するだけです．
引かれていないなら，今見ている高さに猫が線を引く確率 q は，
$\displaystyle q = \frac{_{i - m - 1}C_{K - k - 1}}{_{i - m}C_{K - k}} = \frac{K - k}{i - m}$
となります．
引いた上で，今見ている位置 j に関係する部分に線が引かれる確率 p は，端ならば $\displaystyle p = \frac{1}{N - 1}$，端でなければ $\displaystyle \frac{2}{N - 1}$ です．
あとは，dp[i][j][k] を，「その高さに線をそもそも引かない」「その高さに線を引き，かつそれが j に関係する」「その高さに線を引き，かつそれが j に関係しない」場合の3つに遷移させるだけです．

ソースコード

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

using pii = pair<int, int>;

int main() {
    cout << fixed << setprecision(10);
    int H, N, P, M, K;
    cin >> H >> N >> P >> M >> K;
    P--;
    vector<int> sw(H, -1);
    for(int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        sw[a - 1] = b - 1;
    }

    vector<int> sum(H + 1);
    for(int i = 0; i < H; ++i) {
        sum[i + 1] = sum[i] + (sw[i] != -1);
    }
    vector<vector<double>> dp(N, vector<double>(K + 1));
    dp[P][0] = 1;
    double p = 1.0 / (N - 1);
    for(int i = H - 1; i >= 0; --i) {
        vector<vector<double>> nxt(N, vector<double>(K + 1));
        for(int j = 0; j < N; ++j) {
            for(int k = 0; k <= K; ++k) {
                if(dp[j][k] == 0) {
                    continue;
                }
                if(sw[i] == -1) {
                    double q = (double)(K - k) / (i + 1 - sum[i]); // put possibility
                    if(k == K) {
                        nxt[j][k] += dp[j][k] * (1 - q); // (1 - q) == 1
                    } else {
                        if(j != 0) {
                            nxt[j - 1][k + 1] += dp[j][k] * p * q;
                        }
                        if(j != N - 1) {
                            nxt[j + 1][k + 1] += dp[j][k] * p * q;
                        }
                        nxt[j][k] += dp[j][k] * (1 - q);
                        if(j == 0 || j == N - 1) {
                            nxt[j][k + 1] += dp[j][k] * q * (N - 2) / (N - 1);
                        } else {
                            nxt[j][k + 1] += dp[j][k] * q * (N - 3) / (N - 1);
                        }
                    }
                } else {
                    if(sw[i] == j) {
                        nxt[sw[i] + 1][k] += dp[j][k];
                    } else if(sw[i] + 1 == j) {
                        nxt[sw[i]][k] += dp[j][k];
                    } else {
                        nxt[j][k] += dp[j][k];
                    }
                }
            }
        }
        dp = move(nxt);
    }

    double res = 0;
    for(int i = 0; i < N; ++i) {
        res = max(res, dp[i][K]);
    }
    cout << res << endl;
}