HHKB プログラミングコンテスト　総括

20位でした。賞品にはさすがに手が届かなそうだけど、やっぱり競技プログラミングは最高ですね〜〜〜〜〜！

A Keyboard

はい

B にしては難しくない？はい

C にしては難しくない？std::set で殴るとよいです

D にしては(ry $2(N-A+1)(N-B+1)(N-A-B+1)(N-A-B+2)-(N-A-B+1)^2(N-A-B+2)^2$

累積和して上下左右の障害物までの距離を数えて、あとは簡単な数え上げ

サンプル 2 とかで手計算を試みると、積分のにおいがぷんぷんする

まず最初に思いつく方法としては、区間と最大値をとる変数を決めて残りの変数の条件から積分たとえば、サンプル 2 なら

$$\int_1^2(x-1)xdx=\frac{5}{6}$$

で、これがふたつあるので $\frac{5}{3}$

ただ、これだと積分の数が $O(N^2)$ 個になって、明らかに爆発する

ここで、次に最大値だけを決める方針を考えてみる

最大値をうまく条件化することは難しそうだが、よく考えれば実は「すべての変数の値が $x$ 以下になる確率」を $x$ で微分してから $x$ をかけて積分してやれば、期待値が求められることがすぐわかる（それはそう）

もとの関数は $1$ 次式の積なので、これを頑張って（$\bmod 1000000007$ 畳み込みを要求するなの会結成）計算して、微分して $x$ をかけて積分すれば区間での期待値が求められるなお、愚直に計算しても全然間に合った

区間は高々 $O(N)$ 個に分ければよいので、これで $O(N^3)$ とか $O(N^2\log N)$ とかでこの問題が解けた

なお、求める答えには親切にも $\prod_{i=1}^N(R_i-L_i)$ がかかっているので、$1$ 次式を求める過程で確率に先にかけておくことで計算を省ける