競プロ界の最高峰の問題を堪能できる身体になりたい！
Joined December 2020
- Tweets6.1K
- Following1.6K
- Followers3.5K
- Likes9.6K
【Monge 精進】
12：ABC 480 G - Zonal Score Minimization（3D+)
atcoder.jp/contests/abc480/s…
・「f(l, r) := 区間 [l, r) の最大値と最小値の差」とすると f は anti-Monge！！
・r - l = 1 の部分を適切に除外すれば、分割統治 SMAWK 法で対処できる！！！
【Monge 精進】
13：yukicoder No. 409 ダイエット（3D+）
yukicoder.me/submissions/119…
・f(i, j) := 最後に食べたのが i-1 日目で、そこから j 日後にはじめて食べるときの、その期間の体重変化
・f は Monge
・f は2次関数なので直線 CHT でも LARSCH 系アルゴでも好きなもので通せる！
planar duality は例題がこれだからね。典型化したとて、planar duality の成立性をいうための証明の部分が難しくて、そう簡単には difficulty が下がる気がしない。
割と安心して 6D- を付けられる。知られれば一気に解かれるようになる問題とは今のところ位置つけてない。
atcoder.jp/contests/arc214/t…
slope trick や maroon 典型のあたりとか、まだ整理し切れてないしね……最低限、あの辺ちゃんと理解しないと。
あと、DM 分解のお気持ちは分かったけど、深淵はまだ分かりきってない。
あと、planar duality も習熟度が足りない。
yukicoder の難易度推定に疑問を呈している人の大半は、考察系の問題に対する考察の難易度の評価について言及している印象を持った！！
僕は yukicoder の問題を解くとき、ライブラリの verify に使うことが多くて、そっち側の視点だとかなりいい線行っている印象を持った！！
yukicoder、これから新しく AC するたびにレビュー書いていきたいと思った！！
yukicoder.me/problems/no/409
この問題で、タグ「多倍長整数」を取り下げて、タグ「Monge性によるDP高速化」を入れることを提案した！！！
すごく典型的な問題に限っては、Difficulty を ±100 以内の精度で見積もりできると思っているため、そういう問題に関しては 100 ズレてるだけでも yukicoder に FB を送ることとした。
(これ、やるなら似た系統の問題は全部一律にやるべきで、一部だけやるならやらない方がいい可能性はあるけど…)
昨日は Monge 性を満たす関数群 f1, ..., fN に一般化した Convex Hull Trick（by Li Chao Tree）を書いたけど、Line Container も一応書いておきたい。
直線の問題に対しては、Line Container の方がおそらく定数倍が軽い！！！
