AtCoder Beginner Contest 133

Updated:

AtCoder Beginner Contest 133

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

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

実装

どのような方法でも良いが、子の部分木が部分問題になっているので、 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 を引数に持つのがポイントで、再帰で行くとき、戻るときに cntsum をいじることで、 $0$ から $u$ の path の寄与が、正しいタイミングで正しく計算される。

ポイント

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

(2020-05-19) snuke さんが解説放送で披露してくださった LCA ライブラリを消化したので、よくわかるようになった。難しくはない。

Others