AtCoder425点
stack を使ってカッコ列判定をする問題の亜種! 問題へのリンク 問題概要 3 種類の文字 'A'、'B'、'C' からなる文字列 が与えられる。この文字列に対して、「左から見ていって "ABC" があったら消す」を何度も繰り返していって残る文字列を答えよ。 制約 考…
AtCoder
AtCoder425点
ABC-D
緑色diff
最適化テク:探索候補を絞る
数え上げ問題
標準形を考える
ソート:標準形を用いて考察する
平方数
順列の数え上げ
O(√N)まで考えれば十分
発想の転換が必要になる。与えられた数の順列を考えるのではなく、平方数の方を列挙していく。 問題へのリンク 問題概要 数字のみからなる長さ の文字列 が与えられる。 を並び替えて得られる文字列であって、平方数を表すものが何通りあるかを答えよ。 制約…
不変量
AtCoder
AtCoder425点
ABC-D
操作
操作:2つのものを1つにマージ
スライムやその合体をテーマとした問題
Greedy
シミュレーション
【問題集】シミュレーション
標準形を考える
Greedy:各要素について独立に考えてよい
Greedy:今が良いほど未来も良い
探索順序を工夫して解く
2^K
ビットを活用する
操作を好きな回数だけ行える
最小回数・最小個数を求める
pで何回割れるか
分けて解いてまとめる
緑色diff
最適化問題
素朴なシミュレーションが通るものの、それを正確に実装するのも結構大変 問題へのリンク 問題概要 種類のスライムがいる。 種類目のスライムは、サイズが であり、 体いる。 一般にサイズが であるスライムを 2 体合体させて、新たにサイズが のスライムを …
「要素の削除」をする必要がある場合は set が使えたりする 問題へのリンク 問題概要 最初、頂点数 、辺数 のグラフがある。 このグラフに対して次の 個のクエリに答えて、毎クエリ後にその時点での「グラフの孤立点の個数」を出力せよ。 クエリタイプ 1 (1 …