Yuya Ryuzaki | hotman78
Yuya Ryuzaki | hotman78
確かにそうですね... あまりいい方法が思い浮かんでません 要素数が一定値を超えないことを保証するとかですかね...
現状問題文がかなり説明不足な気がします。 permutation treeが一般的な単語であれば省略しても問題ないのかなとは思ってます。 一般にpermutation treeといった場合条件を満たすノード数最小の木のみなのかもわかっていません。 取り敢えずジャッジではノード数最小の木のみをACとするのでいいと思ってます。
大分時間がたってしまいましたが、問題文を書きました。
ご指摘いただいた点直しました！ ありがとうございます！
ごめんなさい、まだチェッカー作れてませんでした。今のままだとpreorderしかACにならない状態なので、可能なら戻して欲しいです。
@yosupo06
提出も大した量出ないと思うので新規でissue立てて早めにプルリク送る形にしようと思います。
ヒントになるかわからないのですが、一応考えたことを投下します。 対称性を利用した最適化と相性がよさそうに見えます ```python for i in range(n): for j in range(n): ``` となったとき `i`と`j`をswapした式を別に足してあげるようなruleがあると幅広く最適化になる気がします。 また、 ``` python if i != j: ans+=hoge ``` を ```python ans+=hoge if i == j:...
monoid が乗るデータ構造に対して monoid 全体を入力として与えていない事を考えると、 monotone/totally monotone/monge に関しても特殊化して与えてしまっても問題ないと思うのですがどうでしょうか。 具体的には、 f(i,j)=g(A_i-A_j)+B_i+B_j ( g は あまり大きくなりすぎない程度の多項式(CHT の区別を考えると 3乗（？）が良い？)) などがあると思います。
と書いてから思ったんですが実は新機能の C++(Function) header を応用すれば（言語が限定されてしまいますが）インタラクティブ可能そうなので、それもありですかね。