Educational Codeforces Round 69 (Rated for Div. 2)
コンテストページ
https://codeforces.com/contest/1197
✔A - DIY Wooden Ladder
2 番めに大きいものと、個数だけを見ればよいです。
✔ B - Pillars
大きい順に見て、ずっと連結ならよいです。 チェックリストで管理して、常にお隣がチェック済みであることを確認しましょう。
✔C - Array Splitting
切らない場合のスコアからの gain を計算です。 切った箇所の左右の差が gain ですから、これらを列挙して大きい順に K-1 個選べば良いです。
✔D - Yet Another Subarray Problem
[l,r[ に対するこの式は、m で割った余りが l のそれと等しいような添字のところだけ k 引いておいたものの range sum と等しいです。 ですから、あまりの方を全探索して、それにあうような l だけを見る形で走査をしましょう。
✖E - Culture Code
まにあいませんでしたが、とっても好きな問題でした。
マトリョーシカ (l,r) を r の昇順に見ていきます。
a, b: map<lint,lint> を、
- a.floor(x): 外側が x 以下のときの最大体積
- b.floor(x): 外側が x 以下で体積が a.floor(x) となるときの場合の数
となるように調整していきます。
はじめは、a[0]=0, b[0]=1 です。 case 1: a.floor(l) + (r-l) < a.floor(r) のとき マトリョーシカを入れてはいけません。 見なかったことにしましょう。 case 2: a.floor(l) + (r-l) = a.floor(r) のとき どちらでもよいです。 a は変わらないので触らなくてよいです。 b[r] = b.floor(l) + b.floor(r) です。 case 3: a.floor(l) + (r-l) > a.floor(r) のとき 入れましょう。 a[r] = a.floor(l) + (r-l) です。 b[r] = b.floorl() です。
空きの最小値は、x - a[x] の最小値です。 最も外側に来るマトリョーシカ (l,r) が L < r を満たしていることが、外側に置けない条件です。 この上で空きが最小値を取ればよいので、このような r を全探索して b[r] を足し合わせます。 同じ r をとるマトリョーシカが複数あっても 1 回カウントです。 なぜなら外側のサイズが違えば体積も違うはずなのですが、同じならば同じで b では束ねられているからです。
