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

# A - T or T

$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

2点間の距離の二乗 $d$ が整数 $x$ の二乗と等しくなるかチェックします．

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

$R - L \geq 2019$ のとき，$2019$ の倍数が必ず存在するため，最小値は $0$ になります．
$R - L < 2019$ のとき，$L \leq i < j \leq R$ にしたがって，$i, j$ を動かして最小値を求めます．

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

\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}


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

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

まずは2頂点間の距離を求めます．

$u, v$ の共通祖先のうち根から最も遠い頂点(lca)を $w$ とすると，
$u$ と $v$ の距離は $d_{u} + d_{v} - 2 d_{w}$ で計算できます．

$u, v$ の深さを揃えてから，親が一致しない境界まで上に辿るとlcaが求められます．

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;
}

Delight and Impact the World
https://dena.com/jp/
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