ABC368 C - Triple Attack をやった
- 目も
- ソートし忘れ1WA
- どうしたらこういうミスを防げるか……
- (50パフォくらい失ってる)
- windows って関数、いつも忘れてしまう。
- メモ
- コンテスト中の考察
- カッコ列はとりあえず
( を +1, ) を -1 として累積和を取って、途中負にならない & 最後0を判定。Range Min セグ木を使った
- セグ木使わない方法は全然分からず。Stack でも使う？
- 知見
- 閉区間 $[1, N]$ の平方数の数が $\lfloor \sqrt{N} \rfloor$ 。半開区間ではないので、累積和みたいなことをやりたい場合は注意
- コンテスト中の考察
- $C+x$ の桁数を固定したときの $f(C, C+x)$ の最大値・最小値（取りうる範囲）を求めて平方数数え上げ
- 区間 $[L, R]$ に含まれる平方数の数を、いつもの累積和のノリで
$\lfloor \sqrt{R+1} \rfloor - \lfloor \sqrt{L} \rfloor$
で計算しちゃって詰まってた。
区間 $[1, N)$ じゃなくて区間 $[1, N]$ の平方数の数が $\lfloor \sqrt{N} \rfloor$ だから
$\lfloor \sqrt{R} \rfloor - \lfloor \sqrt{L-1} \rfloor$ が正しかった。
- コンテスト中に困ったこと
- $C+x$ の桁数を固定すればいいところまでは行き付けたけど、$C+x$の桁数を固定したときの $f(C, C+x)$ の取りうる範囲を考えればいいというところにたどり着くのにとても右往左往した。どうしたら速く解けるのか？
- メモ
- コンテスト中の考察
- 全方位木DP。argmax を求めるには、(値, 添字) を乗せれば良さそう
- やること
- 木の直径解法を知る
- 全方位木DPを理解する
- 全方位木DP に記載したい
- 各部分木での値も返せるようにする(重心求めるときに使えそう)
- 全方位木DPの非抽象化テンプレートを用意しておく
普通のdpで(値, 添字)を使うのはどう？
タイトルの通りピラミッドだと思うと見通し良かったかも（コンテスト中は気づかず）