今回は ABCDEF の 6 完 (74:13+5:00, Fで1TLE) F を犯罪で通した。だが通れば良いのだ。 かなり難しいセットだったみたいで 6 完できたのはよかった。
愚直に実装しよう。バグらないように。
書かれたとおりに実装する。
オーバーキルじみているが、二分探索でそれぞれ調べた。
行を入れ替えた順列と列を入れ替えた順列を用意して全探索するとよい。
重要な考察として、平均値はどのようになっても変化しないということである。 つまり、分散の途中経過を書くことができる。 するとこれは部分集合を扱う DP そのものであるのでそれを書く。 $O(3^N D)$ かな？
その時の期待値を常に持っておけるようにできるのが理想なので、遅延セグ木で実装できないかと考える。 すると、クエリに対して確率 $p$ と値 $v$ をもつような作用素を考えるとうまく実装できる。 作用素同士の計算に割り算がでてくるのでかなり重く TLE してしまったが、 できるだけ定数倍がかからないようにして GCC optimize してみたら通った。 まさに犯罪。
普通に入れるときの反例さえ見つけられていない。F を解いて燃え尽きちゃった。
なんか E が結構解かれていないみたいで、でもこれは DP できる形にまでなったらいつものなので、 かなり練習が役に立ったと思う。 F は $\log P$ を取り除く方法あるんですかね・・・ まだ完全に通しきれたと自信は持てないので普通の時間で通せるようにしていきたい。
(2023/12/10 22:55)F で GCC optimize で通したと書いたが、実際にありなしで提出してみたらなしのほうが速かった・・・ どうやら、TLE したやつに比べて 作用素の割り算を $2$ 回から $1$ 回にしたところが速くなっていた要素 だったみたいだ。まあそもそも最適化できそうな形してないからそりゃそうなのかな。
あと、F を作用素計算に $\log P$ を付けずに計算する方法だが、アフィン変換を使うといいらしい。 これは現在の値 $a$ に対して $ba + c$ に更新するようなクエリに使える。 今回は、$a$ が $(1-p)a + px$ に更新されるのでこれが使える ( $p$ は値が変わる確率, $x$ は変更する値)。
まず値を保持するベクトルに、 $ \begin{pmatrix} a \\ 1 \end {pmatrix} $ を使用する。そして値を変更するクエリの行列が、 $ \begin{pmatrix} b & c \\ 0 & 1 \end{pmatrix} $ となる。 これを計算すると、 $$ \begin{pmatrix} b & c \\ 0 & 1 \end{pmatrix} \begin{pmatrix} a \\ 1 \end{pmatrix} = \begin{pmatrix} ba + c \\ 1 \end{pmatrix}$$ となるので計算できていることがわかる。 作用素同士の計算についてもこの行列を左から掛け合わせれば良いので割り算が出てこないといった感じだ。
アフィン変換で定数になっている部分については実際にデータにするときは省略できる。 つまり、値は $a$ だけ持っておけばよく、クエリは $b, c$ だけ持っておけば良い。 どのように要素を変化させても、作用素を変化させても定数の部分は常に同じ値であるからだ。
また、今回は遅延セグ木で解いたが、クエリを取り出す部分が $1$ 点のみであるので、 このようなものに対しては双対セグ木というものが使える。 おそらく、作用素の計算のみを行う遅延評価セグメントツリーであり、要素を持つ必要がない。 このようにすると、末端の部分( $1$ 点の部分) だけはその位置の作用素を常にすべて集めることができるので、 区間を持たない $1$ 点について作用素の計算したものが出るようになっている。 後はこれに対してもともと置いてあった要素と作用素を組合せて、要素についての答えが出るといった感じだ。
本番は 2158ms で通したが、アフィン変換を必要なところだけ適切に書いたら 380ms まで実行時間が下がり、 これを双対セグ木に変更したら 227ms にまで実行時間が下がった。 セグメントツリーだけで通すやり方など、まだ色々と方法があるみたいなので、 また追記を書くかもしれない。
(2023/12/11 16:02)双対セグ木のライブラリについて function 型を使わない実装に変えてみたら、 227ms -> 144ms まで下がった。これはすごい。 モノイドの型を作ってそれをそのままセグ木に紐付けるような実装になる。 こうするとそれぞれのモノイド(クエリ？ 普通のセグ木だとRMQ とか RSQ とか)の管理も楽になるので良い。
普通のセグ木や遅延セグ木もそのように実装を変えたらかなり速くなった。 funcition型はやっぱり遅いんだなぁと思った。
(2023/12/21 02:22)