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