問題概要 2次元グリッドの格子点上に点がいくつかある。4点選んで軸に平行な長方形をつくり、内部に点がないようにしたい。面積の最大値を求める問題。 解法 長方形の2点の選び方を全探索する。内部に点があるかどうかは累積和を計算しておけばO(1)で判定で…

問題概要 重み付き無向グラフで2点間の最短路を求める。ただし最短路は4か7の倍数でなければならない。 解法 (ノード、今の時刻%28)を組にしてDijkstraする。

問題概要 パスカルの三角形を下っていくときの経路上の和の最大値を求める問題。 解法 DP。同じ問題がPOJなどいろんなところにある。