新ABCで初めての、自分がrated対象外になった回。Fを解いている途中36.8、終了後36.9（（解けそうになかったのに）上がるの！？）。rated回と比べて心拍数が上がりにくいと感じた（下がりやすいと言ったほうがいいかな）。体温は上がっていたので、このくらいがちょうどいいという気もする。立ち回りは決めていなかったが、「スピード重視、順位表は見ない」とした。結果的には5完早解き回だった。パフォーマンスは1844相当。調子は悪くなかったが、早解き回だとこんなものだろう。
A - T or T
これは書くだけ。久しぶりに問題文がすぐ見れたので、気持ちよく提出した。
現実にありそうな問題で想像しやすい。いい感じのAだと思う。
B - Good Distance
やるだけとはいえかなり重い。なんとかスピードを出してきれいに書くが、平方数判定で少し迷った。sqrt()の結果が整数のときは必ず小数部がゼロになってるという知識を使い何が最も自然な書き方か考えたがわからなかった。整数にキャストして2乗してみるのもあったかなあ。いやないか。
確かにループが書ければ解けるけど、その中ではかなり難しくなっていて、バランスのいいBだ。
C - Remainder Minimization 2019
ちょっと悩んでしまったが、区間の長さが2019以上なら0が含まれるので0。そうでなければ全探索できる。しかし、i,jが10^9に達することがあると知っていたのに忘れてオーバーフローでWA。問題が面白かったので勢い余ってしまったね。これいつも通り見直してたら気づいたかなあ。気づいたか知る方法ないの嫌だなあ。ていうか今見たら2*10^9だった（これは気づいてなかった）。
これもABCのCって感じで好き。先週のと違って歯応えもある。
D - Rain Flows into Dams
問題文を読むのに3分かかる。そして降った雨の量が与えられると誤読。「解が一意に定まる」と書いてある理由がわからないままとりあえず実装してみるが、なぜこんなに簡単なのかわからないし、Nが奇数である理由もわからない。当然サンプルも合わないので、そこをしばらく考えて誤読に気づく。これは、時間をかけて考えたいやつだ。コンテスト中に短時間で解くのが苦手なタイプの問題。とりあえず山が3つとして考える。降雨量の半分をA（Aにしてるあたり混乱を引きずっている）として、Aが決まりそうな方程式が立つなと、けっこうな時間紙で計算して気づく。2つだと確かに定まらないな、というのも確認。そうして山_N-1に降った雨の量がわかって、残りも芋づるにと思ったけどサンプルが合わない。最初に山とダムを取り違えていたので間違えてる。山_1が求まってるんだよね。2を掛けるとか割るとかも混乱してて、幸い問題が思ったより簡単だったのできれいに書いてACすることができた。ただ、このプログラムが本当に負の数を出力しないのかは確信できてなかった。
E - Virus Tree 2
距離2なので、各頂点から1歩で行ける範囲は全部違う色と言い換える。根から塗っていく方針は思いつく。その塗って行き方がなかなか定まらなかった。そして何とか書いてもサンプルは合わない。細かいミスもしていたが、親の親とも違う色である必要があることが抜けていた（サンプルの図を見ながら脳内でコードを動かし気づいた）。コンビネーションじゃなく順列っぽいやつなのも珍しくて、まあ考えればすぐわかるんだけど、過学習してるなあという感じ。ずっと見通しがなくて、時間がかかった。ここはもう少し速く解きたかった。
F - Colorful Tree
サブセット問題を考える。クエリの色が1通りだったら？難しそうだが、LCAを色毎にやればと思いつく。当然それは計算量的にできない。次に、木がまっすぐだったらと考える。元の長さが全部1で、全部のクエリで2になるとすると、長さNの数列の指定区間にxが何個あるかのクエリに答える問題になる。これは解けそうに見えないし、いくら考えても解けそうにない。ここで、各色に対し高々1回しかクエリが来ないことを考える。すると、色毎に頂点リストを持てばその色の各頂点が区間に入るかは判定できるし、全ての色についてそれをやってもO(N)の計算量で済む。LCAでもlogが付く程度でできるんじゃ？現実には、たくさんの頂点を持つ色のクエリがたくさん来る可能性がある（厳しすぎる何だこの問題は）。何とかできないか考えていたが、どうにもならない。
最後の10分は、久しぶりに「座ってるだけ」だった。ABCでこれかあ。
