2021-01-01から1日間の記事一覧

N 個の整数 A_1,A_2,…,A_N が与えられ、N⋅(N−1)/2 個すべての非順序対 (Ai,Aj) (i<j) に対するf(A_i, A_j)の和を求める問題

ただしO(N^2)は間に合わないものとする。 基本的な攻略法 type0 明らかな場合 定数関数 f(x,y)=1 射影 f(x,y)=y type1 四則演算型 足し算 f(x,y)=x+y 引き算 f(x,y)=x-y 掛け算 f(x,y)=xy (ABC177-C) 割り算(有理数) f(x,y)=y/x 割り算(小数部分切り捨て) …