これは安定感のある思考過程を経て解けた気がするので共有したい気持ち！！！ 問題へのリンク 問題概要 長さ の数列 が与えられる。各 は 以上 以下の整数値である。今、以下のような操作を何回でも行うことができる: となるような < を選んで、 と との間の…

区間についてどうのこうのする問題、大抵は DP！ 問題へのリンク 問題概要 個の整数 がある。これらのうちいくつか選んだ合計を最大化したい。ただし、 の区間 [ ] があって、選んだ数のどの 2 つをとっても同一区間上にならないようにしなければならない。 …

ひたすらバグってつらかった。。。DP 高速化系。セグ木を使ってもいいが、累積和だけで解ける。 問題へのリンク 問題概要 座標 地点から座標 地点へと移動する。 移動途中に 個のガソリンスタンドがあって、それらの座標は で与えられる。 燃料 の状態でスタ…

Convex Hull Trick の練習に。 問題へのリンク 問題概要 長さ の数列 が与えられる。数列を 個の区間に分割して、各区間 [, ] についての の総和を最小にせよ。 制約 解法 いかにも な DP になるのを頑張って高速化する系の問題。2 乗だから convex hull tri…

ふと考えてみた。区間 DP っぽく にはなるな...なんて思っていたけどそこから落とせなかった...いやこれ何を食べたらこんな二分探索思いつけるようになるの！？！？！？！？？？ なにかこういう場面で二分探索すると上手く行くよ、というパターン的なものが…

貪欲でも、実家 DP でも、ソシャゲ DP 的な DP でも解けるみたいなのんな。これ、実装がややこしくて、苦手なんて言葉ではいい表せないほどの超絶苦手系なのん。。。 Gerrymandering 問題へのリンク 問題概要 N 個の街が一直線上に並んでいて、各街は 2 種類…

バチャやりました！ vjudge.net バチャの中では 4 問中 3 番目の難易度。問題の構造自体はこの記事の最後の章で書いたような典型的な区間分割型のナップサック DP なのですが、条件がゴチャゴチャしていてややこしかったです。。。 類題として、RUPC の以下…

詰め切るの大変だった！ 問題へのリンク editorials 問題概要 '0'〜'9' からなる長さ の文字列 が与えられる。 これらの文字列をいくつかの連続する部分文字列に分ける。次の条件を満たす必要がある。 各部分文字列を数値とみなしたとき、strictly に単調増…