No.920 あかあお

はい。$O(1)$ にできる。

これは $X, Y, Z \le 10^{18}$ とかでも解ける。 $S, T, U, V, W, X, Y, Z$ などと増やした場合も解けうるが、具体的な制約を見ないとあまり何も言えない。

No.921 ずんだアロー

はい。$\Theta(N)$。

手前 $2$ 要素だけ持ってればよい線形の DP をする。 このことから、数列 $A$ は数列 $B$ を $K \le 10^{18}$ 回繰り返したものとして与えられます、とかでも解ける。

No.922 東北きりきざむたん

解法

連結成分ごとに考えてよいことに気付けば、次のような問題に帰着できる: $N$ 頂点の木 $T = (V, E)$ が与えられる。その頂点には重み $w(x)$ が割り当てられている。木の $2$ 頂点感の距離を $d(x, y)$ と書く。このとき次を $O(N)$ で求めよ: \(\min \left\lbrace \sum _ {y \in V} d(x, y) c(y) ~\middle\vert~ x \in V \right\rbrace\)

この問題に帰着は LCA などを使って $O(N \log N)$ ででき、帰着後の問題は全方位木 DP あるいは imos 法で $\Theta(N)$ で解ける。

考察過程

  • 星 $3.5$ なの多いな。あと問題文が長い
  • 木を切ってできた森の上に空港を設置していく
  • 連結成分ごとに考えられないか？ → Yes。どの木に行きたいのか、どの木から来たのかは区別しなくてよいため
  • 各木の中で木 DP すれば十分そう。全方位木 DP かな
  • 全方位木 DP あまり書きたくないな、面倒なので
  • 各クエリの端点 $a$ から距離 $d$ 離れた頂点にコスト $+d$ して、最も低コストの頂点を選びたい。適当に根を決めたとき、imos みたいにすればその $a$ を頂点とする部分木については明らか。$\mathrm{parent}(a)$ について操作し、それに応じて $a$ にも包除原理ぽく操作してやれば打ち消せるはず
  • えー、LCA を久しく使ってないため貼るのが面倒
  • LCA を整備して CI に乗せた
  • 書いた

メモ

  • すべての点からの距離の総和が最小になるような点を木上で求めるのは典型問題そのままって感じがする。$1$ 次元上だと中央値になるやつ

リンク