「最大値がK以下」⇔「すべてがK以下」
AtCoder
AtCoder400点
ABC-D
どの場所で初めてsmallerになるかを考える
辞書順
DP状態:smaller(桁DP)
Greedy
0と1の問題
ワイルドカード問題
考察:一部の変数を固定して考える
Greedy:ある量を決めると残りが決まっていく
緑色diff
Greedy:辞書順最小を求める
「最大値がK以下」⇔「すべてがK以下」
Yes/No判定問題
最大スコア
考察:操作・条件・目的関数を言い換える
制約条件:ある値<=K
DP状態:どの桁まで見たか(広義の桁DP)
最適化問題
基本的に Greedy にやればよさそうなのに、意外とやりづらい問題。基本に忠実にやれば解ける! 問題へのリンク 問題概要 文字 '0', '1', '?' のみからなる文字列 が与えられる。 中の各 '?' をそれぞれ '0' または '1' に置き換えて得られる文字列を二進法表…
AtCoder
AtCoder200点
ABC-B
累積和
数列
灰色diff
累積和の亜種
DP
データ構造テク:差分更新
累積max
考察:操作・条件・目的関数を言い換える
「最大値がK以下」⇔「すべてがK以下」
典型要素を詰め合わせた教育的問題
for文
for文:前回求めた値を活用する
建物の高さに関する問題
そのまま覚えたい易しい教育的典型問題
NoviSteps6Q
こういうのが素早くストレスなく書けるようになるといい感じな気がする 問題へのリンク 問題概要 海から順番に建物 があって、それぞれの高さは である。 海が見える建物が何個あるかを求めよ。なお、 番目の建物から海が見えるとは より前の 番目の建物より…