Help us understand the problem. What is going on with this article?

AtCoder Beginner Contest 133 振り返り

はじめに

AtCoder Beginner Contest 133 の解法です.

A - T or T

https://atcoder.jp/contests/abc133/tasks/abc133_a

$N \times A$ と $B$ の小さい方が答えになります.

int main() {
    int N, A, B;
    cin >> N >> A >> B;
    cout << min(N * A, B) << endl;
    return 0;
}

B - Good Distance

https://atcoder.jp/contests/abc133/tasks/abc133_b

2点間の距離の二乗 $d$ が整数 $x$ の二乗と等しくなるかチェックします.
整数 $x$ は $0$ から $\sqrt{d}$ まで試します.

int main() {
    int N, D, X[10][10];
    cin >> N >> D;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < D; j++) {
            cin >> X[i][j];
        }
    }
    int res = 0;
    for (int i = 0; i < N - 1; i++) {
        for (int j = i + 1; j < N; j++) {
            int d = 0;
            for (int k = 0; k < D; k++) {
                d += (X[i][k] - X[j][k]) * (X[i][k] - X[j][k]);
            }
            int sq = sqrt(d);
            for (int x = 0; x < sq + 1; x++) {
                if (x * x == d) {
                    res++;
                    break;
                }
            }
        }
    }
    cout << res << endl;
    return 0;
}

C - Remainder Minimization

https://atcoder.jp/contests/abc133/tasks/abc133_c

$R - L \geq 2019$ のとき,$2019$ の倍数が必ず存在するため,最小値は $0$ になります.
$R - L < 2019$ のとき,$L \leq i < j \leq R$ にしたがって,$i, j$ を動かして最小値を求めます.
計算量は高々 $2019^{2}$ になります.

int main() {
    long long L, R;
    cin >> L >> R;
    if (L % 2019 == 0 || R % 2019 == 0) {
        cout << 0 << endl;
        return 0;
    } else if (R - L >= 2019) {
        cout << 0 << endl;
        return 0;
    }
    int res = 2018;
    for (long long i = L; i < R; i++) {
        for (long long j = i + 1; j <= R; j++) {
            int r = i * j % 2019;
            res = min(res, r);
        }
    }
    cout << res << endl;
    return 0;
}

D - Rain Flows into Dams

https://atcoder.jp/contests/abc133/tasks/abc133_d

各山に降った雨を $X_{i} (i = 1, \cdots, N)$ とすると,以下が成り立ちます.

\cfrac{X_{i}}{2} + \cfrac{X_{i + 1}}{2} = A_{i} \tag{1}

$i = 1$ から $i = N$ まで並べます.$X_{N + 1} = X_{1}$ としています.

X_{1} + X_{2} = 2 A_{1} \\
X_{2} + X_{3} = 2 A_{2} \\
X_{3} + X_{4} = 2 A_{3} \\
\cdots \\
X_{N} + X_{1} = 2 A_{N}

奇数行を足し,偶数行を引くと,以下を導くことができます.

X_{1} = A_{1} - A_{2} + A_{3} - \cdots + A_{N}

式(1)にしたがって $X_{i} (i = 2, \cdots, N)$ を順次求めます.

int main() {
    int N;
    cin >> N;
    vector<long long> A(N), res(N, 0);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        if (i % 2 == 0) {
            res[0] += A[i];
        } else {
            res[0] -= A[i];
        }
    }
    for (int i = 1; i < N; i++) {
        res[i] += A[i - 1] * 2 - res[i - 1];
    }
    for (int i = 0; i < N; i++) {
        cout << res[i] << " ";
    }
    cout << endl;
    return 0;
}

E - Virus Tree 2

https://atcoder.jp/contests/abc133/tasks/abc133_e

頂点 $0$ を根として考えます.
頂点 $i$ の子の数を $c_{i}$ とすると,$i \neq 0$ なる頂点 $i$ の子を塗るとき $K - 2$ 色から $c_{i}$ 色選ぶことになります.
頂点 $0$ の子は $K - 1$ 色から選びます.

const int MOD = 1000000007;
int N, K;
vector<vector<int>> G;

long long dfs(int curr, int prev) {
    if (G[curr].size() > K) {
        return 0;
    }
    int k = prev == -1 ? K - 1 : K - 2;
    long long res = 1;
    for (auto x : G[curr]) {
        if (x == prev) {
            continue;
        }
        res *= k;
        res %= MOD;
        k--;
    }
    for (auto x : G[curr]) {
        if (x == prev) {
            continue;
        }
        res *= dfs(x, curr);
        res %= MOD;
    }
    return res;
}

int main() {
    cin >> N >> K;
    G = vector<vector<int>>(N);
    for (int i = 0; i < N - 1; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    cout << dfs(0, -1) * K % MOD << endl;
    return 0;
}

F - Colorful Tree

https://atcoder.jp/contests/abc133/tasks/abc133_f

まずは2頂点間の距離を求めます.
根から頂点 $u$ までの距離を $d_{u}$ で表し,
$u, v$ の共通祖先のうち根から最も遠い頂点(lca)を $w$ とすると,
$u$ と $v$ の距離は $d_{u} + d_{v} - 2 d_{w}$ で計算できます.
頂点 $u$ の $2^{i}$ 個上の親を $p_{u, i}$ とすると $p_{u, i + 1} = p_{p_{u, i}, i}$ が成り立ちます.
$u, v$ の深さを揃えてから,親が一致しない境界まで上に辿るとlcaが求められます.
頂点ごとにクエリを登録しておき,dfsで探索するときに色の書き換えによる距離の変化量を計算します.

struct node {
    int to;
    int col;
    int dis;
};

struct query {
    int id;
    int col;
    int dis;
    int coef;
};

const int MAX_N = 100000;
const int MAX_LOGN = 20;
const int MAX_Q = 100000;
const int MAX_C = 100000 - 1;

vector<vector<node>> G(MAX_N);
vector<vector<query>> qs(MAX_N);

vector<vector<int>> par(MAX_N, vector<int>(MAX_LOGN, -1));
vector<int> dep(MAX_N, 0);
vector<int> dis(MAX_N, 0);
vector<int> cnt(MAX_C, 0);
vector<int> sum(MAX_C, 0);

vector<int> res(MAX_Q, 0);

void init(int u, int p = -1, int d = 0) {
    if (p >= 0) {
        par[u][0] = p;
        dep[u] = dep[p] + 1;
        dis[u] = dis[p] + d;
    }
    for (auto g : G[u]) {
        int v = g.to;
        if (v != p) {
            init(v, u, g.dis);
        }
    }
}
void parent(int n) {
    for (int i = 0; i < MAX_LOGN; i++) {
        for (int j = 0; i < n; i++) {
            if (par[j][i] != -1) {
                par[j][i + 1] = par[par[j][i]][i];
            }
        }
    }
}
int lca(int u, int v) {
    if (dep[u] > dep[v]) {
        swap(u, v);
    }
    for (int i = MAX_LOGN - 1; i >= 0; i--) {
        if (((dep[v] - dep[u]) >> i) & 1) {
            v = par[v][i];
        }
    }
    if (u == v) {
        return u;
    }
    for (int i = MAX_LOGN - 1; i >= 0; i--) {
        if (par[u][i] != par[v][i]) {
            u = par[u][i];
            v = par[v][i];
        }
    }
    return par[u][0];
}
void dfs(int u, int p = -1) {
    for (auto q : qs[u]) {
        int diff = q.dis * cnt[q.col] - sum[q.col];
        res[q.id] += diff * q.coef;
    }
    for (auto g : G[u]) {
        int v = g.to;
        if (v == p) {
            continue;
        }
        cnt[g.col]++;
        sum[g.col] += g.dis;
        dfs(v, u);
        cnt[g.col]--;
        sum[g.col] -= g.dis;
    }
}

int main() {
    int N, Q;
    cin >> N >> Q;
    for (int i = 0; i < N - 1; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        a--, b--;
        G[a].push_back({b, c, d});
        G[b].push_back({a, c, d});
    }
    init(0);
    parent(N);
    for (int i = 0; i < Q; i++) {
        int x, y, u, v;
        cin >> x >> y >> u >> v;
        u--, v--;
        int w = lca(u, v);
        qs[u].push_back({i, x, y, 1});
        qs[v].push_back({i, x, y, 1});
        qs[w].push_back({i, x, y, -2});
        res[i] = dis[u] + dis[v] - 2 * dis[w];
    }
    dfs(0);
    for (int i = 0; i < Q; i++) {
        cout << res[i] << endl;
    }
    return 0;
}
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした