けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

区間分割型ナップサックDP

diverta 2019_2 E - Balanced Piles (800 点)

最初は絶望感がヤバイタイプの問題。とても解ける問題には見えない。でも落ち着くと解ける。 こういう問題を作れるのはすごい。 問題へのリンク 問題概要 個のマスに積み木を重ねていく。最初はどのマスも 0 段である。以下の操作を繰り返して、最終的にすべ…

AtCoder AGC 007 D - Shik and Game (1200 点)

すごく典型的な問題。 現代なら企業コンの 800 点問題とかに出そうな雰囲気だね。このころはまだあまり典型じゃなかったのかな。 問題へのリンク 問題概要 一直線上に 個の点 があってこの順に並んでいる。さらに左側に 、右側に がある。 からスタートする …

AtCoder AGC 002 F - Leftmost Ball (1600 点)

すごく楽しかった。 問題へのリンク 問題概要 色 のボールがそれぞれ 個ずつあります。 個のボールを好きな順序で並べ、各色について最も左側にあるボールを色 へと塗り替えました。 最終的な色の並びとして考えられる個数を 1000000007 で割ったあまりを求…

diverta 2019 E - XOR Partitioning (800 点)

時間かかりすぎた。シンプルで面白い。 問題へのリンク 問題概要 要素からなる 0 以上の整数列 が与えられる。 これをいくつかの連続した部分列に分割する 通りの方法のうち、各連続区間の XOR 和が互いに等しくなるものが何通りあるか、1000000007 で割った…

Codeforces 552 DIV3 F. Shovels Shop (R2300)

問題概要 個の品物があって、それぞれ価格は である。ここから 個の品物を何回かに買いたい。ここで一回の買い物につき一回ずつ使えるクーポン券が 個あって (使わなくても良い)、各クーポンは ちょうど 個の品物を買ったならば、そのうちの安い順に 個の品…

AtCoder AGC 031 B - Reversi (700 点)

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

AOJ 0656 イルミネーション (JOI 2019 予選 E)

区間に対してどうこうする DP 苦手意識ある。。。 区間スケジューリング問題に近い感じ。 問題へのリンク 問題概要 個の整数 がある。これらのうちいくつか選んだ合計を最大化したい。ただし、 の区間 [ ] があって、選んだ数のどの 2 つをとっても同一区間…

CODE FESTIVAL 2018 qual A D - 通勤 (700 点)

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

CS Academy 070 DIV1 E - Squared Ends

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

AtCoder AGC 026 F - Manju Game (2000 点)

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

CS Academy 081 DIV2 D - Gerrymandering

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

2016 Benelux Algorithm Programming Contest D - Bridge Automation (AtCoder 600 点くらい)

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