結果

A,B,C,DはAC。EはさっきAC。

A - T or T

人数分の電車賃(AN)とタクシー代(B)を比較。

B - Good Distance

Nが最大10なので全探索。
差分の二乗の合計( $sum=(y_{1}-z_{1})^{2}+(y_{2}-z_{2})^{2}+\cdots+(y_{D}-z_{D})^{2})$ の $\sqrt{sum}-(long)\sqrt{sum}$ が一定以下で判定したけど問題なく通った。

C - Remainder Minimization 2019

$(i \times j) \mod 2019 = ( (i \mod 2019) \times (j \mod 2019) \mod 2019)$ なので $[(L \mod 2019),(R \mod 2019)]$ を考えればよい。 $O(2019^{2})$ なので全探索可。

[L,R]が2019の倍数をまたいでいるどちょっとややこしくなるかと思ったけどまたいでいる場合は0になる。最初にこの判定をして後は[L,R]で全探索すれば楽じゃないかな。

D - Rain Flows into Dams

すげえ馬鹿なことしてました。

LU分解とか逆行列とか使って解けばよい？
あれ？正則じゃない・・・？*1 いや、一意に定まるんだから正則のはず・・・。となんかすごいぼけた思考をしていました。めんどくなって方針転換

そもそも10⁵ x10⁵の行列の時点でダメです。

雨の量を一つ仮定
山1に降った雨の量( $x_{1}$ )を決めると他の雨の量も求まります。結果、 $x_{1}+x_{N}=2A_{N}$ となっていればそれで答え。

幾つか例を書き出してみて、 $x_{1}$ の仮定が解より大きいなら $x_{1}+x_{N} \gt 2A_{N}$ 、解より小さいなら $x_{1}+x_{N} \lt 2A_{N}$ となることに気づき、 $x_{i}$ の最小0、最大 $2A_{1}$ として二分法で解きました。

寝てる時に「あ、二分法使わなくても差分から一発で求まるわ」と気づいてフートンの中でじたばたしていました。

E - Virus Tree 2

寝て起きたら解けてました。

適当に根を決めます。こいつは自由に $K$ 通りの色を塗れます。子は親の分を除いて $K-1$ 通り。子が複数ある場合は $K-2,\,K-3,\,\cdots$ となっていきます。

子の子についは親と親の親が使えないので $K-2$ 通りになります。子の子が複数あれば $K-3,\,K-4,\,\cdots$ となっていきます。

f:id:trsing:20190708214826p:plain

子の子の子についても同様に考えて $N-2,\,N-3,\cdots$ となっていきます。

f:id:trsing:20190708214755p:plain — 子が増えたりしても考え方は同じ

根は $K$ 、子は $K-1$ 、子の子以降は $K-2$ からやっていけばよいです。幅優先探索しながらかけていくだけ。

F - Colorful Tree

~~そうのうちやる。皆目見当がつかぬ。~~

解説見ながらAC。解説のをC#に書き換えただけですが。

クエリの処理を考える

色 $x_{j}$ のすべての辺の長さが $y_{j}$ に変更されたと仮定して、二頂点 $u_{j},v_{j}$ 間の距離を求めよ。

まず $u-v$ 間の距離を求める。そのためには根とuの距離( $ur$ )、根とvの距離( $vr$ )、 $u$ と $v$ の共通頂点(最小共通祖先(lca))と根の距離( $cr$ )がわかればよい。 $u-v間の距離=ur+vr-2*cr(uv)$

次に色 $x$ の辺の長さが $y$ に変更された場合の距離を求める。それぞれの距離は
$ur'=ur-ur間のxの総長+ur間のxの数\times y\\ vr'=vr-vr間のxの総長+vr間のxの数\times y\\ cr'=cr-cr間のxの総長+cr間のxの数\times y$

変更後の $uv'$ の距離は

$uv'=ur'+vr'-2\times cr\\ \hspace{13pt}= uv-ur間のxの総長+ur間のxの数\times y\\ \hspace{18pt}-vr間のxの総長+vr間のxの数\times y\\ \hspace{18pt}+2\times cr間のxの総長-2\times cr間のxの数\times y$

f:id:trsing:20190712230203p:plain — 色 $x$ (赤)のすべての辺の長さが $10$ に変更されたと仮定して、二頂点 $u,v$ 間の距離を求めよ

色 $x$ (赤)のすべての辺の長さが $10$ に変更されたと仮定して、二頂点 $u,v$ 間の距離を求めよ

最小共通祖先 $c$ 、変更前の根と頂点 $u,v,c$ 間の距離、および頂点 $u,v,c$ に対する色 $x$ の辺の数と色 $x$ の総長がわかればクエリを処理できる。

最小共通祖先を見つける

割愛。

クエリ処理の高速化を考える

クエリごとに処理をすると時間が足りない( $O(QNlogN)$ )。頂点ごとに各色の数・総長を記録するとメモリが足りない( $O(N^{2})$ )。

クエリの読み込みとクエリの処理を分ければよい。

クエリの読み込み

クエリを頂点と紐づける(クエリごとに3つの頂点 $u,v,c$ )。変更前の $uv$ 間の距離を求める。

クエリの処理

色ごとの辺の数と総長を数えながら深さ優先探索を行う(往路で加算、復路で減算すれば根と頂点間の辺の数と総長が出る)。頂点に紐づけられた処理(変更前の長さに対して、 $u,v$ では $-xの総長+xの数\times y$ 、 $c$ では $2\times xの総長-2\times xの数\times y$ )を行えば答えが出る。