日々drdrする人のメモ

今日も明日もdrdr

UOJ - #164: V

Historic Informationまわりの勉強で解いた。解法メモ

uoj.ac

問題概要

 1, 2, ..., Nの番号がついたタンクがある。

 i番目のタンクには最初 a_imの高さの水が入っている。以下のクエリを合計 M回処理せよ。

  1.  i \in [l, r] の各タンクの水の高さを xm上昇させる
  2.  i \in [l, r] の各タンクの水の高さを xm減少させる (高さは負にならない)
  3.  i \in [l, r] の各タンクの水の高さを xmにする
  4. タンク y の現在の水の高さ(m)を出力
  5. タンク y の過去最大の水の高さ(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

コンテスト中に解けなかった。だめだめだった。

atcoder.jp

問題概要

 {N}個の整数が与えられ、 {i}番目の数は {a_i}である。

各数について赤、青、緑の3色で塗り分けることを考える。
そして塗り分けた {N}個の数の中で、その色で塗られた整数の総和をそれぞれ {R, G, B}とする。

全ての塗り分け方の中で、辺の長さが {R, G, B}となる三角形が存在する塗り分け方は何通りあるかをmod 998244353で求めよ。

続きを読む

AtCoder: Mujin Programming Challenge 2018 - F問題: チーム分け

実際には少なく見積もれる計算量がなかなか慣れない。

atcoder.jp

問題概要

 {N}人をいくつかのチームに分ける。
この時、 {i}番目の人は {a_i}人以下のチームのみに所属できる。

この条件の元、 {N}人のチーム分けとして何通り考えられるかをMOD  {998244353}で求めよ。
(ここでは、人は区別するがチームは区別しない)

続きを読む

AtCoder: エクサウィザーズ2019 - E問題: Black or White

コンテスト中に解けなかった問題。思考力が足りなかった (終)
想定解法メモ。

atcoder.jp

問題概要

 {B}個の黒いチョコレートと {W}個の白いチョコレートがある。

黒と白を等確率で選び、選んだ色のチョコレートが存在すれば食べる、をチョコレートがなくなるまで繰り返す。

 {1 \le i \le B+W} について、 {i}番目に食べるチョコレートが黒である確率をmod  {10^9 + 7}で求めよ。

続きを読む