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

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

DP高速化:いもす法

AtCoder ARC 104 D - Multiset Mean (700 点)

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

AtCoder ABC 179 D - Leaping Tak (400 点)

DP 高速化系問題。こういうのが緑 diff になるようになったんかーー 問題へのリンク 問題概要 マスからなるマス目が与えられる。また、 個の互いに disjoint な区間 が与えられる。この区間に属する整数からなる集合を とする。 マス 1 からマス まで、次の…