👏
PAST 第 13 回の感想
A
寝起きだったので時間がかかった。
よく考えるとやるだけ。
B
AB と CD の符号を比較しつつ AD <=> CB の比較と思ったが 3 WA が消えず
仕方ないので Rational で殴った
C
Set に入れてえいや
D
UnionFind
E
閉じの方が多くなったり最後に閉じてなかったらだめ
F
算数をした
0 より小さくなる場合に気づかず WA が出た
G
Kadane だね
出題したことあり
H
Sum of difference そのもの
I
SCC をする
サイズ 2 以上の強連結成分があったら No
J
それぞれの直線について、 S と T を分割しているか判定する（外積でできる）
分割していない→選ぶ
分割している→コスト小さい方から貪欲
K
わからず
d(n) を決め打ちかと思ったけどそれもむずかしそう
L
これ最大独立集合じゃね！？と思って区間の最大独立集合で検索したら区間スケジューリングが出てきた
右端でソートして順番に処理するとよさそうということで考えてみると、座圧して左端で区間最大値セグ木に入れるのがよさそうとなった
M
ぼーっと考えていたら DFS でできるのでは？というひらめきがきた（LIS on Tree みたいなかんじに）
頂点 1 以外の頂点は、必ず含まないといけない区間が決まっているので DFS しながらそれをもとめて、主客転倒っぽい感じで答えを出す
N
Set に入れて前後の値を探すとできる
O
遅延評価付き平衡二分木を書きます書くのを諦めたので Nyaaan 様のライブラリを窃盗した
巡回シフトを区間 Reverse で表せるんよな…って誰かが言ってたのでやってみたら TLE が出て泣いた
Discussion