TopCoder Single Round Match 780

 Easyが通ってレートは微増。

Div1 Easy BeatTheStar

点数が1点もらえる試合～N点もらえる試合が一試合ずつあり、二人のうちどちらかにその得点が入る。G点の試合が勝負の分かれ目になる（つまり、その試合を勝てたら合計得点でも勝ち、負ければ合計得点でも負け）確率は？　という問題。

　余事象を考えると、G点の試合以外で、片方の点数が合計何点以下ならそういう状況にならないか、が分かる。なので、片方の点数がそれ以下になる場合をDPで求め、$2^{N-1}$で割って、1から引く。
　
　Python内fastestだったようなので、自分のコードはここで見ることができます。

Div1 Medium Prominence

コンテスト中は問題内容を把握できていなかった。kmjpさんのブログ記事で問題内容を把握しました。

　内容を把握できれば解法を理解するのはそんなに難しくないですね。

　kmjpさんの解法では前半パートにsetを使っていますが、公式解説を読むと平衡二分木は必要ない模様。左右から山を見ていけばできるのですね。
　後半パートもセグメント木ではなくSparse Tableを使えばO(N)になるのかな。（Pythonでは実行時間が厳しそうだし、実装はサボります。とはいえ、一応O(N)なので、上手く書けば通ってもおかしくはないですか）