atcoder.jp DPをしつつ、セグメント木で高速化する。 普段は配るDPで実装することが多いが、この問題では貰うDPで実装するほうが良さそう。 dpの更新は、セグメント木から前段のLからRの間の最大値を取得する。 セグメント木の更新は、dp[i]の値を一通り一気…

atcoder.jp 2、3回解いているが、なかなか覚えられないのでメモ。 マンハッタン距離が出たら、ひとまず45度回転を考えるのは覚えていた。 45度回転の方法は (X, Y) = (x-y, x+y) を計算すること。 45度回転すると、距離の領域が正方形になり、処理がしやすく…