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

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

DP高速化:いもす法

JOI 春合宿 2010 day1-3 Stairs (難易度 6)

区間分割していく DP を普通にやると になる (オレンジの出荷もそう)。それを累積和を用いて高速化する。 ジャッジページへのリンク 問題文へのリンク 問題概要 (意訳) 個の正の整数 が与えられる。これらをいくつかの連続した区間に分割していく。ただしど…

AtCoder AGC 046 C - Shift (黄色, 800 点)

こういう問題めっちゃ好き!!! 問題へのリンク editorial 問題概要 '0' と '1' のみからなる長さ の文字列が与えられる。以下の操作を 回以上 回以下まで行うことができる。 i < j であって S[ i ] = '0'、S[ j ] = '1' であるような (i, j) を選ぶ S[ j ]…

AtCoder ARC 104 D - Multiset Mean (黄色, 700 点)

すごく NTT したくなる 問題へのリンク 問題概要 正の整数 が与えられる。 をそれぞれ 個以上 個以下とってくる方法のうち、平均が となるものの個数を素数 で割ったあまりを、各 に対して求めよ。 制約 考えたこと まず、平均制約を次のように言い換える。…

AtCoder ABC 179 D - Leaping Tak (水色, 400 点)

DP 高速化系問題。こういうのが緑 diff になるようになったんかーー (水色 diff にアップグレードした!) 問題へのリンク 問題概要 マスからなるマス目が与えられる。また、 個の互いに disjoint な区間 が与えられる。この区間に属する整数からなる集合を …

yukicoder No.801 エレベーター

累積和による DP 高速化のすごく面白い問題! 問題へのリンク 問題概要 階建てのビルに 個のエレベーターがあり、 番目のエレベーターは区間 [ ] の間を動いており、区間内の任意のフロアから任意のフロアへと移動することができる (同じフロアへの移動もエ…