今回は ABCDEF の 6 完 (59:51+05:00, Eで1RE) なんか変な解き方したのが多かったがまあまあいい感じではある。
for を回す。
問題読解に時間を費やした。まあ範囲外の時とそうでないときを場合分けすると解ける。 範囲外のときは $L, R$ どちらか近いほう、そうでないときは $A_i$ を出力する。
形からして、全探索ができそうなのはわかる。 $x$ を回しておくと、$D - x^2$ が出るので、これ以下の最大の $y^2$ を見つけてくる。 sqrt 関数を使ってもいいが、自分は二分探索で見つけた。 この時、$(x, y)$ か $(x, y+1)$ について見てあげると、候補はすべて列挙できる。
条件を満たすようなマスの角に該当するようなところをみて、縦にある 'o' と、横にある 'o' の 数をかければ良い。自分は $4$ 方向の可能性を全部やるために縦に対する累積和と横に対する累積和 を取って計算したが、どうやら、一気に計算できたようだ。
ちょっとそういう経緯から実装に時間がかかってしまった。
とりあえず $\mathrm{mex}$ は $N$ 以下であることがわかる。 ある値 $x$ の個数を $c_x$ みたいに取っておくと、 $c_x = 0$ であるところの最小を探せばいい。 さっきの $\mathrm{mex}$ が $N$ 以下なことを考えると、$c_x$ の配列数は $N+1$ 個だけあれば十分である。 それより大きい値は考慮しない。
このようにする時、$c_x = 0$ であるところを $x$ で更新するような RMQ を作ると、$\mathrm{mex}$ が もとまる。クエリの更新も値の変更のために高々 $2$ 回程度しか更新しないので、普通に間に合う。
RMQ みたいなのを使わなくても set を使っても解ける。
まず、$X, Y$ は独立して考えられる。idx をずらしても問題なし。よって $X, Y$ ごとにソートしてOK. この問題は、ある１辺の長さと点を集める位置を決定できればそこにすべて座標を持ってくるときの 操作回数が $K$ 以下であるかという判定問題になる。
わかりやすさのためここでは $X$ だけ考えてみる。
まず１辺の長さ $L$ を決めうってみる。だが、この時点ではどこに集約するのが最適なのかが決まらない。 ここで重要な考察として、１辺の範囲を $[l, r]$ だとすると、最適な答えの中に $l = X_i$ であるか $r = X_i$ である $i$ が存在することがわかる。 これは範囲外の点について右にあるものと左にある物の数が変わらない場合操作回数が同じになるからである。
そのため、$X_i$ を範囲の左にする時のものと、 $X_i$ を範囲の右にするときのものの操作回数を 列挙してその中の最小のものを調べれば $X$ 座標における １辺の長さ $L$ の最小の操作回数がわかる。 $Y$ も同じように処理すればいい。
例によって、この問題は $L$ に対して操作回数が単調減少になるので二分探索ができ、 この問題を解くことができる。
個人的な感想として、Absolute Minima が役に立ったかなと思った。
なんかうまいこと主客転倒のテクニックが使えないかなと思ったのだが、二乗和を求めるらしく、 うまく行かなさそうだということがわかった。
他に考えられることとしては、転倒数が $k$ である順列の数 $f(k)$ を数え上げられれば、 $k$ に対して答えが $k^2 f(k)$ になるよなぁとは思った。
後は順列の性質とかちょっと調べたりしていたがまあちょっと難しすぎるね。
Perf=2056 でややレートが上がった。コンテスト中にテンパるのをどうにかしたい。 なんか F の実装で変に時間を掛けてしまった気がする。
最近はとりあえずパフォーマンスが安定しつつはあるので継続できればいいと思う。
(2023/11/25 23:23)色々と後から想定解も見ながら解いてみた。
B は std::clamp というものが存在しているようでこれのおかげで場合分けが要らなくなるようだ。
F についてだが、これも別解の解説を見ると実装が簡単になるようだ。ほぼ解説と同じだが頭の整理の為書いておく。 この問題の $L$ を決めたときの小問題は、区間の位置を選んでその区間の位置に玉をすべて持ってくるときの最小の操作回数を 求める問題になっている。
区間の左端を右に動かした時、ある玉 $i$ についてどのようにコストが変化するかと言うと、 区間の長さを $L$, 左端を $X$ , 玉の座標を $x_i$ とした時、$X = x_i-L$ の時、傾き $-1$ から $0$ に変化し、 $X = x_i$ の時傾き $0$ から $1$ に変化するという形になっている。
このような形になっているものは傾きが変化する $x_i-L$ と $x_i$ について考えるとよく、 このような座標をすべて入れてソートした時、傾きがゼロになっている座標はこの配列の $N$ 番目と $N+1$ 番目の間になっている。 下に凸の凸関数で傾きが $0$ の場所は最小値になっているのでその部分の座標は操作回数の最小を示すことになる。
この座標のソートはマージで大丈夫で $O(N)$ でできる。座標が見つかったら、 後は普通にシミュレートするだけなのでこれも $O(N)$ である。 といった感じで解くとかなり実装量が減る。
上で ABC127 F の Absolute Minima が役に立ったと書いたが、まさに傾きを持つやり方という意味で一致している。 この調子で ARC070 E の NarrowRectangles も解きたい。 厳密には解いているが、もう解法を忘れている。
(2023/11/26 02:58)