2020/07/17 - いろいろな記録

解説AC : 20分

ネタバレを見てしまった。ちゃんと考えればよかった。

最近作ったBITが活きる問題。一点加算と区間和計算ができると、配列のある成分の左右の成分の和などを $O(\log N)$ で計算できること自体を覚えておいて良さそう。

解説AC : 30分

何か色々考えていたが、結局ある一点でチャージした方がお得ということに気づけなかった。その上で次のステップとして、矢印を逆向きにしたダイクストラを使うというのは面白い発想だなと思った。（願わくば2ステップ目を考察したかった）

自力AC : 15分

diff高めに出すぎ？ダイヤグラム書いたらできる。 $T_1+T_2$ の間で、2回クロスするのか1回だけ交わるのかのチェックがミソ。

$T_1$ 時点と $t_1+T_2$ 時点での両者の差分が片方プラス片方マイナスになることが条件となるが、ここの判定に差分の積が負になるという条件を利用したら、積が1e19を越えてオーバーフローしてしまった。long longでも上限には注意。

解説AC : 30分

multisetを理解したのでほとんど自力でかけたが、一箇所ステップがバグっていた。分岐が多いところはフローチャートをメモして、個数など変化すべきでないところが変化していないかなどをチェックすること。