AB の 2 完(16:07)。椅子を温めるぞｗ
なんか色々 CD について考察したけど、あんまりいいところまで行かなかったから、やっぱりARCは難しい。 ただ、今回は速解きのおかげで、パフォはおそらく死んでいない。でも悔しい。
転倒数を最小にするにはできるだけ値を大きくしていけばいいので、大きくできる時無限大まで大きくすると仮定する。 すると、連続の減少部分列の転倒数のみ考えればよくなるので、これは適当に下がった個数を $c$ として、 $c(c-1)/2$ みたいなので出ると思う。まあ、現在の減少部分列の長さを持っておいて ">" が出るたびに ans に それを足せばいいという実装になると思う。
これは知識として知っているかが一番だと思う。 $k$ を選んだときの Nim というのは、それぞれの石の $k+1$ で割ったあまりについての XOR が 0 でないとき Alice が勝つというものになる。
今回は、まず何も制約がない状態で Alice が勝つなら $k$ をいくらでも大きくできる。 そうでない時、ある 値の個数が奇数であるような値の最大値 $v$ を考えて、 $k=v-1$ に設定して Nim を行う時 XOR が $0$ じゃないようにできる。
そのため、結局それより大きい値ではずっと XOR は $0$ であるので $v-1$ が最大値だということがわかる。
なんかとりあえず、ソートしても答えが変わらなそうなのはわかったので、 A の数 と B の数 と C の数 に着目すれば数え上げの部分で計算量に $N$ を使わないような実装ができるのだろう というかんじではあった。
そのあと、どうやって入れ替えるのかということを考えたが、よくわからない。いろいろ試したが合わない。
CD は並行して考えていた。 $R$ を昇順、$L$ を降順でいけるかなと思ったが WA が出て反例を見つけた。 $R$ がかぶらないなら良さそうなのだが、かぶっていると、塗りつぶし方の工夫をしないと駄目みたいである。 そこから詰めるのがよくわからない。雰囲気的に DP が漂っているが、どのように落とし込むかもよくわからない。
現在の塗りつぶすサイズの小さいものを順にやろうみたいな実装をしてたら全く間違っていた上 30 分くらい消費した。 手を動かそうと頑張っていたが、このようになることもあるのである。
うーん、知識があると考察の時間を省けるのでかなり便利だなと思った。そのおかげで 爆死せずには済んだ。 ただ、やっぱり考察力という点で言うと、CD が解けない以上あまり成長が見られない。 ARC の CD などはほとんど埋めていないので解けないのはまあ当たり前っちゃ当たり前だけど、 考察力の成長ねぇ・・・なんかシステムをシステム化するかのような成長だよねぇ。
考え方のアップデートみたいなのって自分を塗り替えながら自分が操作するからなんか一番難しそうではある。
(2023/11/19 23:23)