Historic Informationまわりの勉強で解いた。解法メモ
問題概要
の番号がついたタンクがある。
番目のタンクには最初
mの高さの水が入っている。以下のクエリを合計
回処理せよ。
の各タンクの水の高さを
m上昇させる
- タンク
の現在の水の高さ(m)を出力
- タンク
Segment Tree Beatsの実装メモ (応用的な例題まわり)
前回の記事の続き
smijake3.hatenablog.com
コドフォのSegment Tree Beatsの説明の例題として挙がっているTask 3,4を実装したので、そのあたりの考え方含めて書いておく
続きを読むSegment Tree Beatsの実装メモ (基本まわり)
Segment Tree Beats(SGT Beats)の基本的なところの自分の理解をまとめておく。
今回は主に考え方や実装の説明メインで、Historic Informationや計算量解析周りの説明は含まない。(ここらへんも理解できて書けたら書く)
AtCoder: Tenka1 Programmer Contest 2019 - D問題: Three Colors
コンテスト中に解けなかった。だめだめだった。
問題概要
個の整数が与えられ、
番目の数は
である。
各数について赤、青、緑の3色で塗り分けることを考える。
そして塗り分けた個の数の中で、その色で塗られた整数の総和をそれぞれ
とする。
全ての塗り分け方の中で、辺の長さがとなる三角形が存在する塗り分け方は何通りあるかをmod 998244353で求めよ。
AtCoder: Mujin Programming Challenge 2018 - F問題: チーム分け
実際には少なく見積もれる計算量がなかなか慣れない。
問題概要
人をいくつかのチームに分ける。
この時、番目の人は
人以下のチームのみに所属できる。
この条件の元、人のチーム分けとして何通り考えられるかをMOD
で求めよ。
(ここでは、人は区別するがチームは区別しない)
AtCoder: エクサウィザーズ2019 - E問題: Black or White
コンテスト中に解けなかった問題。思考力が足りなかった (終)
想定解法メモ。
問題概要
個の黒いチョコレートと
個の白いチョコレートがある。
黒と白を等確率で選び、選んだ色のチョコレートが存在すれば食べる、をチョコレートがなくなるまで繰り返す。
各 について、
番目に食べるチョコレートが黒である確率をmod
で求めよ。
AtCoder: エクサウィザーズ2019 - D問題: Modulo Operations
これ解くのに1時間はかかりすぎた。反省回。
atcoder.jp
問題概要
個の整数からなる集合
と整数
が与えられる。
この集合に含まれる1つの整数
を取り除き、整数
を
mod
に書き換える。この操作を集合
が空になるまでの
回行う。
集合の整数を取り除く順序は
通り存在するが、全ての順序における最終的な整数
の値の総和を
で割った余りで求めよ。
