脳log[20220906]

2022年09月06日 (火) [AtCoder] 精進１。先週末あった NECプログラミングコンテスト2022 (AtCoder Beginner Contest 267)-F「Exactly K Steps」(青 diff)。木があって任意の頂点から任意の距離にある頂点(の１つ)を高速に求める問題。■提出 #34603482 (WA×14/TLE×2)。木の中心と、中心から出る頂点のうち２つの頂点について考えた(すべてを考えると星型の木で死ぬ)。与えられた頂点 U と中心と中心から出る頂点のうち U を含まないものがわかれば答えが出せる。距離 K が U の深さより大きいなら、中心から出る頂点のうち U を含まないものを根とする距離表を定数時間で引く。距離 K が U の深さより小さいなら、ダブリングで U の親をたどる。WA だった原因は中心を正しく求められていなかったことで、TLE の原因はダブリングのためのデータ作りで配列の比較を繰り返していたことだと思う。■提出 #34645281 (AC / 1549 ms)。WA の原因が誤った木の中心にあることを突き止めているあいだに、そもそも木の中心がいらないことに気がついた。木の直径の両端にある２頂点のどちらかを根とする木において U から K 個上の祖先をダブリングで求めれば良い。無駄にややこしくして無駄にバグらせていた。■いやしかし Ruby 最初の AC 提出 #34576790 の 41 行目に center = now #中心 とあるな。……使われてないけど。770 ms と自分の倍くらい速いのなんで？ 直径を構成する頂点のリストを用意して、U から直径までの距離を愚直に(１ずつ)数えてる。１回のクエリごとに高々半径と同じだけの遡行回数で直径に行き当たるだろうけど、それでいつでも大丈夫？ しかしこんなややこしいことをしていて早いし速いし間違えてないのすごいなー。■直径を幹として他のすべての頂点を幹から分かれた枝(※)と見る木のイメージはこれまで持ったことがなかったなあ。※枝の長さは分枝点から直径の両端までの距離のうち短い方より短いか同じ。■提出 #34582537 (tinsep19 さん / 1606 ms)。クエリ先読みもありか。そうか。まねまね>提出 #34647156 (AC / 1826 ms) うーん、遅い。■■■精進２。先週末あった ARC147-C「Min Diff Sum」(青 diff)。コンテスト中に三分探索を書いていたんだけど、そのときも今日も３分点を求める式を間違えていた。(l+l+r)/3 とか l+(r-l)*0.3 が書けなかった。もっとも、それが書けても不満度を妥当な計算量で求めるのがまた難しかったんだけど。この部分問題には ABC の C 問題と D 問題の中間くらいのポジションをあげてもいいと思う。■提出 #34655113 (TLE×23)。三分探索が書けて判定式が書けて不満度の計算ができても、ローカルで６秒かかっているのでジャッジサーバーでは３秒くらいかかると思う。TLE。■提出 #34656235 (AC / 746 ms)。ループの中の線形時間の処理を累積和＋二分探索に書き換えて AC。■提出 #34660104 (AC / 1739 ms)。整理していくと結局区間の左端の数と右端の数を数えるだけになって、三分探索も二分探索も不要になった。速くなるかなと思ったけど倍以上遅くなった。さっきの 746 ms がソート(NlogN)+累積和(N)+二重探索(log^2(N))で、今度の 1739 ms がソート(NlogN)+線形探索(N)。オーダーは O(NlogN) で変わってないけどね、だからこそこんなに差をつけられて、しかも負けてるのが納得しがたい。考察が進んで遅くなるとか……。ローカルで若干速くなってるものがジャッジサーバーでは２倍遅くなってたりするから、ジャッジが詰まりまくってた影響があったりする？ あとローカルでは入力の受け取り方を変えるだけで３秒が２秒になったりした。入力サイズがでかい。■提出 #34661754 (AC / 658 ms)。ちょこっと速くなった。二重探索に対して妥当な改善だと思う。