解説を読んで実装した。FFTの練習。 問題概要 愚直DPを高速化してください 解法 DPの遷移の係数を求める式を見ると、DP列とある列との畳み込みになっている。FFTして一件落着！と行きたいところだが、DP[i]を求めないとDP[i+1]が求まらないので、オンライン…

問題概要 {1,2,...,N}^K の点を頂点とした K 次元超直方体を重ならないように M 個置く方法は何通りあるか。 解法 超直方体同士が重ならない どこかの次元でその超直方体が占める区間がdisjoint なので、1次元の場合に区間がどういう重なり方(M 区間のそれぞ…

見た目が解けるものに見えないが、実は解ける。見た目とのギャップがすごい。 問題概要 平面上にN点与えられるので、N点全てを一回ずつ使うサイクルを作って、隣り合う2点間のマンハッタン距離の総和を最大化せよ。 解法 x座標の中央値とy座標の中央値で切っ…