2020-12-26から1日間の記事一覧
Codeforces
CodeforcesR2600
CodeforcesDIV1-D
データ構造
クエリ処理問題
クエリ(グラフ上)
クエリ(木上)
Union-Find
undoつきUnion-Find
Union-Findのマージ過程を表す木を考える
部分永続Union-Find
クエリ:削除
Eulerツアー
セグメント木
色に関する問題
グラフ
クエリ先読み
後ろから解く
操作を逆順に見る
個人的要復習
いろんな方法がありそう。Union-Find のマージ過程を表す木でやったけど、ほかにも Undo 付き Union-Find を使うなど 問題へのリンク 問題概要 頂点数 、辺数 のグラフが与えられる。初期状態では各頂点に という値がついている (すべて 1 以上で disjoint)…
Codeforces
CodeforcesDIV1-B
CodeforcesR2000
構築
パズル
必要条件を列挙したら十分条件になる
Greedy:端から順に決まっていく
Greedy
数列
ギャグ要素高め
不変量
こどふぉ特有の 回以下の操作で〜を達成せよ、という問題 問題へのリンク 問題概要 長さ の正の整数からなる数列 が与えられる。以下の操作を 回以下繰り返すことで、数列の値がすべて等しくなるようにしたい。そのような操作列を一つ求めよ。不可能である場…
Codeforces
CodeforcesDIV1-C
CodeforcesR2000
再帰的に上位桁から順に値で分類した木を作る
Greedy:各要素について独立に考えてよい
各桁ごとに見る
転倒数
XOR
0と1の問題
Greedy
数列
バチャ中に TLE が取れなかった... で実装してしまっていたけど、 にする必要があったみたい。 問題へのリンク 問題概要 長さ の 0 以上の整数からなる数列 が与えられる。 0 以上の整数 を適切に定めて XOR で定まる数列 の転倒数が最小となるようにせよ。…