問題概要 unsigned 64bit整数A,Bが与えられる。A=X+Y, B=X^Yを満たす非負整数X,Yのうち、Xが最小のものを求める問題。 解法(DP) 式変形して、A=(B^X)+Xなので、次の状態のDPで解いた。dp[i][Xのiビット目は0or1][Xのi-1ビット目は0or1][(B^X)+Xを計算したと…

問題概要 ２次元平面上にN( 解法 まず、線形性からX成分とY成分は完全に分離して考えてよいことが分かる。 S:=Σ{x[i]^2}, K:=Σ{x[i]}とすると、各jに対して、Σ_i{(x[j]-x[i])^2}=Σ_i{x[j]^2 + x[i]^2 - 2*x[j]*x[i]} = Σ_i{x[i]^2} + N*x[j]^2 - 2*x[j]*Σ_i{…

keyword 平面走査法 座標圧縮 C++ 問題概要 X軸に平行あるいは垂直な線分がS( 解法 まず座標圧縮する。その後は平面走査法でx座標の小さい方から舐めていく。計算量O(S^3)。