AtCoder Beginner Contest 133

更新日時:

AtCoder Beginner Contest 133

解説放送

ソースコード

解法のメモ

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

\[ 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;

は間違い。リテラル 0int 型になる。正しくは

  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$ とすれば答えは正しい。これらの積が答え。

F - Colorful Tree

解答

色もクエリも頂点も $0$-indexed とする。

$ans[i] = i$ 番目のクエリの解答

と定める。まずクエリによる変更を無視した答えを $ans[i]$ の中に突っ込む。これは LCA を求めることにより高速に可能である。この値を頂点 $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 からの 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 col, qid, coeff, y;
};

coeff は (F.1) 式における係数である。つまり $1$ または $-2$ である。

dfs は以下のようになる。

void dfs(int v, int p = -1)
{
  for (auto q : qs[v])
  {
    ll f = -sum[q.col] + (ll)cnt[q.col] * q.y;
    ans[q.qid] += x * q.coeff;
  }
  for (auto e : es[v])
  {
    if (e.to == p)
    {
      continue;
    }
    cnt[e.col]++;
    sum[e.col] += e.co;
    dfs(e.to, v);
    cnt[e.col]--;
    sum[e.col] -= e.co;
  }
}

parent を引数に持つのがポイントで、戻ってきてから cntsum をいじることで、正しいタイミングで正しく計算される。

ポイント

これは LCA を計算するのがそもそも面倒である。そしてそのあとのクエリの処理も思い付きづらい。ライブラリコピペするゲームになっているから面倒である。

その他