コンテストページ
AtCoder Regular Contest 101 - AtCoder
解法
✔ D - Median of Medians（700 点）
答え X を二分探索です。中央値が X 以上である区間の個数が ceil(区間の総数 / 2) 以上である最大の X が答えです。
中央値が X 以上である区間を数えましょう。 各成分を X <= x ? 1 : -1 しておくと、総和が 0 以上の区間の数を数えればよいです。 分割統治です。真ん中を決めて、そこから両側への累積和を計算です。 左側を全探索です。左側が x だとすると、右側は -x 以上のものを数えればよく、これは累積和を取ってソートをして lower_bound でできます。
計算量は全部で Θ( N * ( log N )2 ) 、実行時間は1343 ms と、若干ギリギリなのですが、ログは 1 つにできたりしないのでしょうか（他力本願）
ところでこちらの問題は AC したことがあるようですし、当時の実行時間は 100 ms 前後です。もしかして：ながたかな退化ですか！？（泣）
✖ E - Ribbons on Tree（900 点）
解けませんでした。3 乗時間かかるお話をします。
根を決めます。各頂点 x に対して、その部分木内の部分的なペアリングであって、未解決な頂点の i 個ある場合の数計算します。すると、子のマージは多項式として、 となります。この計算は、次数の 3 乗（FFT をしても 2 乗ログ）だけかかります。悲しいですね。（実は FFTで 間に合うという説はありませんか？）（はい！？）
もしくは、問題文は包除の見た目をしていますが、集合の元の数だけでは決まりませんし、使える形ではなさそうに感じました。
✖ F - Robots and Exits（900 点）
ここまでたどり着けませんでした。
結果
102 位 2298 黄色パフォです。D が AC 済みだったことを考えると、冷えでしょうか。前 2 問が遅すぎたとは思わないのですが、後ろ 2 問どちらかは通したかったなという気持ちです。とはいえ F を読まないのは戦略として間違いではなかったと思っています。、順位表的に丘なのはわかっていたのですが、E も、全くわからなかったわけではありませんし、そもそも基本的に飛ばしていいことがある可能性は低いと思っています。
