状態遷移していく部分列
JOI
JOI本選
JOI難易度6
二分探索
しゃくとり法
0と1と2の問題
非自明な線形時間
操作
最小コスト
ある量を固定して考える
lower_bound
「次の要素」へのポインタを求める
Greedy
AtCoder
状態遷移していく部分列
最初 DP とか考えたくなるやつ。落ち着くと見えてくる。 問題へのリンク 類題とか drken1215.hatenablog.com 問題概要 "J" と "O" と "I" のみからなる長さ の文字列 が与えられる。ところで、レベル の JOI 文字列とは、"JJ...JOO...OII...I" (それぞれ 個…
とても教育的な Greedy かもしれない! 問題へのリンク 問題概要 長さ の正の整数からなる数列 が与えられる。この数列からいくつかの値を取り除くことで、数列が となるようにしたい。 取り除くべき個数の最小値を求めよ。どのように取り除いても の形にで…
AtCoder
AtCoder400点
ABC-D
DP
数え上げ問題
禁止文字列
文字列問題
グラフ・盤面・数列の個数の数え上げ
ナップサックDP
状態遷移を意識するDP
水色diff
連続部分列を扱う問題
状態遷移していく部分列
こういうの素早く書けるようになるにはどうしたらいいんだろう... 問題へのリンク 問題概要 'A', 'G', 'C', 'T' のみからなる長さ の文字列のうち、「どの隣接した 2 文字を swap しても "AGC" を連続部分列として含まないもの」が何通りあるか求めよ。 制約…
DP
数え上げ問題
ナップサックDP
3つのものの真ん中に着目
累積和
ABC-D
AtCoder400点
AtCoder
状態遷移を意識するDP
ワイルドカード問題
文字列問題
青色diff
状態遷移していく部分列
これ好きなん!!! 400 点問題が問題分読んで 5 秒以内に方針立ったのは珍しいので、成長かもなん。 そして、DEGwer さんや chokudai さんが「DP は割とコーディングしながら細部詰めてる」と言っていたので、それを実践してみて、確かに良さそうかもなん。…