Cの構築問題

解法

AとBの絶対差と最大値の和を取ることで、第三項を構築できます。

コード

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

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

    int a, b;
    cin >> a >> b;

    int d = abs(a - b);

    cout << max(a, b) + d << "\n";

    return 0;
}

入力形式処理問題

解法

C言語のscanfを使用して特定の形式で入力を読み取り、c-b-1を出力します。

コード

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

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

    i64 a, b, c;
    scanf("%lld,%lld,...,%lld", &a, &b, &c);
    printf("%lld\n", c - b - 1);

    return 0;
}

水面反射問題

解法

座標を水面に対称移動させた後、新しい点と原点とのベクトルを計算します。

コード

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

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

    int n, h;
    cin >> n >> h;

    while (n--) {
        i64 x, y, z;
        cin >> x >> y >> z;

        z = h + abs(h - z);
        i64 nx = x, ny = y, nz = z;
        i64 g = gcd(nx, gcd(ny, nz));
        nx /= g, ny /= g, nz /= g;

        cout << nx << " " << ny << " " << nz << "\n";
    }

    return 0;
}

計画選択問題

解法

p ≤ 7 であるため、ビット列挙で各計画を選択するかどうかを判定し、選択した計画の最終案が草地と補集合となるか確認します。

コード

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

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

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

    vector<string> cs(n);
    for (auto &i : cs) {
        cin >> i;
        for (auto &j : i) {
            j = ((j - '0') ^ 1) + '0';
        }
    }

    vector has(q, vector<string>(n));
    for (auto &i : has) {
        for (auto &j : i) {
            cin >> j;
        }
    }

    int ans = -1;
    vector<int> res;

    auto check = [&](int x)->void{
        vector<string> now(n, string(m, '0'));
        vector<int> ok;
        for (int i = 0; i < q; i++) {
            if (x >> i & 1) {
                ok.emplace_back(i + 1);
                for (int j = 0; j < n; j++) {
                    for (int k = 0; k < m; k++) {
                        if (has[i][j][k] == '1') {
                            now[j][k] = '1';
                        }
                    }
                }
            }
        }

        if (now == cs) {
            if (ans == -1 || ok.size() < ans) {
                ans = ok.size();
                swap(res, ok);
            }
        }
    };

    for (int i = 0; i < (1 << q); i++) {
        check(i);
    }

    cout << ans << "\n";
    for (auto i : res) {
        cout << i << " ";
    }

    return 0;
}

三分割問題

解法

三つの部分に等しく分割するためには、総和が3の倍数でなければなりません。

その後、累積和を計算し、sum/3に達する箇所を特定し、続いて条件を満たす分割が存在するかを確認します。

コード

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

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

    int n;
    cin >> n;

    vector<i64> pre(n + 1), has(n + 1);
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pre[i] += pre[i - 1] + a[i];
        has[i] += has[i - 1] + (a[i] > 0);
    }

    if (pre[n] % 3 != 0 || has[n] < 3) {
        cout << 0 << "\n";
        return 0;
    }

    i64 avg = pre[n] / 3, ans = 0;
    for (int i = 1; i <= n; i++) {
        if (!has[i] || pre[i] != avg) {
            continue;
        }
        for (int j = i + 1; j <= n; j++) {
            if (pre[j] - pre[i] != avg || has[j] - has[i] == 0) {
                continue;
            }
            if (pre[n] - pre[j] != avg || has[n] - has[j] == 0) {
                continue;
            }
            ans++;
        }
    }

    cout << ans << "\n";

    return 0;
}

部分列カウント問題

解法

区間（実際には[1,n]）の部分列"red"の数を求めます。交換操作は実質的に単点変更であるため、線分木を使用して"r"、"e"、"d"、"re"、"ed"、"red"の6つの部分文字列の数を管理します。

コード

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

template<class Node>
struct SegmentTree {
#define lc u<<1
#define rc u<<1|1
    const int n, N;
    vector<Node> tr;

    SegmentTree() : n(0) {}
    SegmentTree(int n_) : n(n_), N(n * 4 + 10) {
        tr.reserve(N);
        tr.resize(N);
    }
    SegmentTree(string &init) : SegmentTree(init.size() - 1) {
        function<void(int, int, int)> build = [&](int u, int l, int r) {
            tr[u].l = l, tr[u].r = r;
            if (l == r) {
                tr[u] = {l, r, {init[l] == 'r', init[l] == 'e', init[l] == 'd', 0, 0, 0}};
                return;
            }
            i64 mid = (l + r) >> 1;
            build(lc, l, mid);
            build(rc, mid + 1, r);
            pushup(tr[u], tr[lc], tr[rc]);
        };
        build(1, 1, n);
    }

    void pushup(Node& U, Node& L, Node& R) { // 上伝
        U.l = L.l, U.r = R.r;
        for (int i = 0; i < 6; i++) {
            U.res[i] = L.res[i] + R.res[i];
        }
        U.res[3] += L.res[0] * R.res[1];
        U.res[4] += L.res[1] * R.res[2];
        U.res[5] += L.res[0] * R.res[4] + L.res[3] * R.res[2];
    }

    void modify(int u, int x, char c, int k) {
        if (tr[u].l >= x && tr[u].r <= x) {
            if (c == 'r') tr[u].res[0] += k;
            else if (c == 'e') tr[u].res[1] += k;
            else if (c == 'd') tr[u].res[2] += k;
            return;
        }
        int mid = (tr[u].l + tr[u].r) >> 1;
        if (x <= mid)
            modify(lc, x, c, k);
        if (x > mid)
            modify(rc, x, c, k);
        pushup(tr[u], tr[lc], tr[rc]);
    }

    i64 get() {
        return tr[1].res[5];
    }
};

struct Node { // 線分木の定義
    int l, r;
    array<i64, 6> res;
};

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

    int n, q;
    cin >> n >> q;

    string s, t;
    cin >> s >> t;

    s = " " + s, t = " " + t;

    string pa = "red";
    SegmentTree<Node> st(s), tt(t);

    while (q--) {
        int x;
        cin >> x;

        if (pa.find(s[x]) != -1) {
            st.modify(1, x, s[x], -1);
        }
        if (pa.find(t[x]) != -1) {
            tt.modify(1, x, t[x], -1);
        }
        swap(s[x], t[x]);
        if (pa.find(s[x]) != -1) {
            st.modify(1, x, s[x], 1);
        }
        if (pa.find(t[x]) != -1) {
            tt.modify(1, x, t[x], 1);
        }

        cout << st.get() - tt.get() << "\n";
    }

    return 0;
}