| A | B | C | D | E | F | |
| 問題文 | ■ | ■ | ■ | ■ | ■ | ■ |
| 自分の提出 | ■ | ■ | ■ | ■ | ■ | |
| 結果 | AC | AC | AC | AC | AC |
全体感想
32分5完で114位でした。
最近は6完できることが多かったのですが、久しぶりにやられてしまいました。
1500点のトップが99位ですので、スピードはまぁまぁだったようです。
整数論、数え上げなど得意分野はある一方、「木グラフに対してあれこれせよ」みたいなのは経験値がだいぶ足りていない気がします。共通祖先を求めるだけでもかなり実装量が多く感じてしまうのですよね。過去問（■）で経験しましたが、このときも数時間かかって書いています。今回のはそれより考察も実装量も重いので、現状だと実力不足…。手早く実装できるようにしっかり復習しておきます。
問題B – Good Distance
平方数の判定って、桁落ちによる計算誤差が怖いんですよね。32bit整数の範囲だと、
def is_square(n):
m = int(n ** .5)
return n == m * mで大丈夫かと思います。0.5乗の計算はfloat型の計算になって、$2^{-53}$ くらいの誤差は避けられません（参考：■）。roundあるいは+0.5してからintをとってあげると、少し誤差に強くなって64bit整数くらいなら耐えると思います。それでも数十桁になると誤差が出たりします。
問題C – Remainder Minimization 2019
全部やると、$O((R-L)^2)$ でダメです。しかし、$R-L$ が $2019$ 以上だと、$2019$ の倍数になるペアが必ず存在するのでこの場合は計算する必要がありません。$R-L$ が十分小さい場合だと、全探索の計算量が十分余裕です。
$2018$ 以下でもいいのか、$2020$ まで見た方がいいのかとか、細かい境界が気になったりしますが、計算量には影響が微小なので、間に合うなら少し多めにとって安心を得るのも良いでしょう。私は $3000$ 以下なら全探索という実装にしていました（ちょっとやりすぎ）。
問題D – Rain Flows into Dams
\[ x_1 + x_2 = a_1,\quad x_2 + x_3 = a_2,\quad x_3 + x_4 = a_3,\quad x_4 + x_5 = a_4,\quad x_5 + x_1 = a_5. \]
5つの式を全て足すと、$x_1 + x_2 + x_3 + x_4 + x_5$ が求まります。ここから$x_2+x_3$, $x_4+x_5$ を引くと $x_1$ が求まるので、それを使うと$x_2, x_3, \ldots$ も順に計算できます。
連立1次方程式の表現として、（特に機械に扱いやすい形に）行列による表示があります。
上の$N = 5$ の場合、
\[
\begin{pmatrix}1&1&0&0&0\\0&1&1&0&0\\0&0&1&1&0\\0&0&0&1&1\\1&0&0&0&1\end{pmatrix} \begin{pmatrix}x_1\\x_2\\x_3\\x_4\\x_5\end{pmatrix} = \begin{pmatrix}a_1\\a_2\\a_3\\a_4\\a_5\end{pmatrix}
\] と書けます。したがって、人間は行列とベクトルを機械が扱える形に整理してあげて、あとはnp.linalg.solve に頭を使ってもらうという方針もとることが可能です。
この際、$N = 10^5$ に対して $N\times N$ 行列を定義しようとするとその時点で標準的なPCだとメモリが不足します。このような場合は、疎行列を用いればOKです。解答例：■。
問題E – Virus Tree 2
一直線に頂点が並んでいるような状況であれば、初心者向けの典型的なdpでしょう。それが木になっただけです。
頂点 0 の塗り方を適当に決めます（$K$ 通り）。その頂点の周りに $n$ 個の頂点があれば、それらの頂点の塗り方は頂点$0$の塗り方によらず $\prod_{i=1}^n (K-i)$ 通りです。
さらに、この頂点 $n$ 個の塗り方が何であれ、残りの頂点の塗り方の数え上げは同じことになります。これは、頂点 $0$ を取り除くと木グラフがばらばらの部分木に分解され、互いに干渉しないことから分かります。
ということは、それぞれのばらばらになった木に対する部分問題を解けばよいです。
「部分問題に帰着できた」「小さい場合に帰着できた」
これすなわち漸化式とかdpとかの考え方そのものです。実装は再帰を使うのが簡単だと思います。
問題F – Colorful Tree
時間内に解ききれませんでした。LCA の計算だけでもほとんど経験がないので実装にすごく時間がかかります。そもそも30分以上を「重心分解するとどうなるか」等の考察に当てた（これ結局計算量が落ちない）ため、実装に当てられる時間が30分くらいしか残らず。その時間内でLCAを書ききってそこから先もミスなく実装して……というほどLCAが身体に馴染んでいないので、厳しかったですね。
解説では、Euler Tour がどうこうと書かれていて難しそうですが、ここは普通にdfsしながら各色に対する集計結果は使い回す（バックトラック）形でやってあげるだけで良さそうです。それほど考察難ではないですが私には手際よく実装できないやつなので、詰まらず実装できるように練習しておこうと思いました。
