YSF Beginner Contestに参加しました

6/17 21:00〜22:30 に有志コンを開催します！https://t.co/NXLuvbyZyQ
writer: @null_0124
tester: @butsurizuki (Thanks!)
言語選択に関してはリンク先を読んでください。
配点: 100-200-300-350-400-600
— null🍆🌥️ (@null_0124) June 13, 2020

コンテストへのリンク

高校の偏差値が高すぎる。

1:13:16(コンテスト時間1:30:00)で7問全問正解。

A　やるだけ。
B　やるだけ。
C　やるだけ。
D　累積和。
E　mod p上で四則演算。
F　累積和。
G　最小共通祖先。

典型問題が多い。 AtCoderのABCであれば6完水パフォ、7完青バフォがでるはず。 Gは私の実力では解くことは難しいがライブラリを貼って解いた。

A - A+B Problem

問題へのリンク

やるだけ。

// https://www.hackerrank.com/ysf1
#include <algorithm>
#include <array>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
#define int long long

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    int n, m;
    cin >> n >> m;
    cout << n + m << endl;
}
}

B - 三変数方程式

問題へのリンク

N<3000なのでx, y, zすべてを全通り試すとTLEしそう。なのでx, yだけを全探索する。

n-x-y>=0ならばc=n-x-y。
n-x-y<0ならばcは存在しない。

#include <algorithm>
#include <array>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
#define int long long

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    int n;
    cin >> n;

    int ans = 0;

    for (int a = 0; a <= n; a++) {
        for (int b = 0; b <= n; b++) {
            const int c = n - a - b;
            if (c >= 0) ans++;
        }
    }

    cout << ans << endl;
}

C - ソーシャルディスタンス / Social Distance

問題へのリンク

やるだけ。読解ミスして1WAした。

#include <algorithm>
#include <array>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
#define int long long

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

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

    for (int i = 1; i < n; i++) {
        if (a[i] - a[i - 1] < d) a[i] = a[i - 1] + d;
    }

    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    cout << endl;
}

D - Range Xor Query

問題へのリンク

XOR演算子は交換可能で逆元が存在する。そのため累積XORを事前に計算しておけば、配列の区間の総XORはO(1)で求められる。

#include <iostream>
#include <vector>
using namespace std;

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    // cumulative XOR
    vector<int> csa(n + 1);
    csa[0] = 0;
    for (int i = 0; i < n; i++) csa[i + 1] = csa[i] ^ a[i];

    for (int qi = 0; qi < q; qi++) {
        int l, r;
        cin >> l >> r;

        const int ans = csa[r] ^ csa[l - 1];
        cout << ans << endl;
    }
}

E - modular arithmetic

問題へのリンク

mod p上で四則演算ができますか？　私はできます。答えは0以上p未満なので、引き算するときはpを足してpの余剰を取ってそうします。割り算するときは逆元を掛けます。

「1000000007 で割ったあまり」の求め方を総特集！〜逆元から離散対数まで〜

#include <algorithm>
#include <array>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
#define int long long

// this code is copied from drken's blog.
// https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a

long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b;
        swap(a, b);
        u -= t * v;
        swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
// end of copied code

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    int p, n;
    cin >> p >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    string s;
    cin >> s;

    int x = a[0];
    for (int i = 0; i < (int)s.size(); i++) {
        switch (s[i]) {
            case '+':
                x = (x + a[i + 1]) % p;
                break;

            case '-':
                x = (x - a[i + 1] + p) % p;
                break;

            case '*':
                x = (x * a[i + 1]) % p;
                break;

            case '/':
                x = (x * modinv(a[i + 1], p)) % p;
                break;
        }
    }

    cout << x % p << endl;
}

F - 区間の和 / Sum of Range

問題へのリンク

Sを計算します。 Sは愚直に計算すればO(NK-KK)で求められますが、累積和を用いる方法ではO(N+N-K)で求められます。 Sをソートしておけば、クエリは二分探索でO(log(N-K))で求められます。ソートがボトルネックとなります。

#include <algorithm>
#include <array>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
#define int long long

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    vector<int> csa(n + 1);
    csa[0] = 0;
    for (int i = 0; i < n; i++) csa[i + 1] = csa[i] + a[i];

    vector<int> s(n - k + 1);
    for (int i = 0; i <= n - k; i++) {
        s[i] = csa[i + k] - csa[i];
    }
    sort(s.begin(), s.end());

    int q;
    cin >> q;
    for (int qi = 0; qi < q; qi++) {
        int x;
        cin >> x;

        auto itr = upper_bound(s.begin(), s.end(), x);
        int count = distance(s.begin(), itr);
        cout << count << endl;
    }
}

G - 木登り / Climbing Tree

問題へのリンク

2つの頂点s,t間の距離を高速で求めたいです。クエリに答える前にすべての頂点の根からの距離と、最小共通祖先uを計算しておきます。 (根からsへの距離) + (根からtへの距離) - 2*(根からuへの距離)と答えることで、高速に答えられます。

うしライブラリ🐮を貼ります。

#include <algorithm>
#include <array>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
constexpr int INF = 1000000000 + 8;

// https://ei1333.github.io/luzhiled/snippets/graph/template.html
template <typename T>
struct edge {
    int src, to;
    T cost;

    edge(int to, T cost) : src(-1), to(to), cost(cost) {}

    edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}

    edge &operator=(const int &x) {
        to = x;
        return *this;
    }

    operator int() const { return to; }
};

template <typename T>
using Edges = vector<edge<T>>;
template <typename T>
using WeightedGraph = vector<Edges<T>>;
using UnWeightedGraph = vector<vector<int>>;
template <typename T>
using Matrix = vector<vector<T>>;

// https://ei1333.github.io/luzhiled/snippets/tree/doubling-lowest-common-ancestor.html
template <typename G>
struct DoublingLowestCommonAncestor {
    const int LOG;
    vector<int> dep;
    const G &g;
    vector<vector<int>> table;

    DoublingLowestCommonAncestor(const G &g)
        : g(g), dep(g.size()), LOG(32 - __builtin_clz(g.size())) {
        table.assign(LOG, vector<int>(g.size(), -1));
    }

    void dfs(int idx, int par, int d) {
        table[0][idx] = par;
        dep[idx] = d;
        for (auto &to : g[idx]) {
            if (to != par) dfs(to, idx, d + 1);
        }
    }

    void build() {
        dfs(0, -1, 0);
        for (int k = 0; k + 1 < LOG; k++) {
            for (int i = 0; i < table[k].size(); i++) {
                if (table[k][i] == -1)
                    table[k + 1][i] = -1;
                else
                    table[k + 1][i] = table[k][table[k][i]];
            }
        }
    }

    int query(int u, int v) {
        if (dep[u] > dep[v]) swap(u, v);
        for (int i = LOG - 1; i >= 0; i--) {
            if (((dep[v] - dep[u]) >> i) & 1) v = table[i][v];
        }
        if (u == v) return u;
        for (int i = LOG - 1; i >= 0; i--) {
            if (table[i][u] != table[i][v]) {
                u = table[i][u];
                v = table[i][v];
            }
        }
        return table[0][u];
    }
};

void search(WeightedGraph<int> &g, vector<int> &dists, int p = 0) {
    for (auto &&edge : g[p]) {
        int np = edge.to;
        if (dists[np] != INF) continue;

        int ndist = dists[p] + edge.cost;

        dists[np] = ndist;
        search(g, dists, np);
    }
}

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    int n;
    cin >> n;
    WeightedGraph<int> g(n);
    vector<int> dists(n, INF);
    dists[0] = 0;

    for (int i = 0; i < n - 1; i++) {
        int a, b, c;
        cin >> a >> b >> c;

        a--;
        b--;
        g[a].emplace_back(b, c);
        g[b].emplace_back(a, c);
    }

    search(g, dists, 0);
    DoublingLowestCommonAncestor<WeightedGraph<int>> lca(g);
    lca.build();

    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int s, t;
        cin >> s >> t;
        s--, t--;

        const int ca = lca.query(s, t);
        const int ans = dists[s] + dists[t] - 2 * dists[ca];

        cout << ans << endl;
    }
}