本稿では、2024年钉耙コーディング中国大学生アルゴリズム設計スーパーリーグ（1）から選出された数問の問題とその解法について説明する。

循環位移（Circular Shift）

HDU - 7433

アプローチ

文字列ハッシュを用いて、文字列Aを2回連結したAAを作成する。この文字列のハッシュ値を計算し、mapまたはsetに記録する。|A| ≤ |B| であるので、B中での長さ|A|のすべての部分文字列のハッシュ値がAAに存在するかどうかを確認すればよい。

実装例

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

struct StringHash {
    using u64 = unsigned long long;
    u64 base = 13331;
    vector<u64> power, hash;
    
    StringHash(string &s) {
        s = " " + s;
        int N = s.size();
        power.resize(N + 1);
        hash.resize(N + 1);
        power[0] = 1;
        hash[0] = 0;
        for (int i = 1; i < s.size(); i++) {
            power[i] = power[i - 1] * base;
            hash[i] = hash[i - 1] * base + s[i];
        }
    }
    
    u64 getHash(int l, int r) {
        return hash[r] - hash[l - 1] * power[r - l + 1];
    }
    
    u64 combine(int l1, int r1, int l2, int r2) {
        return getHash(l1, r1) * power[r2 - l2 + 1] + getHash(l2, r2);
    }
    
    bool isEqual(int l1, int r1, int l2, int r2) {
        return getHash(l1, r1) == getHash(l2, r2);
    }
};

void solve() {
    string a, b;
    cin >> a >> b;
    int len = a.size();
    a = a + a;
    
    StringHash hashA(a), hashB(b);
    set<i64> hashSet;
    
    for (int i = 0; i + len - 1 < a.size(); i++) {
        hashSet.insert(hashA.getHash(i, i + len - 1));
    }
    
    i64 result = 0;
    for (int i = 0; i + len - 1 < b.size(); i++) {
        if (hashSet.count(hashB.getHash(i, i + len - 1)))
            result++;
    }
    cout << result << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

星星（Stars）

HDU - 7434

アプローチ

グループ別背包問題を考慮する。dp[i]を体積iの星に必要な最小コストとする。

実装例

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

void solve() {
    int n, k;
    cin >> n >> k;
    vector<array<i64, 5>> data(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> data[i][1] >> data[i][2] >> data[i][3] >> data[i][4];
    
    vector<i64> dp(k + 1, INT_MAX);
    dp[0] = 0;
    
    for (int i = 1; i <= n; i++) {
        for (int v = k; v >= 0; v--) {
            for (int j = min(v, 4); j >= 0; j--) {
                dp[v] = min(dp[v], dp[v - j] + data[i][j]);
            }
        }
    }
    cout << dp[k] << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

树（Tree）

HDU - 7435

アプローチ

max(a_u, a_v) × |a_u - a_v| を展開すると、max² - max × min となる。この計算結果は2つの値の間的大小関係のみに依存し、木の構造は関係ない。サブツリーの重みを多重集合Sと見なし、新たな要素xを追加する場合の貢献량은以下の通り：

• x = y の場合：f(x,y) = 0
• x < y の場合：f(x,y) = y² - xy
• x > y の場合：f(x,y) = x² - xy

∑1、∑y、∑y² は重み付きBITで維持できる。各ノードの答えはサブツリーとその本身から得られ、オフライン処理をサポートするため、DSU on treeで処理できる。最後に×2するのは、f(a_u, a_v) と f(a_v, a_u) の両方を計算する必要があるためである。モジュロは 2^64 であり、unsigned long long の自然オーバーフローを使用できる。

実装例

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;

template <typename T>
struct BIT {
    int n;
    vector<T> tree;
    
    BIT() {}
    BIT(int _n) : n(_n) {
        tree.resize(n + 1);
    }
    
    void add(int idx, T val) {
        while (idx <= n) {
            tree[idx] += val;
            idx += idx & (-idx);
        }
    }
    
    T sumPrefix(int idx) {
        T res = 0;
        while (idx > 0) {
            res += tree[idx];
            idx -= idx & (-idx);
        }
        return res;
    }
    
    T rangeQuery(int l, int r) {
        if (l > r) return 0;
        return sumPrefix(r) - sumPrefix(l - 1);
    }
};

constexpr int MAXV = 1e6;

struct TreeSolver {
    int nodeCount, order = 0;
    vector<int> subtreeSize, heavyChild, inTime, outTime, eulerNode;
    vector<vector<int>> graph;
    u64 currentScore = 0;
    vector<u64> answer, nodeValue;
    vector<BIT<u64>> bit;
    
    TreeSolver(int n) : nodeCount(n), subtreeSize(n + 1), heavyChild(n + 1),
        inTime(n + 1), outTime(n + 1), eulerNode(n + 1) {
        graph.resize(n + 1);
        answer.resize(n + 1);
        nodeValue.resize(n + 1);
        bit.resize(3, BIT<u64>(MAXV));
    }
    
    void addEdge(int u, int v) {
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    
    void insertNode(int u) {
        u64 val = nodeValue[u];
        currentScore += bit[2].rangeQuery(val + 1, MAXV) - val * bit[1].rangeQuery(val + 1, MAXV);
        currentScore += val * val * bit[0].sumPrefix(val - 1) - val * bit[1].sumPrefix(val - 1);
        
        bit[0].add(val, 1);
        bit[1].add(val, val);
        bit[2].add(val, val * val);
    }
    
    void removeNode(int u) {
        u64 val = nodeValue[u];
        currentScore -= bit[2].rangeQuery(val + 1, MAXV) - val * bit[1].rangeQuery(val + 1, MAXV);
        currentScore -= val * val * bit[0].sumPrefix(val - 1) - val * bit[1].sumPrefix(val - 1);
        
        bit[0].add(val, -1);
        bit[1].add(val, -val);
        bit[2].add(val, -val * val);
    }
    
    u64 getResult() { return currentScore; }
    
    void dfs1(int u, int parent) {
        inTime[u] = ++order;
        eulerNode[order] = u;
        subtreeSize[u] = 1;
        for (int v : graph[u]) {
            if (v != parent) {
                dfs1(v, u);
                subtreeSize[u] += subtreeSize[v];
                if (!heavyChild[u] || subtreeSize[heavyChild[u]] < subtreeSize[v])
                    heavyChild[u] = v;
            }
        }
        outTime[u] = order;
    }
    
    void dfs2(int u, int parent, bool keep) {
        for (int v : graph[u]) {
            if (v != parent && v != heavyChild[u])
                dfs2(v, u, false);
        }
        
        if (heavyChild[u])
            dfs2(heavyChild[u], u, true);
        
        for (int v : graph[u]) {
            if (v != parent && v != heavyChild[u]) {
                for (int i = inTime[v]; i <= outTime[v]; i++)
                    insertNode(eulerNode[i]);
            }
        }
        insertNode(u);
        answer[u] = getResult();
        
        if (!keep) {
            for (int i = inTime[u]; i <= outTime[u]; i++)
                removeNode(eulerNode[i]);
        }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    TreeSolver solver(n);
    
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        solver.addEdge(u, v);
    }
    
    for (int i = 1; i <= n; i++)
        cin >> solver.nodeValue[i];
    
    solver.dfs1(1, 0);
    solver.dfs2(1, 0, false);
    
    u64 ans = 0;
    for (int i = 1; i <= n; i++)
        ans ^= 2ull * solver.answer[i];
    
    cout << ans << '\n';
    return 0;
}

序列立方（Sequence Cubed）

HDU - 7438

アプローチ

直接計算は困難であるため、部分列出现回数の立方和を、元の列から3つの同じ列を選ぶ方案数に変換することを考える。これにより、包除原理を用いて計算できる。

実装例

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

const int MAXN = 255;
const int MOD = 998244353;

i64 dp[MAXN][MAXN][MAXN];
i64 prefix[MAXN][MAXN][MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<int> arr(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> arr[i];
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                if (arr[i] == arr[j] && arr[j] == arr[k])
                    dp[i][j][k] = prefix[i - 1][j - 1][k - 1] + 1;
                
                prefix[i][j][k] = (prefix[i - 1][j][k] + prefix[i][j - 1][k] + prefix[i][j][k - 1]
                    - prefix[i - 1][j - 1][k] - prefix[i - 1][j][k - 1] - prefix[i][j - 1][k - 1]
                    + prefix[i - 1][j - 1][k - 1] + dp[i][j][k] + MOD + MOD + MOD) % MOD;
            }
        }
    }
    
    cout << prefix[n][n][n] << '\n';
    return 0;
}

三元环（Three-Element Cycles）

HDU - 7439

アプローチ

3点有向グラフを考えると、要么成环，要么有一个点入度为2である。点iの入度をd_iとすれば答えは C(n,3) - Σ C(d_i,2) となる。题目における関係から、i → j は i < j かつ f_i < f_j かつ g_i < g_j の場合のみ成立し、そう否则は j → i となる。따라서、この3次元関係に基づき、まず前2次元で i < j かつ f_i ≥ f_j の入度を求め、その後 CDQ分割統治で3次元関係を満たす各点の次数を求める。

実装例

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

template <typename T>
struct FenwickTree {
    int n;
    vector<T> tree;
    
    FenwickTree() {}
    FenwickTree(int _n) : n(_n) {
        tree.resize(n + 1);
    }
    
    void modify(int idx, T val) {
        while (idx <= n) {
            tree[idx] += val;
            idx += idx & (-idx);
        }
    }
    
    T queryPrefix(int idx) {
        T res = 0;
        while (idx > 0) {
            res += tree[idx];
            idx -= idx & (-idx);
        }
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<array<int, 3>> data(n + 1);
    
    for (int i = 1; i <= n; i++) {
        cin >> data[i][0];
        data[i][2] = i;
    }
    for (int i = 1; i <= n; i++)
        cin >> data[i][1];
    
    FenwickTree<i64> bit(n);
    vector<int> indegree(n + 1, 0);
    
    for (int i = n; i >= 1; i--) {
        indegree[i] += bit.queryPrefix(data[i][0]);
        bit.modify(data[i][0], 1);
    }
    
    for (int i = n; i >= 1; i--)
        bit.modify(data[i][0], -1);
    
    auto solveRange = [&](auto &&self, int left, int right) -> void {
        if (left == right) return;
        
        int mid = (left + right) / 2;
        self(self, left, mid);
        self(self, mid + 1, right);
        
        sort(data.begin() + left, data.begin() + mid + 1, [](auto &a, auto &b) {
            if (a[0] != b[0]) return a[0] < b[0];
            return a[1] < b[1];
        });
        
        sort(data.begin() + mid + 1, data.begin() + right + 1, [](auto &a, auto &b) {
            if (a[0] != b[0]) return a[0] < b[0];
            return a[1] < b[1];
        });
        
        int i = left, j = mid + 1;
        while (j <= right) {
            while (i <= mid && data[i][0] < data[j][0]) {
                bit.modify(data[i][1], 1);
                i++;
            }
            indegree[data[j][2]] += bit.queryPrefix(data[j][1] - 1);
            j++;
        }
        for (int k = left; k < i; k++)
            bit.modify(data[k][1], -1);
        
        i = mid;
        j = right;
        while (i >= left) {
            while (j > mid && data[j][0] > data[i][0]) {
                bit.modify(data[j][1], 1);
                j--;
            }
            indegree[data[i][2]] += bit.queryPrefix(data[i][1]);
            i--;
        }
        for (int k = right; k > j; k--)
            bit.modify(data[k][1], -1);
    };
    
    solveRange(solveRange, 1, n);
    
    i64 result = 1LL * n * (n - 1) * (n - 2) / 6;
    for (int i = 1; i <= n; i++)
        result -= 1LL * indegree[i] * (indegree[i] - 1) / 2;
    
    cout << result << '\n';
    return 0;
}

位运算（Bit Operations）

HDU - 7440

アプローチ

真値表を描画すると、nの各ビットについて、0の場合は4通りの方案、1の場合は12通りの方案がある。kビットを列挙し、nの各ビットに対応させて掛け算すればよい。

実装例

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

void solve() {
    int n, k;
    cin >> n >> k;
    i64 result = 1;
    
    for (int i = 0; i < k; i++) {
        if ((n >> i) & 1)
            result *= 12;
        else
            result *= 4;
    }
    cout << result << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

并（Union）

HDU - 7444

アプローチ

点数が少ないが座標が大きいため、座標離散化を考虑する。k個の矩形の面積_unionの期待値を求める問題を考える。全域をスキャンする方法は一部の矩形のみをスキャンするのに適していないため、問題の変換を検討する。

1つの矩形は H × W の格子に貢献し、n個の矩形がどの格子に貢献するかを計算できる。これは1階差分2次元累積和で計算できる。k個の矩形の貢献を1点に集中させると、その点がk個の矩形にカバーされた期待値になる。座標を離散化した後、2点間で構成される矩形の面積が現在覆われる点に対する総貢献となる。

g_i をi個の矩形に覆われた領域の面積之和とする。k個の矩形を選び、i回覆われた領域を列挙する。n - i < k の場合、その領域は少なくともk個の矩形の1つに覆われるので、貢献は g_i となる。n - i ≥ k の場合は計算しない。補集合を考えると、これらの領域がk個の矩形のいずれにも覆されない確率は Σ (1 - C(n-i,k) / C(n,k)) × g_i となる。

実装例

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

template <class T>
constexpr T power(T a, i64 b) {
    T result = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) result *= a;
    }
    return result;
}

constexpr i64 modMul(i64 a, i64 b, i64 p) {
    i64 res = a * b - i64(1.L * a * b / p) * p;
    res %= p;
    if (res < 0) res += p;
    return res;
}

template <i64 P>
struct ModInt {
    i64 x;
    constexpr ModInt() : x{0} {}
    constexpr ModInt(i64 v) : x{norm(v % getMod())} {}
    
    static i64 Mod;
    constexpr static i64 getMod() {
        return P > 0 ? P : Mod;
    }
    constexpr static void setMod(i64 m) { Mod = m; }
    
    constexpr i64 norm(i64 v) const {
        if (v < 0) v += getMod();
        if (v >= getMod()) v -= getMod();
        return v;
    }
    
    constexpr i64 val() const { return x; }
    constexpr ModInt operator-() const { return ModInt(getMod() - x); }
    
    constexpr ModInt &operator*=(const ModInt &rhs) {
        if (getMod() < (1ULL << 31))
            x = x * rhs.x % int(getMod());
        else
            x = modMul(x, rhs.x, getMod());
        return *this;
    }
    
    constexpr ModInt &operator+=(const ModInt &rhs) {
        x = norm(x + rhs.x);
        return *this;
    }
    
    constexpr ModInt &operator-=(const ModInt &rhs) {
        x = norm(x - rhs.x);
        return *this;
    }
    
    constexpr ModInt &operator/=(const ModInt &rhs) { return *this *= rhs.inv(); }
    
    friend constexpr ModInt operator*(ModInt lhs, ModInt rhs) { return lhs *= rhs; }
    friend constexpr ModInt operator+(ModInt lhs, ModInt rhs) { return lhs += rhs; }
    friend constexpr ModInt operator-(ModInt lhs, ModInt rhs) { return lhs -= rhs; }
    friend constexpr ModInt operator/(ModInt lhs, ModInt rhs) { return lhs /= rhs; }
    friend constexpr istream &operator>>(istream &is, ModInt &a) { i64 v; is >> v; a = ModInt(v); return is; }
    friend constexpr ostream &operator<<(ostream &os, const ModInt &a) { return os << a.val(); }
    friend constexpr bool operator==(ModInt a, ModInt b) { return a.val() == b.val(); }
    friend constexpr bool operator!=(ModInt a, ModInt b) { return a.val() != b.val(); }
};

template <> i64 ModInt<0>::Mod = 998244353;

constexpr int MODP = 998244353;
using Z = ModInt<MODP>;

struct CombCalculator {
    int limit;
    vector<Z> fact, invFact, invNum;
    
    CombCalculator() : limit{0}, fact{1}, invFact{1}, invNum{0} {}
    CombCalculator(int n) : CombCalculator() { init(n); }
    
    void init(int m) {
        m = min<i64>(m, Z::getMod() - 1);
        if (m <= limit) return;
        fact.resize(m + 1);
        invFact.resize(m + 1);
        invNum.resize(m + 1);
        
        for (int i = limit + 1; i <= m; i++)
            fact[i] = fact[i - 1] * i;
        
        invFact[m] = fact[m].inv();
        for (int i = m; i > limit; i--) {
            invFact[i - 1] = invFact[i] * i;
            invNum[i] = invFact[i] * fact[i - 1];
        }
        limit = m;
    }
    
    Z factorial(int m) {
        if (m > limit) init(2 * m);
        return fact[m];
    }
    
    Z inverseFactorial(int m) {
        if (m > limit) init(2 * m);
        return invFact[m];
    }
    
    Z inverse(int m) {
        if (m > limit) init(2 * m);
        return invNum[m];
    }
    
    Z C(int n, int m) {
        if (n < m || m < 0) return 0;
        return factorial(n) * inverseFactorial(m) * inverseFactorial(n - m);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<pair<int, int>> leftPos, rightPos;
    vector<i64> xs, ys;
    
    for (int i = 0; i < n; i++) {
        int x1, x2, y1, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        leftPos.emplace_back(x1, y1);
        rightPos.emplace_back(x2, y2);
        xs.push_back(x1);
        xs.push_back(x2);
        ys.push_back(y1);
        ys.push_back(y2);
    }
    
    sort(xs.begin(), xs.end());
    sort(ys.begin(), ys.end());
    int xSize = unique(xs.begin(), xs.end()) - xs.begin();
    int ySize = unique(ys.begin(), ys.end()) - ys.begin();
    xs.resize(xSize);
    ys.resize(ySize);
    
    vector diff(xSize + 1, vector<int>(ySize + 1, 0));
    
    for (int i = 0; i < n; i++) {
        auto &[lx, ly] = leftPos[i];
        auto &[rx, ry] = rightPos[i];
        
        lx = lower_bound(xs.begin(), xs.end(), lx) - xs.begin() + 1;
        rx = lower_bound(xs.begin(), xs.end(), rx) - xs.begin() + 1;
        ly = lower_bound(ys.begin(), ys.end(), ly) - ys.begin() + 1;
        ry = lower_bound(ys.begin(), ys.end(), ry) - ys.begin() + 1;
        
        diff[lx][ly]++;
        diff[lx][ry]--;
        diff[rx][ly]--;
        diff[rx][ry]++;
    }
    
    for (int i = 1; i <= xSize; i++)
        for (int j = 1; j <= ySize; j++)
            diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
    
    vector<Z> covered(n + 1);
    for (int i = 1; i <= xSize; i++)
        for (int j = 1; j <= ySize; j++)
            covered[diff[i][j]] += Z(xs[i] - xs[i - 1]) * (ys[j] - ys[j - 1]);
    
    CombCalculator comb(n);
    
    for (int k = 1; k <= n; k++) {
        Z answer = 0;
        for (int i = 0; i <= n; i++)
            answer += (comb.C(n, k) - comb.C(n - i, k)) * covered[i];
        answer /= comb.C(n, k);
        cout << answer << '\n';
    }
    
    return 0;
}