操作:特定の文字を特定の文字に入れ替える
AtCoder
AGC-A
AtCoder500点
青色diff
不変量
最適化テク:自明な上界が最適解
操作
最小回数・最小個数を求める
クエリ処理問題
文字列
連続部分列を扱う問題
区間
0と1と2の問題
操作:区間
操作:特定の文字を特定の文字に入れ替える
数学的帰納法に基づく考察
数珠
中間値の定理
個人的要復習
最適化問題
ひたすらに迷走してしまった。今回の記事は解説というより、個人的備忘録として書く。 問題へのリンク 問題概要 一般に、'A' と 'B' と 'C' の 3 種類の文字からなる文字列 のスコアを次のように定める 文字列 に対して、以下の操作を繰り返し実施していく。…
AtCoder
AtCoder400点
緑色diff
ABC-D
Union-Find
最適化テク:自明な上界が最適解
必要条件を列挙したら十分条件になる
グラフ
回文
操作
条件の言い換え
最小回数・最小個数を求める
操作を好きな回数だけ行える
連結成分
操作:上書き
全域木を考える
最適化問題
操作:特定の文字を特定の文字に入れ替える
今や Union-Find やるだけだと茶色 diff (下手したら灰色 diff) だけど、ちゃんと考察要素を入れるとやっぱり緑色 diff になるのね。 問題へのリンク 問題概要 正の整数からなる整数列 が与えられる。以下の操作を好きなだけ行うことによって、 個の値がすべ…
Codeforces
格子点をmodごとに分類する
累積和
K飛ばしで累積和
0と1の問題
文字列
CodeforcesDIV1-A
CodeforcesR1500以下
マルチテストケース問題
入力が定数個
操作
操作:特定の文字を特定の文字に入れ替える
操作:1文字を変更する
操作:削除
Greedy:各要素について独立に考えてよい
累積和テク:累積和や累積結果を前処理しておく
累積和テク:条件を満たすものの個数を累積和で表す
個置きに累積和をとるの、3 ヶ月前の僕だったら思いつかなかったかもしれない。 問題へのリンク 問題概要 整数 が与えられる。また、長さ の 0 と 1 のみからなる文字列 が与えられる。文字列 に対して以下の操作を行うことができる。 文字列 中の文字 "0" …