JOI難易度6
JOI
JOI本選
JOI難易度6
二分探索
しゃくとり法
0と1と2の問題
非自明な線形時間
操作
最小コスト
ある量を固定して考える
二分探索:lower_bound
「次の要素」へのポインタを求める
Greedy
AtCoder
indexベースで考える
解空間:O(N^2)通りの選択肢
区間
典型要素を詰め合わせた教育的問題
制約条件:各グループの何かが等しい
最適化問題
最初 DP とか考えたくなるやつ。落ち着くと見えてくる。 問題へのリンク 問題概要 "J" と "O" と "I" のみからなる長さ の文字列 が与えられる。ところで、レベル の JOI 文字列とは、"JJ...JOO...OII...I" (それぞれ 個ずつ) のことを指すものとする。 文字…
最適化テク:探索候補を絞る
差分更新
AOJ
JOI予選・二次予選
AtCoder
JOI
JOI難易度6
テク:区間ごとに分割する
気付き系
ジグザグ
操作:一斉に±aする
左右からそれぞれ走査する
これまたちょっと重たい。。。 問題へのリンク 問題概要 折れ線グラフが与えられる。これは に対して () を結んでいる。あらゆる水平な直線を考えたときの、折れ線グラフのうち直線の上に来ている部分を連結成分ごとに分解したとき、連結成分の個数として考…