はい。やりました。結果は順位を見る分にはふつーの結果。 ABCDEFの遅解き6完といった感じでしょうか。 Fに関しては正当性がコンテスト後になんとなくわかった感じになった。 時間も少ないしダメ元で提出してみよーっていうのが功を奏した感じですね。
狭義単調減少です。ソートしたものとの比較じゃうまく行かないので、それで少し解くのが遅くなった。 forで丁寧に回します。
これちょっと複雑。場合分けだぁ。とりあえず、$S_{N-1}$ までにおいても、 maxとminについては足さないようにしておいて、最後の値がminより小さくなるようだったら、 minが足される。このときminを足しても $X$ 以上になってくれるようだったら、$0$ を入れてok. また、入れる値がmaxより大きくなっても maxを足す羽目になるので、これで $X$ よりちいさかったら、 どうやっても $X$ 以上にできないので $-1$ をする。これ以外は入れる値がそのまま足されるので、 $X$ になるように調整する。
小さい桁から、321-like Number をdfsなどで見つけていく。全通り試せたら、 全部vectorに入れて、ソートして $K$ 番目の値をだせばok.
何も考えず、int と型を置くのはやめようね。2WA.
データの順序は関係しないのでどっちもソート。 このとき、 $i$ を選べば、どこまでが総和として $P$ 以下になるのかがわかる。 $P$ 以下になるような $j$ については $B$ についての累積和を使って総和を求めておいて ($A_i$ を足すのも忘れず)、 その他は $P$ を足すような動作でそこまで時間はかからない。 自分の解は $O(N \log M)$ と言ったところだろうか。まあ実際は $A$ もソートしちゃってるから違うけど。
とりあえず、完全二分木のような形の木だろう。そのため、根までの深さも $ \log N $ 程度しかない。 頂点 $X$ の子であるようなものから距離が $K$ なものは求めやすい。 だが、親側のほうはちょっと分かりづらい。このとき、親に潜って、もともといた子のじゃないほうの 部分木について見ることを考える。 これを根まで繰り返せば最終的に全部見れる。親に潜るたびに $K$ を $1$ 小さくして、 子について見るのでその子について 距離が $K-1$ なものを見る。 これを根まで繰り返す。すると答えが出る。 各親について $O(\log N)$ の処理がされるので、 $O( \log^2 N)$ となると思う。
木の見てない方を見るという処理の書き方をミスって 1WA した。バグ取りはどこが間違っているか 分かりづらいので、時間がかかってしまう。
- の処理のほうの処理をどうしたらいいかを迷っていた。それはそうだけどｗ 最初はクエリの順序を変更するのかとか思っていたけど、すでにできたdp配列から計算可能だった。
このとき、$x$ を削除するとして、$i$ を昇順に、dp[i+x] -= dp[i] をしていけばよかった。 これも部分的にdpのようになっている。まず dp[0] はどうあっても $x$ は使われていないので、 完成していると言える。このとき、この状態から $x$ を使った状態がおかしいので、dp[x] は dp[0]の数だけ減らさないといけないと言える。 するとdp[x]は完成する。これを昇順にやれば、dp[i]を見るときにはすでに完成した配列となるので、 順序よく処理できるというわけだ。
たしかにdp[0]という絶対に使ってないものがあったなという思いになっている。
何となくこれで通りそうかなーっていうことも時には大事だと実感した。役には立たないけど。 コンテストの順位を上げる程度には役に立つ。付け焼き刃。
解けてないから感想はあまり言えないけど、なんか連結成分数と、もう連結しない要素みたいなのを 持てばうまく行きそうかななんて思った。うーん、dpのなかでdpをするとか？わからない。
perf=1823だった。Fを解くのが遅すぎかなー。6完下位という感じ。 ただ、Fを解いてなかったらもっと悲惨なことになってたから、まあ助かったとは言える。 ABCのパフォは結構安定していると思う。競プロを3年程度やってなくても、この程度のパフォが でてるということは、割と自信を持ってもいいとは思う。
ちょっと追記だけど、Fみたいなのは、なんか典型っぽいので、なにかに使えるかもーなんて。
(2023/09/23 23:21)