PalindromicSubstringsDiv2 と要領は同じ。Sのi番目からj番目までの部分文字列をS[i,j]と表記する。「S に含まれている回文の個数の期待値」＝「S の部分文字列の回文の個数の期待値」。期待値の線形性よりこれは「Sのそれぞれの部分文字列について回文にな…

愚直に全部分文字列が回文であるかどうかを判定すると \(O(N^3)\) になる。Sのi番目からj番目の範囲の部分文字列を S[i,j] とすると、S[i,j] が回文である条件は、S[i] == S[j] かつ S[i+1,j-1] が回文になることである。これを理由して動的計画法を適用する…

問題クラス名通り、Bounding Boxの面積を出せばよい。 public class BoundingBox { public int smallestArea(int[] X, int[] Y) { return (X.Max() - X.Min()) * (Y.Max() - Y.Min()); } }