ECR114 F. Occurrences

前書き

想定解法より計算量が良かったというのと、$m\leq 10 ^ {18}$ とかでも解けたので。

問題

Problem - F - Codeforces

解法

(前半パートはかなり雑なので、公式解説を併せて読むことを推奨します)

作る列 $a$ に $A_{i,j}$ が含まれる場合を考える。このとき、$a$ において $A _ { i , j }$ の次は $A _ { i , j + 1}$ が置かれていなければ条件に反する。同様に、$a$ において $A _ { i , j }$ の前は $A _ { i , j - 1 }$ が置かれていなければ条件に反する。

そこで、「$x$ の後は $y$ が置かれていなければならず、また $y$ の前は必ず $x$ が置かれていなければならない」のような条件に対して $(x,y)$ の有向辺を張った有向グラフ $D$ を構築する。

まず、$D$ の連結成分であって、連結成分全体が有向パスでないものに含まれる頂点は $a$ に置くことが出来ない。これは、入次数または出次数が $2$ 以上の頂点が存在する場合はその頂点で必ず条件に反し、有向サイクルであるような場合は $a$ の長さが有限とはならないことから分かる。

$D$ の連結成分であって、連結成分全体が有向パスであるようなものに関しては、パスに現れる順番に $a$ に置けば条件に反しない。

以上より、$D$ の連結成分であって、連結成分全体が有向パスであるようなものを $P _ 1,\ldots, P _ t$ とすれば、$\displaystyle \sum_{i=1}^{a} |P _ {b _ i}| = m\;(1\leq b_i \leq t)$ を満たす列 $b$ を数え上げる問題となる。

更に言い換えると、これは $C _ i := \# \{ j \mid | P _ j | = i \}$ の母関数 $\displaystyle f(x) = \sum _ {i = 0} ^ \infty C _ i \cdot x _ i$ に対して $\displaystyle [ x ^ m ] \sum _ {i = 0} ^ \infty f(x) ^ i = [ x ^ m ] \dfrac{1}{1 - f(x)}$ を求める問題となる。ここで、$C _ 0 = 0$ であるから $\dfrac{1}{1 - f(x)}$ は問題なく定義される。

$\dfrac{1}{1 - f(x)} \bmod x ^ {m + 1}$ は $O(m \log m)$ で計算できるので、この問題を $O(n + k + \sum c _ i + m \log m)$ で解くことが出来た。

本問では $m\leq 3\times 10 ^ 5$ なのでこれで十分であるが、求めたいものは $\dfrac{1}{1 - f(x)}$ の $m $ 次の項の係数のみであるから、Bostan Mori のアルゴリズムを用いれば $O(n + k + \sum c _ i + k \log k \log m)$ で解くことも可能である。

SIMDで愚直解を通す

ABC091 D - Two Sequences

問題

D - Two Sequences

概要

長さ $N$ の整数列 $A,B$ に対して $\displaystyle \bigoplus _{1\leq i,j\leq N} A _ i + B _ j$ を計算する問題。

解法

数列の要素は $2^{28}$ 未満なので、和は $32$ bit に収まる。$256$ bit に $A$ を $8$ 要素ずつ詰めて愚直にやる。

実装

Submission #29355762 - AtCoder Beginner Contest 091

AC135 F - Delete 1, 4, 7, ...

問題

atcoder.jp

解法

$k$ 回篩った後に残る数のパターンは $3 ^ k$ の周期を持つ。詳細は省くが周期毎の和は計算できるので、端数が計算出来ればよい。そこで、以後 $N\lt 3 ^ K$ を仮定する。

$1$ 回篩うたびに列の要素数 $n$ は $n - \left\lceil \dfrac{n}{3} \right\rceil = \left\lfloor \dfrac{2n}{3} \right\rfloor$ へと減少する。$3 ^ {29} \lt 10 ^ {14} \lt 3 ^ {30}$ であり、$N = 3 ^ {29} - 1, K = 29$ では $536870911$ 個、$N=10 ^ {14},K=30$ では $521509504$ 個の要素が残り、この辺りが最悪ケースと考えられる。

$K$ 回篩った後の $i$ 番目 (1-indexed) の要素は、$f(x):=\left\lceil \dfrac{3x}{2}\right\rceil$ に対して $\underbrace{f(f(\cdots f}_{K 個}(i)\cdots ))$ として計算される。従って、愚直に答えを計算しようとすれば約 $1.56 \times 10 ^ {10}$ 回程度の演算を要する。

各要素は最大で $10 ^ {14}$ にも及ぶので、$64$ bit 整数を用いて記憶する必要がある。従って、avx2 で用いる $256$ bit のレジスタに $4$ つ格納でき、理想的には $4$ 倍の高速化が期待される。

計算回数が (理想的に) $1/4$ になると仮定しても依然として $3.90 \times 10 ^ 9$ 回程度となるが、上記の最悪ケースを試すと 1650 ms 程度で実行が終了するので投げてみるとおおよそ同じような実行時間で AC が得られる。

実装

Submission #29357608 - AtCoder Regular Contest 135

Educational Codefoeces Round 107 G. Chips on a Board

問題

codeforces.com

概要

問題を言い換えると,次のような問題が解ければよいことが分かる.

長さ $N$ で各要素が $0$ 以上 $M $ 未満の非減少な非負整数列 $c$ が与えられる.以下の形式で表されるクエリが $Q$ 個与えられるので,それぞれ順番に処理せよ.

  • l r v : $\displaystyle \bigoplus _ {i = l} ^ {r - 1} (c _ i - v)$ が $0$ でなければ A と出力,$0$ ならば B と出力.ここで,$\oplus$ はビット毎の排他的論理和であり,また $c _ l \geq v$ が保証される.

実行時間制限 : 5 sec

制約

  • $1\leq N, M, Q \leq 2\cdot 10 ^ 5$
  • $0\leq c _ i \lt M $
  • 各クエリ l r v について,
    • $0\leq l \lt r \leq N $
    • $0\leq v \lt M $

解法

如何にも SIMD で頑張れば通りそうな問題.クエリ処理で現れる $c _ i - v$ は $2\times 10 ^ 5$ 未満なので,32 bit 整数で扱うことができる.従って,256 bit のレジスタで $8$ つずつまとめて処理することで,高速化できる.

実装

Submission #149951251 - Codeforces

yukicoder No.1827 最長部分スーパーリッチ門松列列

問題

yukicoder.me

解法

$\displaystyle v = \min _ { i : \mathrm{even} } a _ i \gt \max _ { i : \mathrm{odd} } a _ i$ または $\displaystyle v = \min _ { i : \mathrm{odd} } a _ i \gt \max _ { i : \mathrm{even} } a _ i$ を満たす $v = p _ k$ を固定した場合の長さの最大値を考える。

列 $x = (x _ 1, \ldots, x _ N)$ および $y = (y _ 1, \ldots, y _ {N - 1})$ を以下で定義する。 $$ \begin{aligned} x _ i & := \begin{cases} -1 & \text{if $p _ i = v\;(\mathrm{i.e.}\; i = k)$} \\ 0 & \text{if $p _ i \lt v$} \\ +1 & \text{if $p _ i \gt v$} \end{cases} , \\ y _ i & := \begin{cases} 1 & \text{if $x _ i \neq x _ { i + 1 }$} \\ 0 & \text{if $x _ i = x _ { i + 1 }$} \end{cases} . \end{aligned} $$

$x$ において同じ値が連続する部分を $1$ つのブロックとして見ることにすると、例えば $x,y$ は下図のようになる。

f:id:suisen_kyopro:20220129001604p:plain

$\displaystyle p _ k = \min _ { i : \mathrm{even} } a _ i \gt \max _ { i : \mathrm{odd} } a _ i$ または $\displaystyle p _ k = \min _ { i : \mathrm{odd} } a _ i \gt \max _ { i : \mathrm{even} } a _ i$ を満たす最長の門松列列を得るためには、$i\gt k$ の部分に関しては $x$ の値が $0,1,0,1,\ldots$ となるように添字の小さい方から貪欲に選ぶのが最適であり、$i\lt k$ の部分に関しては $x$ の値が $\ldots,1,0,1,0$ となるように添字の大きい方から貪欲に選ぶのが最適である。つまり、最長の門松列列の長さは $(\text{ブロックの個数}) - (\text{$-1$ ブロックに隣接する $1$ ブロックの個数})$ として求めることが出来る。

$-1$ ブロックに隣接する $1$ ブロックの個数に関しては、$x _ i = -1$ となるのは $i = k$ に限られるので $x _ {k - 1} = 1$ と $x _ {k + 1} = 1$ をチェックすればよく、$O(1)$ で計算できる。 一方、$p_k$ の昇順に見るなど、適切な順序で見れば $x$ 自体の更新箇所は毎回 $O(1)$ 個で済むが、要素の更新に対してブロック数を管理するのはやや面倒である 1

ここで、ブロックの個数は $y_i=1$ を満たす $i$ の個数に $1$ を加えたものに一致することに注目する。$x$ の更新に対して $y$ を更新するのは容易であるから、$x$ のブロック数の代わりに $y$ と $y_i=1$ を満たす $i$ の個数を管理することにすれば、これは $O(1)$ で更新可能である。

以上より、各テストケースを $ \Theta(N)$ で解くことが出来た。

実装

提出 (C++17 (gcc 11.2.0 + boost 1.78.0), 56 ms, AC)

#include <iostream>
#include <vector>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;
    while (t --> 0) {
        int n;
        std::cin >> n;
        std::vector<int> p(n);
        for (auto &e : p) {
            std::cin >> e;
            --e;
        }
        std::vector<int> q(n);
        for (int i = 0; i < n; ++i) {
            q[p[i]] = i;
        }
        int block_num = 1;
        std::vector<int> x(n, 1);
        auto update = [&](int i, int v) {
            block_num -= i > 0     and x[i - 1] != x[i];
            block_num -= i + 1 < n and x[i + 1] != x[i];
            x[i] = v;
            block_num += i > 0     and x[i - 1] != x[i];
            block_num += i + 1 < n and x[i + 1] != x[i];
        };

        int ans = 0;
        for (int i : q) {
            update(i, -1);
            int len = block_num;
            len -= i > 0     and x[i - 1] == 1;
            len -= i + 1 < n and x[i + 1] == 1;
            ans = std::max(ans, len);
            update(i, 0);
        }
        std::cout << ans << '\n';
    }
    return 0;
}


  1. いわゆる「区間を管理する set」を用いれば $O(\log N)$ time で更新可能であるが、ここでは割愛する。区間を管理する set に関しては 区間をsetで管理するやつでもうバグらせたくない - むげんのぶろぐ などを参照。

第九回 アルゴリズム実技検定

A - アトラクション

問題文の通りに判定する。

h, w = map(int, input().split())
a, b = map(int, input().split())
if a >= h and b <= w:
    print("Yes")
else:
    print("No")

B - 穴の開いた硬貨

全ての硬貨が互いに倍数・約数関係にあるので、大きい順に貪欲に使うことで硬貨の枚数を最小化できる。

従って、各 $C _ i := B _ i - A _ i$ に対して $C _ i \bmod 100 \geq 50$ なら $50$ 円玉が一枚、$C _ i \bmod 10 \geq 5$ なら $5$ 円玉が一枚必要となる。

ans = 0
for _ in range(int(input())):
    a, b = map(int, input().split())
    r = b - a
    ans += r % 100 >= 50
    ans += r % 10 >= 5
print(ans)

C - 最速正解者

問題文の通りに実装する。Python だと ordchr で都度変換してると面倒なので dict で処理すると楽そう。

d = {}
for i in range(int(input())):
    p, v = input().split()
    if v == 'WA' or p in d:
        continue
    d[p] = i + 1
for key in 'ABCDEF':
    print(d[key])

D - 試験

問題文で与えられている通りに順列 $P = (1, 2, \ldots, N)$ をソートする。

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

int main() {
    int n;
    std::cin >> n;
    std::vector<int> a(n), b(n);
    for (auto &e : a) std::cin >> e;
    for (auto &e : b) std::cin >> e;

    std::vector<int> p(n);
    std::iota(p.begin(), p.end(), 0);

    std::sort(
        p.begin(), p.end(),
        [&](int i, int j) {
            if (a[i] + b[i] != a[j] + b[j]) {
                return a[i] + b[i] > a[j] + b[j];
            } else if (a[i] != a[j]) {
                return a[i] > a[j];
            } else {
                return i < j;
            }
        }
    );

    for (int i = 0; i < n; ++i) {
        std::cout << p[i] + 1 << " \n"[i == n - 1];
    }
    return 0;
}

E - キーボード

問題文通りに注意深く実装する。

#include <iostream>

int main() {
    std::string s;
    std::cin >> s;
    int n = s.size();

    long long ans = 0;

    char p;

    for (int i = 0; i < n; ++i) {
        if (i == 0) {
            ans += 500;
        } else if (p == s[i]) {
            ans += 301;
        } else if (('1' <= p and p <= '5') == ('1' <= s[i] and s[i] <= '5')) {
            ans += 210;
        } else {
            ans += 100;
        }
        p = s[i];
    }
    std::cout << ans << std::endl;

    return 0;
}

F - 将棋のように

幅優先探索。予め可能な遷移 $(dx,dy)$ を列挙しておくと楽?

#include <iostream>
#include <deque>
#include <vector>

int main() {
    int a, b;
    std::cin >> a >> b;
    --a, --b;

    std::vector<std::pair<int, int>> trans;
    for (int i = -1; i <= +1; ++i) {
        std::string s;
        std::cin >> s;
        for (int j = -1; j <= +1; ++j) {
            if (s[j + 1] == '#') {
                trans.emplace_back(i, j);
            }
        }
    }

    std::vector vis(9, std::vector(9, false));
    vis[a][b] = true;
    int ans = 0;

    std::deque<std::pair<int, int>> dq { { a, b } };
    while (dq.size()) {
        auto [i, j] = dq.front();
        dq.pop_front();
        ++ans;
        for (auto [dx, dy] : trans) {
            int ni = i + dx, nj = j + dy;
            if (ni < 0 or ni >= 9 or nj < 0 or nj >= 9 or vis[ni][nj]) continue;
            vis[ni][nj] = true;
            dq.emplace_back(ni, nj);
        }
    }
    std::cout << ans << std::endl;
    return 0;
}

G - 連結

Dynamic Connectivity に見えてぎょっとするけど、制約が緩いので毎回愚直に処理してよい。

#include <iostream>
#include <atcoder/dsu>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, q;
    std::cin >> n >> q;
    std::vector<std::vector<int>> g(n);
    while (q --> 0) {
        int t, u, v;
        std::cin >> t >> u >> v;
        --u, --v;
        if (t == 1) {
            if (auto it_u = std::find(g[u].begin(), g[u].end(), v); it_u != g[u].end()) {
                auto it_v = std::find(g[v].begin(), g[v].end(), u);
                g[u].erase(it_u);
                g[v].erase(it_v);
            } else {
                g[u].push_back(v);
                g[v].push_back(u);
            }
        } else {
            atcoder::dsu uf(n);
            for (int i = 0; i < n; ++i) {
                for (int j : g[i]) {
                    uf.merge(i, j);
                }
            }
            if (uf.same(u, v)) {
                std::cout << "Yes\n";
            } else {
                std::cout << "No\n";
            }
        }
    }
    return 0;
}

H - 最長非共通部分列

最長共通部分列 (LCS) と同様の DP で解くことが出来る。

$S[:k]$ で $S$ の先頭 $k$ 文字からなる文字列、つまり $S[ : k ] = S _ 0 S _ 1 \cdots S _ { k - 1 } $ とする。

$$ \mathrm{dp}[i][j] := S[:i], T[:j] に対する問題の答え $$

で定義すれば、$\mathrm{dp}[0][0]=0$ で初期化でき、遷移は以下のように計算出来る。

$$ \mathrm{dp}[i][j] = \begin{cases} \mathrm{dp}[i - 1][j - 1] + 1 & \text{if\; $S _ { i - 1 } \neq T _ { j - 1 } $} \\ \max \{ \mathrm{dp}[i - 1][j], \mathrm{dp}[i][j - 1] \} & \text{otherwise} \end{cases} $$

状態数は $O(NM)$、遷移は $O(1)$ なので、全体 $O(NM)$ でこの問題を解くことが出来た。

#include <iostream>
#include <vector>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::string s, t;
    std::cin >> s >> t;

    const int n = s.size(), m = t.size();

    std::vector dp(n + 1, std::vector(m + 1, 0));

    for (int i = 0; i <= n; ++i) for (int j = 0; j <= m; ++j) {
        if (i and j and s[i - 1] != t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
        if (i) dp[i][j] = std::max(dp[i][j], dp[i - 1][j]);
        if (j) dp[i][j] = std::max(dp[i][j], dp[i][j - 1]);
    }
    
    std::cout << dp[n][m] << std::endl;

    return 0;
}

I - 直通エレベーター

$1$ 階と $N$ 階とエレベーターがある階だけを残したグラフを構築して最短路問題を解けばよい。頂点数は高々 $2M+2$、辺数は高々 $3M+1$ なので Dijkstra 法を用いれば全体 $O(M \log M)$ でこの問題が解ける。

#include <algorithm>
#include <iostream>
#include <limits>
#include <queue>
#include <tuple>
#include <vector>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    long long n;
    int m;
    std::cin >> n >> m;

    std::vector<long long> xs { 1, n };

    std::vector<std::tuple<long long, long long, long long>> ps(m);
    for (int i = 0; i < m; ++i) {
        long long u, v, c;
        std::cin >> u >> v >> c;
        ps[i] = { u, v, c };
        xs.push_back(u);
        xs.push_back(v);
    }

    std::sort(xs.begin(), xs.end());
    xs.erase(std::unique(xs.begin(), xs.end()), xs.end());

    const int k = xs.size();

    std::vector<std::vector<std::pair<int, long long>>> g(k);

    for (int i = 0; i < k - 1; ++i) {
        long long cost = xs[i + 1] - xs[i];
        g[i].emplace_back(i + 1, cost);
        g[i + 1].emplace_back(i, cost);
    }

    for (auto &[u, v, w] : ps) {
        u = std::lower_bound(xs.begin(), xs.end(), u) - xs.begin();
        v = std::lower_bound(xs.begin(), xs.end(), v) - xs.begin();
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }

    using state = std::pair<long long, int>;
    std::priority_queue<state, std::vector<state>, std::greater<state>> pq;
    std::vector<long long> dist(k, std::numeric_limits<long long>::max());

    pq.emplace(dist[0] = 0, 0);
    while (pq.size()) {
        auto [du, u] = pq.top();
        pq.pop();
        if (du != dist[u]) continue;
        for (auto [v, cost] : g[u]) {
            if (long long dv = du + cost; dv < dist[v]) {
                pq.emplace(dist[v] = dv, v);
            }
        }
    }

    std::cout << dist[k - 1] << std::endl;
    return 0;
}

J - 回転と反転

各操作でマス $(i,j)$ がどう移動するかを考える。

  • 時計回り

$$ \begin{pmatrix} 0 & 1 & 0 \\ -1 & 0 & n - 1 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} i \\ j \\ 1 \end{pmatrix} = \begin{pmatrix} n - j - 1 \\ i \\ 1 \end{pmatrix} $$

  • 反時計回り

$$ \begin{pmatrix} 0 & -1 & n - 1 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} i \\ j \\ 1 \end{pmatrix} = \begin{pmatrix} j \\ n - i - 1 \\ 1 \end{pmatrix} $$

  • 上下反転

$$ \begin{pmatrix} -1 & 0 & n - 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} i \\ j \\ 1 \end{pmatrix} = \begin{pmatrix} n - i - 1 \\ j \\ 1 \end{pmatrix} $$

  • 左右反転

$$ \begin{pmatrix} 1 & 0 & 0 \\ 0 & -1 & n - 1 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} i \\ j \\ 1 \end{pmatrix} = \begin{pmatrix} i \\ n - j - 1 \\ 1 \end{pmatrix} $$

従って、これらの行列を用いて各時点の変換行列を保持すればよい。

#include <array>
#include <iostream>
#include <vector>

using Row = std::array<int, 3>;
using Vec = Row;
using Matrix = std::array<Row, 3>;

Matrix operator*(const Matrix &A, const Matrix &B) {
    Matrix C{};
    for (int i = 0; i < 3; ++i) for (int j = 0; j < 3; ++j) for (int k = 0; k < 3; ++k) {
        C[i][k] += A[i][j] * B[j][k];
    }
    return C;
}

Vec operator*(const Matrix &A, const Vec &x) {
    Vec y{};
    for (int i = 0; i < 3; ++i) for (int j = 0; j < 3; ++j) {
        y[i] += A[i][j] * x[j];
    }
    return y;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, q;
    std::cin >> n >> q;

    Matrix CW_inv {
        Row { 0, -1, n - 1 },
        Row { 1, 0, 0 },
        Row { 0, 0, 1 }
    };
    Matrix CCW_inv {
        Row { 0, 1, 0 },
        Row { -1, 0, n - 1 },
        Row { 0, 0, 1 }
    };
    Matrix UD_inv {
        Row { -1, 0, n - 1 },
        Row { 0, 1, 0 },
        Row { 0, 0, 1 }
    };
    Matrix LR_inv {
        Row { 1, 0, 0 },
        Row { 0, -1, n - 1 },
        Row { 0, 0, 1 }
    };

    Matrix A {
        Row { 1, 0, 0 },
        Row { 0, 1, 0 },
        Row { 0, 0, 1 }
    };

    std::vector ans(n, std::vector(n, 0));

    while (q --> 0) {
        int t;
        std::cin >> t;
        if (t == 1) {
            int x, y;
            std::cin >> x >> y;
            --x, --y;
            Vec pos = A * Vec { x, y, 1 };
            ans[pos[0]][pos[1]] ^= 1;
        } else if (t == 2) {
            char c;
            std::cin >> c;
            A = A * (c == 'A' ? CW_inv : CCW_inv);
        } else if (t == 3) {
            char c;
            std::cin >> c;
            A = A * (c == 'A' ? UD_inv : LR_inv);
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            Vec pos = A * Vec { i, j, 1 };
            std::cout << ans[pos[0]][pos[1]];
        }
        std::cout << '\n';
    }
    return 0;
}

(これ難しくない?)

K - ガソリンスタンド

ガソリンスタンドの個数が少ないので、どのガソリンスタンドを経由するかを全探索することを考える。$a _ i$ を経由する場合の $s, t$ 間の最短距離 $d _ i (s, t)$ は $d _ i (s, t) = \mathrm{dist}(a _ i, s) + \mathrm{dist}(a _ i, t)$ と書けるので、各 $i = 1,\ldots, K$ に対して $\mathrm{dist}(a _ i, v)$ を計算しておくことにすれば前計算 $O(K (N + M))$、クエリ $O(K)$ でこの問題を解くことが出来る。全体の計算量は $O(K (N + M + Q))$。

#include <deque>
#include <iostream>
#include <limits>
#include <vector>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m, q, k;
    std::cin >> n >> m >> q >> k;
    std::vector<int> a(k);
    for (int &e : a) {
        std::cin >> e;
        --e;
    }
    std::vector<std::vector<int>> g(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v;
        --u, --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    std::vector dist(k, std::vector(n, -1));
    for (int i = 0; i < k; ++i) {
        dist[i][a[i]] = 0;
        std::deque<int> dq { a[i] };
        while (dq.size()) {
            int u = dq.front();
            dq.pop_front();
            for (int v : g[u]) {
                if (dist[i][v] < 0) {
                    dist[i][v] = dist[i][u] + 1;
                    dq.push_back(v);
                }
            }
        }
    }

    while (q --> 0) {
        int s, t;
        std::cin >> s >> t;
        --s, --t;
        int ans = std::numeric_limits<int>::max();
        for (int i = 0; i < k; ++i) {
            ans = std::min(ans, dist[i][s] + dist[i][t]);
        }
        std::cout << ans << '\n';
    }
    return 0;
}

L - 嘘つきな生徒たち

$A$ を reverse して狭義単調増加にするために必要な要素の変更回数を求める。

添え字 $i _ 1 \lt i _ 2 \lt \cdots \lt i _ k$ を変更せずに残すとすると、狭義単調増加の条件から $j = 1, \ldots, k - 1$ に対して $A _ { i _ j } + (i _ { j + 1 } - i _ j) \leq A _ { i _ { j + 1} }$、すなわち $A _ { i _ j } - i _ j \leq A _ { i _ { j + 1} } - i _ { j + 1 }$ を満たす必要がある。

実はこれでは十分ではなく、添字 $0,\ldots, i _ 1 - 1$ および $i _ k + 1, \ldots, N - 1$ で変更後の値が $0$ 以上 $P$ 以下に収まるために、追加で $0 \leq A _ { i _ 1 } - { i _ 1 }$ および $A _ { i _ k } - { i _ k } \leq P - N + 1$ を満たす必要がある。

以上より、条件をまとめると以下のように書け、これは必要十分条件である。 $$ 0 \leq A _ { i _ 1 } - i _ 1 \leq \cdots \leq A _ { i _ k } - i _ k \leq P - N + 1 $$

条件を満たす添字列のうち最長のものが求まればよく、これはおおよそ Longest Increasing Sequence (LIS) と同様にして $O(N \log N)$ で求められる。

#include <algorithm>
#include <iostream>
#include <limits>
#include <vector>

constexpr int inf = std::numeric_limits<int>::max();

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, p;
    std::cin >> n >> p;

    std::vector<int> a(n);
    for (auto it = a.rbegin(); it != a.rend(); ++it) std::cin >> *it;

    for (int i = 0; i < n; ++i) {
        a[i] -= i;
        if (a[i] > p - n + 1 or a[i] < 0) {
            a[i] = -inf;
        }
    }

    std::vector dp(n + 1, inf);
    dp[0] = 0;

    for (int v : a) {
        if (v == -inf) continue;
        int x = std::upper_bound(dp.begin(), dp.end(), v) - dp.begin();
        dp[x] = v;
    }

    for (int i = n; i >= 0; --i) {
        if (dp[i] == inf) continue;
        std::cout << n - i << std::endl;
        break;
    }

    return 0;
}

M - 名前の変更

index アクセスのできる set があれば 殴れる (解説を確認したところ、想定解でした) 問題。

#include <iostream>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

template <typename T>
using ordered_set = tree<T, null_type, std::less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int main() {
    int n, q;
    std::cin >> n >> q;
    std::vector<std::string> ans(n);
    ordered_set<std::pair<std::string, int>> mp;
    for (int i = 0; i < n; ++i) {
        std::string s;
        std::cin >> s;
        mp.insert(std::pair { ans[i] = s, i });
    }
    while (q --> 0) {
        int x;
        std::string t;
        std::cin >> x >> t;
        --x;
        auto [old_name, i] = *mp.find_by_order(x);
        mp.erase(std::pair { old_name, i });
        mp.insert(std::pair { ans[i] = t, i });
    }
    for (int i = 0; i < n; ++i) {
        std::cout << ans[i] << " \n"[i == n - 1];
    }
    return 0;
}

N - 共通部分

Convex Cut を知っていますか?という問題。

$S$ に対して $T$ の各辺で上記問題の要領で Cut すれば $O(NM)$ で共通部分の凸多角形を求められる。

#include <complex>
#include <iomanip>
#include <iostream>
#include <vector>

using coordinate_t = long double;
using Point = std::complex<coordinate_t>;
using Line = std::pair<Point, Point>;
using Polygon = std::vector<Point>;

constexpr coordinate_t EPS = 1e-9;

int sgn(coordinate_t x) {
    return x < -EPS ? -1 : x > +EPS ? +1 : 0;
}

coordinate_t det(const Point &x, const Point &y) {
    return x.real() * y.imag() - x.imag() * y.real();
}

Point cross_point(const Line &l1, const Line &l2) {
    Point u = l1.second - l1.first, v = l2.first - l2.second, c = l2.first - l1.first;
    return l2.first - det(u, c) / det(u, v) * v;
}

auto convex_cut(const Polygon &convex, const Line &l) {
    const auto &[la, lb] = l;
    Polygon res;
    int sz = convex.size();
    for (int i = 0; i < sz; ++i) {
        int j = i + 1;
        if (j == sz) j -= sz;
        const Point &a = convex[i], &b = convex[j];
        int da = sgn(det(lb - la, a - la));
        if (da >= 0) res.push_back(a);
        int db = sgn(det(lb - la, b - la));
        if (da * db < 0) res.push_back(cross_point(l, Line { a, b }));
    }
    return res;
}

coordinate_t signed_area(const Polygon &poly) {
    coordinate_t res = 0;
    int n = poly.size();
    for (int i = 0; i < n; ++i) res += det(poly[i], poly[(i + 1) % n]);
    return res / 2;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    std::cin >> n >> m;

    Polygon s(n), t(m);
    for (int i = 0; i < n; ++i) {
        coordinate_t x, y;
        std::cin >> x >> y;
        s[i] = { x, y };
    }
    for (int i = 0; i < m; ++i) {
        coordinate_t x, y;
        std::cin >> x >> y;
        t[i] = { x, y };
    }
    
    for (int i = 0; i < m; ++i) {
        s = convex_cut(s, Line { t[i], t[(i + 1) % m] });
    }

    std::cout << std::fixed << std::setprecision(20) << std::abs(signed_area(s)) << std::endl;

    return 0;
}

O - ペアスコア

$B _ j - B _ i = k\; (1\leq k \leq N)$ を満たす $i, j$ の答えへの寄与を考える (主客転倒)。$i, j$ の並べ方は $N - (B _ j - B _ i)$ 通り、それ以外の並べ方は $(N - 2) !$ 通りである。従って、寄与は $S _ k \cdot (N - k) \cdot (N - 2) !$ と求められる。

以上より、$C _ k := \# \{ (i, j) \mid B _ j - B _ i = k \}$ と定義すれば、求める答えは $\displaystyle (N - 2) ! \cdot \sum _ {k = 1} ^ N C _ k \cdot S _ k \cdot (N - k)$ である。

あとは各 $C _ k$ を高速に求められればよいが、$\displaystyle M := \sup_i B_i = 100000$ に対して $B ' _ i = M - B _ i \geq 0$ として代わりに $B _ i + B ' _ j = k + M $ を満たす $i, j$ の組を数えることにする。和の条件になったので、これは高速フーリエ変換を用いて計算できる。計算量は $O(N + M \log M)$。

#include <iostream>
#include <atcoder/modint>
#include <atcoder/convolution>

using mint = atcoder::modint998244353;

constexpr int M = 100000;

int main() {
    int n;
    std::cin >> n;

    std::vector<mint> f(M + 1), g(M + 1);
    for (int i = 0; i < n; ++i) {
        int v;
        std::cin >> v;
        ++f[v];
        ++g[M - v];
    }

    std::vector<int> s(n + 1);
    for (int i = 1; i <= n; ++i) {
        std::cin >> s[i];
    }

    auto c = atcoder::convolution(f, g);
    c.erase(c.begin(), c.begin() + M);
    c.resize(n + 1, 0);

    mint ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans += c[i] * (n - i) * s[i];
    }
    for (int i = 1; i <= n - 2; ++i) {
        ans *= i;
    }
    std::cout << ans.val() << std::endl;
    return 0;
}

AtCoder Beginner Contest 230 G - GCD Permutation

問題

atcoder.jp

解法

$$ f ( x , y ) : = \# \{ ( i , j ) : 1 \leq i \leq j \leq N , \; \gcd ( i , j ) = x , \; \gcd ( P _ i , P _ j ) = y \} $$

とおくと、$x\gt N$ または $y\gt N$ のとき $f(x,y)=0$ なので、答えは $(1)$ で表されます。

$$ \sum _ {x = 2} ^ N \sum _ { y = 2 } ^ N f ( x , y ) \tag{1} $$

$\gcd ( a , b ) = x$ などの等号条件よりも $x \mid \gcd ( a , b ) \iff x\mid a \land x\mid b$ のような倍数条件の方が扱いやすいです。そこで、次のように $g$ を定義します。

$$ g ( x , y ) : = \# \{ ( i , j ) : 1 \leq i \leq j \leq N , \; x \mid \gcd ( i , j ), \; y \mid \gcd ( P _ i , P _ j ) \} $$

このとき、$g(x,y)$ は次のように表されます。

$$ g ( x , y ) = \# \left \{ ( i , j ) \; :\; 1 \leq i \leq j \leq \left\lfloor\frac { N }{ x } \right\rfloor, y \mid P _ { i x }, y \mid P _ { j x} \right \} $$

$c(x,y)$ を $c ( x, y ) := \# \left \{ i \; :\; 1 \leq i \leq \lfloor N / x \rfloor,\; y \mid P _ { i x } \right \}$ で定義すれば、$g(x,y)$ は $c$ を用いて以下のように計算できます。

$$ g(x,y)= \dfrac{c(x,y) \cdot (c(x,y) + 1)}{2} $$

$g$ の計算方法は分かったので、次は $f(x,y)$ を $g$ を使って表します。$\displaystyle g( x , y ) = \sum _ { x \mid x ' } \sum _ { y \mid y ' } f ( x ' , y ' ) $ より、$\displaystyle f ( x , y ) = \sum _ { x \mid a ' } \sum _ { y \mid b ' } \mu ( a ' / x ) \cdot \mu (b ' / y ) \cdot g ( a' , b' )$ です。

これは以下のようにして確かめられますが、倍数系メビウス変換の式なので覚えてしまった方が速いと思います。

証明 $$ \begin{aligned} f ( x , y ) &= \sum _ { x \mid x ' } f ( x' , y ) \cdot \delta _ { x , x ' } \\ &= \sum _ { x \mid x ' } f ( x' , y ) \sum _ { a \mid (x ' / x )} \mu ( a ) \\ &= \sum _ { x \mid x ' } \sum _ { ax \mid x ' } f ( x' , y ) \cdot \mu ( a ) \\ &= \sum _ { x \mid a ' \land a' \mid x ' } f ( x' , y ) \cdot \mu ( a ' / x ) \\ &= \sum _ { x \mid a ' } \mu ( a ' / x ) \sum _ { a' \mid x ' } f ( x' , y ) \\ &= \sum _ { x \mid a ' } \sum _ { y \mid b ' } \mu ( a ' / x ) \cdot \mu (b ' / y ) \sum _ { a' \mid x ' } \sum _ { b' \mid y ' } f ( x' , y' ) \\ &= \sum _ { x \mid a ' } \sum _ { y \mid b ' } \mu ( a ' / x ) \cdot \mu (b ' / y ) \cdot g ( a' , b' ) \end{aligned} $$

(書いてから気づいたんですが、和を展開するのが素直ですね)

以上より、答えは次のように表されます。

$$ \begin{aligned} \sum _ { x = 2 } ^ N \sum _ { y = 2 } ^ N f ( x , y ) &= \sum _ { x = 2 } ^ N \sum _ { y = 2 } ^ N \sum _ { x \mid a ' } \sum _ { y \mid b ' } \mu ( a ' / x ) \cdot \mu (b ' / y ) \cdot g ( a' , b' ) \\ &= \sum _ { a' = 2 } ^ N \sum _ { b' = 2 } ^ N g ( a' , b' ) \sum _ { x \mid a ' , x \neq 1 } \mu ( a ' / x ) \sum _ { y \mid b ', y \neq 1 } \mu (b ' / y ) \\ &= \sum _ { a' = 2 } ^ N \sum _ { b' = 2 } ^ N g ( a' , b' ) \cdot ( \delta _ { a ', 1 } - \mu ( a ' ) ) \cdot ( \delta _ { b ', 1 } - \mu ( b ' ) ) \\ &= \sum _ { a' = 2 } ^ N \sum _ { b' = 2 } ^ N g ( a' , b' ) \cdot \mu ( a ' ) \cdot \mu ( b ' ) \\ &= \sum _ { a' = 2 } ^ N \mu ( a ' ) \sum _ { b' = 2 } ^ N g ( a' , b' ) \cdot \mu ( b ' ) \\ &= \sum _ { a' = 2 } ^ N \mu ( a ' ) \sum _ { b' = 2 } ^ N \dfrac{c(a', b')\cdot (c(a', b') + 1)}{2} \cdot \mu ( b ' ) \end{aligned} $$

まず、外側の和で $\mu (a') = 0$ となる部分は無視してよいです。そして、内側の和でも $\mu (b') = 0$ となる部分は無視してよいです。従って $c(x,y)$ は $\mu(x)\neq 0\land \mu(y)\neq 0$ となる部分しか必要なく、$y \mid P _ { i x } \land \mu(y) \neq 0$ を満たす $y$ の個数は $2 ^ { \omega(P _ { i x }) } - 1$ 個 ($\omega(n)$ は $n$ の異なる素因数の個数) です。$n \leq 2\cdot 10 ^ 5$ では $\omega(n)\leq 6$ なので、これは高々 $63$ 個です。

以下のようなコードを書いて最大ケースでどれくらいの計算回数になるかを見積もると $90809523 \lt 10 ^ 8$ 程度であり、常に $\omega(n)=6$ となる訳ではないことを加味すれば十分高速であることが確かめられます。

実験コード

#include <array>
#include <iostream>
#include <vector>

template <uint32_t N>
struct MobiusFunction {
    constexpr MobiusFunction() : mpf{}, dat{} {
        dat.fill(1);
        for (uint64_t p = 2; p <= N; ++p) {
            if (mpf[p]) continue;
            mpf[p] = p;
            dat[p] = -1;
            for (uint64_t q = p * 2; q <= N; q += p) {
                if (not mpf[q]) mpf[q] = p;
                dat[q] = q % (p * p) ? -dat[q] : 0;
            }
        }
    }
    constexpr int32_t operator()(const uint32_t n) const {
        return dat[n];
    }
private:
    std::array<uint32_t, N + 1> mpf;
    std::array<int32_t, N + 1> dat;
};

constexpr uint32_t N = 200000;
MobiusFunction<N> mobius;

int main() {
    int64_t sum = 0;
    for (uint32_t a = 2; a <= N; ++a) {
        if (not mobius(a)) continue;
        sum += (N / a) * 63;
    }
    std::cout << sum << std::endl;
    return 0;
}

実装

コンパイル時に素因数列挙やメビウス関数の計算をすることで 123 ms で通すことが出来ました (2021/12/15 時点で Fastest)。

atcoder.jp

感想

メビウス関数で和の形にするのは典型手法なんでしょうか

AtCoder Grand Contest 044 C - Strange Dance

想定解とは異なる解法で通しました。計算量は想定解の方がよいです。

問題

AtCoder Grand Contest 044 C - Strange Dance

解法

$ i , j \in \{ 0 , \ldots , 3 ^ N - 1 \} $ に関して、$i$ と $j$ の下位 $k$ trit が等しいならば、$P_i$ と $P_j$ の下位 $k$ trit も等しくなります。そこで、添字を上位 $\left\lfloor \dfrac{N}{2}\right\rfloor$ trit と下位 $N - \left\lfloor \dfrac{N}{2}\right\rfloor$ trit に分けて考えます。

下位 $N - \left\lfloor \dfrac{N}{2}\right\rfloor$ trit に関しては、愚直にシミュレートすることですべての $i \in \{ 0,\ldots, 3 ^ N - 1\} $ に対する $P_i$ の下位 $N - \left\lfloor \dfrac{N}{2}\right\rfloor$ trit を求めます。このパートの計算量は $O( N \cdot 3 ^ {N/2} \cdot | T | )$ です。

続いて、上位 $\left\lfloor \dfrac{N}{2}\right\rfloor$ trit について考えます。難しいのは、下位の桁からの繰上りがあることです。下位 $N - \left\lfloor \dfrac{N}{2}\right\rfloor$ trit を固定すると上位 trit の値に関わらず繰上りが起こるタイミングが等しいことに注目し、下位 trit を固定します。各繰上りの間にサルサが偶数回流れたか、奇数回流れたかを $O(1)$ で求められるように適切な前計算 1 をしておくことで、下位 trit を $\mathrm{lower}$ で固定したときの上位 trit の行先を $O(N \cdot 3^{N/2} \cdot \mathrm{carry}(\mathrm{lower}))$ でシミュレートできます。ここで、 $\mathrm{carry}(\mathrm{lower})$ は下位 trit を$\mathrm{lower}$ で固定したときの繰上りの回数です。$C_R(T)$ を $T$ に含まれる R の数として、$\displaystyle \sum_{\mathrm{lower} = 0 } ^ { 3 ^ {N - \lfloor N/2 \rfloor} - 1} \mathrm{carry}(\mathrm{lower}) = C_R(T) \leq |T| $ よりこのパートも全体 $O( N \cdot 3 ^ {N/2} \cdot | T | )$ で計算できます。

上位 trit の結果と下位 trit の結果をマージすることで答えが得られますが、このパートは $O(3 ^ N)$ で計算できるので、全体の計算量は $O(3 ^ N + N\cdot 3 ^ {N / 2} \cdot | T | )$ となります。

制約を考えるとかなりやばそうなんですが、250 ms くらいで通りました


  1. 例えば、$T$ に対して R を $0$ に、S を $1$ に書き換えて得られる数列の累積 xor を計算しておくとよいです

2018-2019 ACM-ICPC, Asia Dhaka Regional Contest G - Techland

問題

PDF の G です。

頂点番号が 1-indexed で振られた $N$ 頂点の木が与えられる。また、map<int, set<int>> M が空で初期化されている。以下のクエリを処理せよ;

  • 1 X L R: M[X] = { L, L + 1, ..., R } とする。
  • 2 X: M.erase(X) とする。
  • 3 x k v_1 ... v_k: $\min \{ \mathrm{dist}(x, y) \mid \exists 1\leq i\leq k.\; \text{s.t.}\; y\in M[v_i] \}$ を出力する。そのような最小値が存在しない場合は -1 を出力する。

解法

map の更新は愚直にやってよいので、問題となるのは 3 つ目のクエリです。

平方分割をします。バケットサイズを $B$ として $[1,B],[B+1,2B],\ldots,[iB+1,(i+1)B],\ldots$ というように頂点を分割します。各バケットから多始点 BFS を行うことで、すべての頂点 $u$ に対して

$$ d_u(i) = \min \{ \mathrm{dist}(u,v)\mid iB+1\leq v\leq (i+1)B \} $$

を予め計算しておきます。バケットの個数は $O(N / B)$ 個なので、計算量は $O(N ^ 2 / B)$ です。

これにより、区間 $M ( v _ i ) = [ L _ { v _ i } , R _ { v _ i } ]$ に完全に包含されるバケットについては最短距離が $O(1)$ で求まります。そして、このようなバケットの個数は $O(N/B)$ 個です。

また、$[ L _ { v _ i } , R _ { v _ i } ]$ に包含されないバケットであって、$[ L _ { v _ i } , R _ { v _ i } ]$ との共通部分が空でないものは高々 2 つであり、その区間長は $B$ 以下です。この部分に関しては LCA などを用いて一つずつ距離を求めることにすれば、$O(B \log N)$ ないし $O(B)$ で残りの部分が計算できます。

以上より、例えば $B=\sqrt N$ とすれば、タイプ 3 のクエリは $O(k\sqrt{N} \log N)$ や $O(k\sqrt{N})$ で処理することができます。

全体の計算量は $O( (N + \sum k) \sqrt{N} + Q)$ や $O( (N + \sum k \log N) \sqrt{N} +Q)$ となります。

実装

提出リンク

バチャ中に AC したコードそのままです。完全に包含されているブロック達の $\min$ をセグ木で計算していたり、クエリ $O(1)$ LCA を貼ったりしています。かなりごちゃごちゃしていてますが、直す気が起きず...