2020-10-05から1日間の記事一覧

マンハッタン距離は45度回転させて考える(図示)X=x-y; Y=x+y

45度回転させる式は、X=x-y; Y=x+y (回転と同時にかかっている√2の倍率は無視します) 回転前のマンハッタン距離 = 回転後のチェビシェフ距離(座標の差の最大値) これで反時計回りに45度回転し、XY座標で2次元累積和を使うと解ける問題がある 例:ABC018 …