トップ > 第九回 アルゴリズム実技検定

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

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 だと ord や chr で都度変換してると面倒なので 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;
}