Educational Codeforces Round 148 (Rated for Div. 2)

　D1までと思ったら、D1がhackされてしまった。

コンテストへのリンク

コンテスト後のツイート

Educational Codeforces Round 148 (Rated for Div. 2) D1まで。
B ソートして累積和。
C 増減が変わるところをチェック
D1 各クエリに対して、最後のn個かn-1個だけプラスで、他は二つペアにして-1として使うのが最適。答えを二分探索し、判定では、最初の数字から何個-1を使うか考えればOK。

— titia (@titia_til) May 12, 2023

D1. Red-Blue Operations (Easy Version)

　二分探索の下限を小さくしたらAC。

　答えが負になる場合があると気付いていなかった。たとえばn=1の場合を考えると分かりやすいけれど、値は大きくなったり小さくなったりを繰り返すので、負になることもある。二分探索するとき、上限・下限の見積もりは気を付けよう。

　（この方針ではD2は解けなそう）

E. Combinatorics Problem

　解説AC。

　k=1のときの配列Bは、累積和を使えば求められる。

　kを明示的に表すことにし、b[i]をb(i, k)と表すことにすると、二項係数の性質から、b(i, k) = b(i-1, k-1) + b(i-1, k)となる。これを使えば解ける。

・k=1のときは配列Bを求められそうなので、実験してみる

・kが5以下という制約を利用することを考えると、k-1からkの場合が求められそう

　みたいな流れで解くのが理想的だったのかな。まず実験すべきでした。