脳log[20240905]

2024年09月05日 (木) [AtCoder] 精進。ABC369-G「As far as possible」。なにやら「貪欲法」「HLD」の文字が目に入ってきていた。だからといって、なるほど、そう言われてみればそうか、とはならなかったので、なかなかに難しい。同じ問題がまた出てもやはり解けないだろう。実装の練習だと割り切ってどのように実装するかを考えた。BIT……セグメント木(ちゃんとしたやつだと区間加算をしながら区間 max を取得したりできるの？)……オイラーツアー……マージテクの巻き戻し……。■提出 #57459978 (AC / 1442 Byte / 1308 ms)。マージテクは必要なかった。最も遠くがどれだけ遠いかだけを葉から根へ積み上げていった。候補の中から最も遠くへ通じている枝を選ぶのにはプライオリティキューを使った。■Ruby によるすべての提出を見るとゴルファーがひとりいるだけだった。提出 #57339115 (173 Byte / 936 ms)。あきれるほかない。入出力とソートをしているだけにしか見えない。短く、そして速い。そんなのおかしいよ。■こちらのブログ「ABC369 - merom686's blog」から「木全体で一つのvectorに突っ込んでしまえる」「自分は子への辺を2回走査したが、解説の実装例では1回しかやってなくて」「最大値を更新するタイミングでそれまでの最大値を（最大値である可能性が今なくなったので）vectorに入れていた」というのを手がかりにして、なんとか１パスで、最大値を取り合うような実装をひねり出した。提出 #57461586 (AC / 321 Byte / 822 ms)。提出したあとでもまだ化かされてる気がしてる。答えが見えなければ実装法も見えない。難しすぎる。■■■けんちょんの解説が上がっていた。「AtCoder ABC 369 G - As far as possible (3D, 黄色, 600 点) - けんちょんの競プロ精進記録」。そこに「ここで重要な考察として、 K = 2, 3, \dots のときは、頂点 v_{1} を使うものとしてよいことがわかる」と書かれているが、自分が思考停止してしまったのがここで(つまりわからなかった)、K=2 の場合に K=1 の答えを選ばない最適解があるような気がしてしまったのだった。読んでも頂点の位置関係がうまく把握できなかったので自分で考えますよ。K=1 の頂点 V1 とは異なる V2、V3 を青木君が選んだとする。他に根 V0 と、V2、V3 の LCA として C0 が頂点として存在する。V0=C0 の場合もある。いま、V1 と V2、V3 との LCA が C0 より根に近いか、V2、V3 の方に近いかを考える。LCA が C0 と一致する、もしくは V2(V3) に近いとすると、V2(V3) を V1 に置き換えた方が青木君の得になる。置き換えても V1、V2 と V3 との関係は変わらない一方、LCA より先は V2 より V1 の方が長いのだから。LCA が C0 より根に近い場合も頂点を置き換えた方が青木君の得になるし、LCA と C0 との距離の分だけよりスコアを稼ぐことができる。K=3、4... についてはわからないけど、けんちょんのページには書いてありますよ。コンテストのことを考えると難しいのは、「K=2 の場合に K=1 の答えを選ばない最適解があるような気がしてしまった」ときに、それは最適ではないのではないかと疑って、自分の直感を否定するような証明を考えることができるのかということ。できないんだよなあ。たぶんこうでしょで深く考えないのが自分の性分であれば。間違いだとはっきりするまで間違いを疑ってもいいことないじゃない。