AtCoder Beginner Contest 133
Updated:
- Review: 2020-05-19
Source codes
Solutions
A - T or T
$\min(AN, B)$ を出力する。
B - Good Distance
全探索をする。
ポイント
$K$ が平方数であるかどうかを判定するには ll t = sqrt(K) + 0.5;
として t * t == K
かどうかを判定する。 double -> int への縮小変換は切り捨てらしい。
C - Remainder Minimization 2019
解答
$L \leq i < j \leq \min(R, L + 2100)$ を探索すれば $R - L$ の大きさにかかわらず、間に合う。
解説放送の解答
\[ up(x) = \min \{ n \geq x \mid n \% 2019 = 0 \}. \] とする。すると $up(L) \leq R$ の場合は答えは $0$ である。そうでない場合は、 $L \leq i < j \leq R$ をみたす $(i, j)$ を全て探索しても間に合う。これで答えが出る。
D - Rain Flows into Dams
解答
$0$ - indexed とする。連立 $1$ 次方程式 \[ x _ i + x _ {i + 1} = A _ i \ \ \ \ \ (i \in N) \tag{D.1} \] を解けということである。ここで index は $\mathbb{Z}/N\mathbb{N}$ である。まず \[ \sum _ {i \in N} x _ i = \frac{1}{2} \sum _ {i \in N} A _ i \] である。これを $sum$ とおく。さらに (D.1) 式を $1$ つ飛ばしに足して、 \[ 2 x _ 0 + x _ 1 + \dots + x _ {N - 1} = A _ 0 + A _ 2 + \dots + A _ {N - 1} \] を求め $tmp$ とおく。すると $x _ 0 = tmp - sum$ と求まる。あとは \[ x _ i = A _ {i - 1} - x _ {i - 1} \ \ \ \ \ (i = 1, \dots, N - 1) \] と求めればよろしい。
ポイント
解説放送では、すぬけさんは最初を $x$ と置いて \[ x = \frac{1}{2}\sum _ {i \in N} (-1) ^ i A _ i \] を実験的に導出していた。
私は間違えてしまった。
sum = accumulate(A, A + N, 0) / 2;
は間違い。リテラル 0
は int
型になる。正しくは
sum = accumulate(A, A + N, 0LL) / 2;
である。
E - Virus Tree 2
解答
$0$ を根とする。根から順番に dfs で色を塗っていくことにする。問題文の制約は以下の通りになる。
ある頂点の子を塗る際は、子を全て別の色で塗る必要がある。さらにその頂点の色でも塗ることはできないし、その頂点の親の色でも塗ることはできない。
そこで頂点に対し、その子を塗ることにする。最初の根を塗る際の色は $K$ 通り。次に根の子を塗る方法は順列でいいので \[ \begin{pmatrix} K - 1 \\\ c \end{pmatrix} c! \] 通り。さらにそれ以降は \[ \begin{pmatrix} K - 2 \\\ c \end{pmatrix} c! \] 通りとなる。最後の根も $c = 0$ とすれば答えは正しい。これらの積が答え。
実装
どのような方法でも良いが、子の部分木が部分問題になっているので、 DFS をしながら答えを返す方法が一例である。
mint dfs(int v = 0, ll depth = 0)
{
visited[v] = true;
ll child{0};
mint ans{1};
for (auto w : V[v])
{
if (!visited[w])
{
++child;
ans *= dfs(w, depth + 1);
}
}
if (depth == 0)
{
return K * C(K - 1, child) * C.fact[child] * ans;
}
return C(K - 2, child) * C.fact[child] * ans;
}
これだと dfs()
を呼び出せば終わる。
F - Colorful Tree
色もクエリも頂点も $0$-indexed とする。
考察
まずクエリによるコストの変更を考慮しない場合は、 LCA で高速に解答が求まる。そこでまず、
$ans[i] = i$ 番目のクエリの解答
と定め、クエリによる変更を無視した答えを $ans[i]$ の中に突っ込む。この値を頂点 $u, v$ に対し $dist(u, v)$ と書くことにする。 $0$ を root と定める。
続けてクエリによる変更の影響を調査することにする。 $(x _ q, y _ q, u _ q, v _ q)$ を投げられたとする。すると本当の $ans[q]$ と $dist(u _ q, v _ q)$ の差異は以下の通りにまとめられる。 \[ ans[q] - dist(u _ q, v _ q) = f(u _ q, x _ q, y _ q) + f(v _ q, x _ q, y _ q) - 2 f(lca(u _ q, v _ q), x _ q, y _ q). \tag{F.1} \] ここで、
$f(u, x, y) = 0$ と $u$ の間の経路における、色 $x$ の辺の長さを全て $y$ に変更した時の変更の影響
である。そこでこれを 頂点 $u$ ごとに計算する ことを考える。ただし、その計算のタイミングは、 root $= 0$ から DFS で頂点を訪れる順番(オイラーツアー)で管理するものとする。つまり、 DFS で辺を下に辿る際に辺の影響を足し、辺を上に辿る際に辺の影響を打ち消す。こうすることで、帳尻を合わせる。そこで以下の一時変数を変更しながら DFS を行う。
$sum[c] =$ 色 $c$ に対する今までの経路で辿ってきた辺の長さの総和、
$cnt[c] =$ 色 $c$ に対する今までの経路で辿ってきた辺の個数、
大雑把に言えば以下の通りになる。 \[ f(u, x, y) = - sum[x] + cnt[x] y. \]
これを、 $0$ から DFS して $u$ に到達した時に計算すればよろしい。ただし、頂点ごとに処理するので、 (F.1) 式における係数である $1$ or $-2$ は織り込んだ上で $ans[q]$ に計算結果を格納する必要がある。
実装
そこで query として、以下の struct を用意し、これを辺ごとに vector<Query>
を持っておく。
struct Query
{
int id, color, y, coefficient;
};
coefficient
は (F.1) 式における係数である。つまり $1$ または $-2$ である。具体的にいうと、クエリ $(x _ q, y _ q, u _ q, v _ q)$ を、以下の $3$ つに分解する。
W[u].push_back({i, x, y, 1});
W[v].push_back({i, x, y, 1});
W[lca(u, v)].push_back({i, x, y, -2});
DFS は以下の通り。
void dfs(int u = 0, int p = -1)
{
for (auto const &q : W[u])
{
ans[q.id] += q.coefficient * (-sum[q.color] + cnt[q.color] * q.y);
}
for (auto const &e : V[u])
{
if (e.dst == p)
{
continue;
}
sum[e.color] += e.cost;
cnt[e.color]++;
dfs(e.dst, u);
sum[e.color] -= e.cost;
cnt[e.color]--;
}
}
parent を引数に持つのがポイントで、再帰で行くとき、戻るときに cnt
と sum
をいじることで、 $0$ から $u$ の path の寄与が、正しいタイミングで正しく計算される。
ポイント
(当時の感想) これは LCA を計算するのがそもそも面倒である。そしてそのあとのクエリの処理も思い付きづらい。ライブラリコピペするゲームになっているから面倒である。
(2020-05-19) snuke さんが解説放送で披露してくださった LCA ライブラリを消化したので、よくわかるようになった。難しくはない。