ferinの競プロ帳

競プロについてのメモ

2019-2020 ACM-ICPC Pacific Northwest Regional Contest (Div. 1)

チーム練でやった https://codeforces.com/gym/102433

BCLMは気づいたら通ってた

E

個数+1 を種類ごとに掛け合わせる

D

減らすのは/2で増やすのは+1しかないので適当にシミュレーション

I

同時に入れられないやつに辺をはると最大独立集合
swapのparityを考えると二部グラフなので求まる

A

全方位木DP
\sum_{u} a \lbrack u \rbrack  \times (u-vパスの重み) + a \lbrack v \rbrack  \times (u-vパスの重み) を求めたい
1項目は \sum_{\text{辺} e} (部分木内の頂点重み)*(辺重み)
2項目は a \lbrack v \rbrack  \times \sum_{\text{辺} e} (部分木の頂点数)*(辺重み)

1項目は dp[v] = sum(dp[c] + (辺v-cの重み)*(部分木cの頂点重み))
2項目は num[v] = sum(num[c] + (辺v-cの重み)*(部分木cの頂点数))

あとはこれを全方位にする

K

セグ木もって頑張る
キャッシュの方は最後にロードされた (i,p) の列を覚えておく
メモリの方は m 個の区間加算ができるセグ木をもっておく

クエリ2がきたタイミングでキャッシュの p 番目の情報をセグ木から取る
ただし、キャッシュに書き込んだあとにメモリを+1していると書き込んだ後の更新分まで反映してしまってまずい

クエリ2で答える場所について、何番目のクエリまでの情報で答えればよいか?をクエリ先読みで求めておく
クエリ1が来るたびその範囲にクエリ番号を更新しておいて、クエリ2がきたときにその位置を記憶しておくとできる
この情報を元にクエリ2の答えを求める

添字間違えて実装間に合わなくて涙

G

二次元平面で縦・横方向に移動する物体が衝突 → 直線y=-x+200000上に同時に存在
あるパルスがy=-x+200000に存在するか?を管理しつつ時系列順にシミュレートする
直線に乗るタイミングは t[i]+200000-a[i] で直線から消えるタイミングは t[i]+m[i]+200000-a[i] なのでこのタイミングで直線の状態が変わる

直線から消える方・乗る方をそれぞれまとめて処理しないと変なことになるので注意