Segment Tree Beats(SGT Beats)の基本的なところの自分の理解をまとめておく。 今回は主に考え方や実装の説明メインで、Historic Informationや計算量解析周りの説明は含まない。(ここらへんも理解できて書けたら書く)

コンテスト中に解けなかった。だめだめだった。atcoder.jp 問題概要 個の整数が与えられ、番目の数はである。各数について赤、青、緑の3色で塗り分けることを考える。 そして塗り分けた個の数の中で、その色で塗られた整数の総和をそれぞれとする。全ての塗…

実際には少なく見積もれる計算量がなかなか慣れない。atcoder.jp 問題概要 人をいくつかのチームに分ける。 この時、番目の人は人以下のチームのみに所属できる。この条件の元、人のチーム分けとして何通り考えられるかをMOD で求めよ。 (ここでは、人は区別…

コンテスト中に解けなかった問題。思考力が足りなかった (終) 想定解法メモ。atcoder.jp 問題概要 個の黒いチョコレートと個の白いチョコレートがある。黒と白を等確率で選び、選んだ色のチョコレートが存在すれば食べる、をチョコレートがなくなるまで繰り…