Segment Tree Beatsの実装メモ (基本まわり)

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

AtCoder: Tenka1 Programmer Contest 2019 - D問題: Three Colors

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

atcoder.jp

問題概要

個の整数が与えられ、番目の数はである。

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

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

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

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

atcoder.jp

問題概要

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

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

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

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

atcoder.jp

問題概要

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

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

各 について、番目に食べるチョコレートが黒である確率をmod で求めよ。

AtCoder: エクサウィザーズ2019 - D問題: Modulo Operations

これ解くのに1時間はかかりすぎた。反省回。
atcoder.jp

問題概要

個の整数からなる集合と整数が与えられる。

この集合に含まれる1つの整数を取り除き、整数を mod に書き換える。この操作を集合が空になるまでの回行う。

集合の整数を取り除く順序は通り存在するが、全ての順序における最終的な整数の値の総和をで割った余りで求めよ。

AtCoder Grand Contest 032 - D問題: Rotation Sort

コンテスト中に悩んで解けなかった。想定解法のメモ。
atcoder.jp

問題概要

の順列が与えられる。

この順列に対し、以下の操作を行える。

• あるを選び、を一つ左にシフトする
  • コストはかかる
• あるを選び、を一つ右にシフトする
  • コストはかかる

を昇順に並べるために必要な最小のコスト操作を求めよ。

AtCoder: 早稲田大学プログラミングコンテスト2019 - D問題: Choose Your Characters

コンテスト時間中に解いた。解法メモ。

atcoder.jp

問題概要

とあるアクションゲームにおいて、の番号が振られた種類のキャラがいる。
これらのキャラには、対戦する際の有利不利、もしくは五分の関係がある。
(キャラがキャラに対し有利である場合は、必ずキャラはキャラに不利)
この有利不利の関係は個与えられ、それ以外のキャラ同士の関係は五分となっている。

この時、以下を満たすような区間を選ぶことにした。

• 相手が任意のキャラを選んでも、そのキャラに対し五分もしくは有利になるキャラが1体以上存在する。(相手と同じキャラは除外して考える)

この区間の幅が最小となり、選べる同じ幅の中でもが最小となるを求めよ。