N_noa21`s memo

競プロメインです

4/27

ABC351をA~DとFの5完。

Eはチェビシェフ距離ってことまで考えたけど詰めきれなかった、勿体無い様に感じるけど結局実は遠かったのかもしれない

 

E - Packing Potatoes

ループするやつ。なんか足し忘れて地獄を見た

 

E - Virus Tree 2

上側から見て木DPぽいやつもできるんだ〜ってやつ

 

F - XOR on Grid Path

半分全列挙でいけそうだけどわからんって言って解説見たらそうだったやつ。

9/24

F - #(subset sum = K) with Add and Erase

昨日の問題。

例えば2,3,5を数として持っているときに、5を2通り作れるが、3を取り出したときに2,3からできた5と単体の5を区別できるのか？と疑問だったが、

 

確かに3がなくなったとき、dp配列にはこれまでの2,3,5で作れる数の場合の数が入っているため、現在の5の場合の数から、3がなくなった場合の2の場合の数を引いてやることで、3を使っていたパターンだけを引くことができると考えると納得した。

また、この手順のときに加算の場合は降順、減算の場合は昇順にやらないと手順がダブってバグるので注意。

9/23

F - Bread

いわゆるマージテクらしい。

分割の過程を二分木として書いてみると、確かに分割する際にこれ以上分割しない部分もこれまでの分割で含まれていた回数分コストがかかっているし、

さらにこれから分解する分は今までの分解にかかるコスト+これからする分解にかかるコストがかかるので納得。

よって、深い方からコストを小さくするように並べて、深いところからマージしたら一段上に上がる、というようにすればコストが求まる、ということらしい。

 

操作を逆から見たらどうか、という思考は常に片隅に置いておきたい。

 

 

9/21

一応9/21が誕生日でした

今日から心機一転頑張りたいところ

 

E - Warp

座標でdpできないよ〜となっていたが、問題をしっかり読めてなくて、ワープの種類が3種類で300回までなので全体、1つ目のワープの回数、2つ目のワープの回数でdpして、障害物がある座標なのかの判定を入れてあげればよかった

 

3種類の変数x,y,zの時、全体nがわかっていたらn,x,y,zではなくzはn-x-yでわかるからn,x,yだけでいいというテクニックを忘れがち

 

9/22

E - Takahashi and Animals

外出したのでこれだけ、DPを書くときにそこまで計算する量が多くないなら場合わけしてdp1、dp2のようにしてもいいという手法

9/17~9/20

ここ最近のやつ

E - Add and Mex

結局0~200000までになる数はAiにiを加算より、iが大きくなると適する数がどんどん減って2000000くらいで済むやつ。思いつかなかった。

 

E - Notebook

根付き木の構築として考えればよかったが、気づかなかった。

ADDとかDELETEから頂点のことだと思えばよかったのか？

 

E - MST + 1

 

頂点1から最小全域木を作って、そのクエリの辺が追加されるのと最小全域木上でクエリの辺が結ぶ頂点がつながるの、どっちが先かな〜をしようとしたが、これだと3個以上の頂点を含むサイクルで他に辺がない場合のケースを考えられないので、全ての頂点から最小全域木をする必要になり？になるので、

クエリをまとめて重み順にしてから処理する。この処理の連結判定はUnionFindでする。で上手くいくらしい(クエリをまとめて処理、あまりやったことなかったから意識したい)

 

(追記):元々やりたかった解法がkyopro_friendsさんが書いてくれてたダブリング的なのでできるっぽいので調べてみると、アルゴリズムロジックというサイトが書いてくれてた、どちらもありがたい〜〜。

https://atcoder.jp/contests/abc235/editorial/3258

https://algo-logic.info/lca/