Fを除く六完。500位以内だったのでレート減少は止まったかと思ったのだが、-5だった。悲しい。
コンテスト後のツイート
G n^2+n+X=sq^2とすると、n^2+n+X-sq^2=(n-k)(n+k+1)みたいな形に因数分解されなくてはダメ。整理すると、sq^2-X=k*(k+1)となるが、このsqとkの差は小さそう！（予想）→AC。
— titia (@titia_til) August 24, 2025
F - kirinuki
解説AC。
といっても、解説の詳細は理解できず、Cartesian Treeを使うことと前計算を行うことを理解し、あとは自分で考えた。
まず、最大長方形っぽいと思うところは良かったが、そこから、Cartesian Treeを使おうという発想に行かねばならなかった。すると、横の長さと縦の長さの範囲が決まったとき、その中にK以下の長方形は何個あるか？ という問題に帰着できる。
（横の長さ, 縦の長さ）が決まったとき、K以下の長方形が何個あるかは求められるので、それを前計算して累積和を取れば範囲に対しても対応できる。横の長さ*縦の長さに制約があるのがポイント。
整理すれば一つ一つのステップはそんなに難しくないのだが、実際に解くのは大変な問題だった。
とはいえ、一番重要なのは、最大長方形っぽいというところから、Cartesian Treeを使おうと発想する部分。ここは押さえておきたい。
0 件のコメント:
コメントを投稿