Many Formulas

問題概要 ある整数が与えられます。この整数の任意の桁と桁の間に + 記号を0個以上挿入することで式を形成し、形成可能なすべての式の合計値を計算します。

解法 1 ≤ |S| ≤ 10 であるため、全探索が現実的です。n桁の整数では、n-1箇所の隙間に加号を挿入するかどうかを決定できます。バイナリビットマスク用于枚举所有可能的加号插入位置。

実装

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

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

    i64 val;
    cin >> val;

    string str = to_string(val);
    const int digits = str.size();

    i64 total = 0;
    for (int mask = 0; mask < (1 << (digits - 1)); mask++) {
        i64 start = 0;
        for (int idx = 0; idx < str.size(); idx++) {
            if (((mask >> idx) & 1) || idx + 1 == str.size()) {
                i64 part = stoll(str.substr(start, idx - start + 1));
                total += part;
                start = idx + 1;
            }
        }
    }

    cout << total << '\n';
    return 0;
}

Tak and Cards

問題概要 n個の整数と目標平均値Aが与えられます。数を選択して、その平均値をAにする組み合わせの数を求めてください。

解法 n個から数を選択して平均値を求めるため、動的計画法（DP）を利用します。平均値の性質上、i個の数の合計が j となる組み合わせ数を保持する必要があります。

dp[i][j] を、i個の数を合計jにした場合の組み合わせ数と定義します。状態遷移では過去の選択の影響を避けるため、要素数を減らす方向（逆順）にDPを更新します。最終答えは Σ dp[i][i×A] となります。

実装

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

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

    int n, A;
    cin >> n >> A;

    vector<int> arr(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> arr[i];

    const int MAX_SUM = 2500;
    vector dp(n + 1, vector<i64>(MAX_SUM + 1, 0));

    sort(arr.begin() + 1, arr.end());
    dp[0][0] = 1;

    for (int k = 1; k <= n; k++) {
        for (int i = k; i >= 1; i--) {
            for (int j = MAX_SUM; j >= arr[k]; j--) {
                dp[i][j] += dp[i - 1][j - arr[k]];
            }
        }
    }

    i64 result = 0;
    for (int i = 1; i <= n; i++)
        result += dp[i][i * A];

    cout << result << '\n';
    return 0;
}

Wall

問題概要 10×10 の行列が与えられ、0〜9 の数字間の変換コストを表しています。n×m の行列について、-1 でない値をすべて 1 に変換する最小コストを求めてください。

解法 まず、0〜9 の各数字から 1 への最短変換コストを求めます。全点対最短経路問題なので、Floyd-Warshall アルゴリズムを使用します。準備完了後、入力行列の各要素について変換コストを加算するだけです。

実装

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

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

    int n, m;
    cin >> n >> m;

    const int NUM = 10;
    int cost[NUM][NUM];
    for (int i = 0; i < 10; i++)
        for (int j = 0; j < 10; j++)
            cin >> cost[i][j];

    for (int k = 0; k < 10; k++)
        for (int i = 0; i < 10; i++)
            for (int j = 0; j < 10; j++)
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);

    vector grid(n, vector<int>(m));
    i64 total = 0;

    for (auto& row : grid)
        for (auto& cell : row) {
            cin >> cell;
            if (cell != -1) total += cost[cell][1];
        }

    cout << total << '\n';
    return 0;
}

Coloring Edges on Tree

問題概要 木構造が与えられます。各辺に色を塗るのですが、1つの頂点に接続するすべての辺が互いに異なる色を持つようにする必要があります。最小の色数で塗り分ける方法を求めてください。

解法 木をDFSで巡回しながら辺に色を付けていきます。各頂点において、親頂点との接続辺の色を記録しながら、その頂点に 연결된他のすべての辺に色を塗ります。現在の色が親の色と同じ場合は色を1つ進めます。これにより、使用する色の総数が最小になります。

実装

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

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

    int n;
    cin >> n;

    vector<array<int, 2>> edges(n);
    map<pair<int, int>, int> colorMap;
    vector<vector<int>> adj(n + 1);

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        edges[i] = {u, v};
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    set<int> usedColors;

    function<void(int, int, int)> dfs = [&](int node, int parent, int parentColor) {
        int currentColor = 1;
        for (int child : adj[node]) {
            if (child == parent) continue;
            if (currentColor == parentColor) currentColor++;
            colorMap[{node, child}] = colorMap[{child, node}] = currentColor;
            usedColors.insert(currentColor);
            dfs(child, node, currentColor);
            currentColor++;
        }
    };

    dfs(1, 0, 0);

    cout << usedColors.size() << '\n';
    for (int i = 1; i < n; i++) {
        auto [u, v] = edges[i];
        cout << colorMap[{u, v}] << '\n';
    }

    return 0;
}

Fault-tolerant Network

問題概要 2×n 台のコンピュータが2列に配置されています。各コンピュータには価値があり、隣接コンピュータ間はLANケーブルで接続されています。これらの列の間にケーブルを接続して、任意の一台が故障しても全体が接続を維持できるようにします。接続コストは |a-b|（価値の差）です。

解法 4つの角のコンピュータ（a1, an, b1, bn）は必ず对面と接続する必要があります。いずれかの角が接続されていない場合、隣接する计算机が故障すると孤立します。

以下の3ケースに分類して最少コストを求めます：

2辺の場合：aとbの端点同士を交叉接続 3辺の場合：1組は直接接続、残りの2点は各自的列内で最小コストの辺を接続 4辺の場合：各端点到对面で最も安価な接続

実装

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

void solve() {
    int n;
    cin >> n;

    vector<i64> left(n + 1), right(n + 1);
    for (int i = 1; i <= n; i++) cin >> left[i];
    for (int i = 1; i <= n; i++) cin >> right[i];

    i64 answer = min(abs(left[1] - right[1]) + abs(left[n] - right[n]),
                     abs(left[1] - right[n]) + abs(left[n] - right[1]));
    
    i64 minA1 = INT_MAX, minAn = INT_MAX, minB1 = INT_MAX, minBn = INT_MAX;

    for (int i = 1; i <= n; i++) {
        minA1 = min(minA1, abs(left[1] - right[i]));
        minAn = min(minAn, abs(left[n] - right[i]));
        minB1 = min(minB1, abs(right[1] - left[i]));
        minBn = min(minBn, abs(right[n] - left[i]));
    }

    answer = min({answer,
        abs(left[1] - right[1]) + minAn + minBn,
        abs(left[1] - right[n]) + minAn + minB1,
        abs(left[n] - right[1]) + minA1 + minBn,
        abs(left[n] - right[n]) + minA1 + minB1});

    answer = min(answer, minA1 + minAn + minB1 + minBn);

    cout << answer << '\n';
}

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

    int t;
    cin >> t;
    while (t--) solve();

    return 0;
}

Nearest Excluded Points

問題概要 複数のマークされた座標が与えられます。マークされていない座標の中で、これらの点からマンハッタン距離が最小のものを各マーク点に対して求めてください。

解法 1つの点到するマンハッタン距離で最も近い点は必ず上下左右の4方向的近傍に存在します。マークされた点を一块として考えると、その块に最も近い点は必ずその块を囲む境界上のマークされていない点になります。

BFSを用いて、未マークの各点をキューに入れ、境界から顺次に块内部の点に波及させていきます。各点の答案是最初に到達した未マーク点です。

実装

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

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

    int n;
    cin >> n;

    vector<pair<int, int>> marked(n);
    const int dirX[] = {1, -1, 0, 0};
    const int dirY[] = {0, 0, 1, -1};
    
    map<pair<int, int>, pair<int, int>> result;
    set<pair<int, int>> blocked;
    queue<pair<int, int>> q;

    for (auto& p : marked) {
        cin >> p.first >> p.second;
        blocked.insert(p);
    }

    for (auto [x, y] : marked) {
        for (int d = 0; d < 4; d++) {
            int nx = x + dirX[d], ny = y + dirY[d];
            if (blocked.count({nx, ny})) continue;
            q.push({nx, ny});
            result[{nx, ny}] = {nx, ny};
        }
    }

    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();

        for (int d = 0; d < 4; d++) {
            int nx = x + dirX[d], ny = y + dirY[d];
            if (blocked.count({nx, ny})) {
                result[{nx, ny}] = result[{x, y}];
                q.push({nx, ny});
                blocked.erase({nx, ny});
            }
        }
    }

    for (auto node : marked) {
        auto [x, y] = result[node];
        cout << x << ' ' << y << '\n';
    }

    return 0;
}

Vacation Query

問題概要 長さNの01配列Sに対して、Q回の操作を行います：

タイプ1 L R：S_L から S_R までの各ビットを反転 タイプ2 L R：S_L から S_R までの最長連続1の長さ答える

解法 セグメントツリーを使用して、最大部分和問題テンプレートを実装します。遅延伝播により範囲反転操作をサポートします。各ノードには、1と0 각각について、合計値、最大接頭辞、最大接尾辞、最大区間の情報を保存します。反転操作ではこれらの値を交换します。

実装

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

#define LEFT u << 1
#define RIGHT u << 1 | 1
const int MAXN = 100005;

int arr[MAXN];
int n, q;

struct Node {
    int l, r;
    int sum1, prefix1, suffix1, best1;
    int sum0, prefix0, suffix0, best0;
    int assign, flip;
} seg[MAXN << 2];

void applyAssign(int u, int value) {
    int len = seg[u].r - seg[u].l + 1;
    if (value == 0) {
        seg[u].assign = 0; seg[u].flip = 0;
        seg[u].sum0 = seg[u].prefix0 = seg[u].suffix0 = seg[u].best0 = len;
        seg[u].sum1 = seg[u].prefix1 = seg[u].suffix1 = seg[u].best1 = 0;
    } else {
        seg[u].assign = 1; seg[u].flip = 0;
        seg[u].sum0 = seg[u].prefix0 = seg[u].suffix0 = seg[u].best0 = 0;
        seg[u].sum1 = seg[u].prefix1 = seg[u].suffix1 = seg[u].best1 = len;
    }
}

void applyFlip(int u) {
    seg[u].flip ^= 1;
    swap(seg[u].sum1, seg[u].sum0);
    swap(seg[u].prefix1, seg[u].prefix0);
    swap(seg[u].suffix1, seg[u].suffix0);
    swap(seg[u].best1, seg[u].best0);
}

void propagate(int u) {
    if (seg[u].assign != -1) {
        applyAssign(LEFT, seg[u].assign);
        applyAssign(RIGHT, seg[u].assign);
        seg[u].assign = -1;
    }
    if (seg[u].flip) {
        applyFlip(LEFT);
        applyFlip(RIGHT);
        seg[u].flip = 0;
    }
}

void merge(int u) {
    seg[u].sum1 = seg[LEFT].sum1 + seg[RIGHT].sum1;
    seg[u].sum0 = seg[LEFT].sum0 + seg[RIGHT].sum0;
    
    seg[u].prefix1 = seg[LEFT].prefix1 + (seg[LEFT].sum0 ? 0 : seg[RIGHT].prefix1);
    seg[u].suffix1 = seg[RIGHT].suffix1 + (seg[RIGHT].sum0 ? 0 : seg[LEFT].suffix1);
    seg[u].prefix0 = seg[LEFT].prefix0 + (seg[LEFT].sum1 ? 0 : seg[RIGHT].prefix0);
    seg[u].suffix0 = seg[RIGHT].suffix0 + (seg[RIGHT].sum1 ? 0 : seg[LEFT].suffix0);
    
    seg[u].best1 = max({seg[LEFT].best1, seg[RIGHT].best1, seg[LEFT].suffix1 + seg[RIGHT].prefix1});
    seg[u].best0 = max({seg[LEFT].best0, seg[RIGHT].best0, seg[LEFT].suffix0 + seg[RIGHT].prefix0});
}

void build(int u, int l, int r) {
    seg[u].l = l; seg[u].r = r;
    seg[u].assign = -1; seg[u].flip = 0;
    
    if (l == r) {
        int v = arr[l];
        seg[u] = {l, r, v, v, v, v, v ^ 1, v ^ 1, v ^ 1, v ^ 1, -1, 0};
        return;
    }
    
    int mid = (l + r) >> 1;
    build(LEFT, l, mid);
    build(RIGHT, mid + 1, r);
    merge(u);
}

void rangeFlip(int u, int l, int r) {
    if (seg[u].l >= l && seg[u].r <= r) {
        applyFlip(u);
        return;
    }
    propagate(u);
    int mid = (seg[u].l + seg[u].r) >> 1;
    if (l <= mid) rangeFlip(LEFT, l, r);
    if (r > mid) rangeFlip(RIGHT, l, r);
    merge(u);
}

Node rangeQuery(int u, int l, int r) {
    if (seg[u].l >= l && seg[u].r <= r) return seg[u];
    propagate(u);
    int mid = (seg[u].l + seg[u].r) >> 1;
    
    if (r <= mid) return rangeQuery(LEFT, l, r);
    if (l > mid) return rangeQuery(RIGHT, l, r);
    
    Node left = rangeQuery(LEFT, l, mid);
    Node right = rangeQuery(RIGHT, mid + 1, r);
    Node res;
    
    res.sum1 = left.sum1 + right.sum1;
    res.sum0 = left.sum0 + right.sum0;
    res.prefix1 = left.prefix1 + (left.sum0 ? 0 : right.prefix1);
    res.suffix1 = right.suffix1 + (right.sum0 ? 0 : left.suffix1);
    res.prefix0 = left.prefix0 + (left.sum1 ? 0 : right.prefix0);
    res.suffix0 = right.suffix0 + (right.sum1 ? 0 : left.suffix0);
    res.best1 = max({left.best1, right.best1, left.suffix1 + right.prefix1});
    res.best0 = max({left.best0, right.best0, left.suffix0 + right.prefix0});
    
    return res;
}

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

    cin >> n >> q;
    string s;
    cin >> s;
    for (int i = 1; i <= n; i++) arr[i] = s[i - 1] - '0';

    build(1, 1, n);

    while (q--) {
        int type, l, r;
        cin >> type >> l >> r;
        if (type == 1) {
            rangeFlip(1, l, r);
        } else {
            Node ans = rangeQuery(1, l, r);
            cout << ans.best1 << '\n';
        }
    }

    return 0;
}