脳log[20230822]

2023年08月22日 (火) [AtCoder] 精進１。ABC133-F「Colorful Tree」(黄 diff)。高速に木を処理する問題。２つの頂点のあいだで、距離と、指定した色の辺の数と、指定した色の辺の長さの和が知りたい。距離は根からの距離を調べておけば LCA を引き算して求まる。色の辺についても同じことができるけど、色の種類数が最大で N-1 あることが問題になる。予めすべての色について調べて記録しておくことは N^2 になるのでできない。どうするか。クエリ先読みでやった。■提出 #44828105 (AC / 1276 Byte / 1269 ms)。木でクエリ先読みというと ABC202-F「Count Descendants」を思い出す。コンテスト中に解けたのは会心の出来だったから。■■■精進２。ABC143-F「Distinct Numbers」(黄 diff)。K 枚のグループがいくつ作れるかを二分探索した。グループ数を G とする。G 枚より多いカードは G 枚だけ使える。それ以下の枚数のカードは全部使える。使える枚数が K×G より少ないかどうかで判定する。■提出 #44829467 (AC / 247 Byte / 932 ms)。あーっ、今なら ABC の D 問題に Project Planning (青 diff) が出てきても解けるなあ。同じ問題だこれ。■提出 #44843265 (AC / 190 Byte / 336 ms)。まったく同じではない点は、この問題の K は 1 から N まで可変だということで、サンプルを見てわかるように K が増えるにつれ答えである G は減少するという性質があるわけで、個々の K について独立に二分探索で答えを求めることには無駄があった。