SRM601Div1Easy
問題
サイズNの2つの数列appleとorangeが与えられる。任意の数字xを選び、i番目のappleとorangeから合計x個を取り出す。これをNまで行う。この操作を行った時のappleの合計とorangeの合計の組み合わせの数を求めよ。
解法
appleとorangeの和の最小値Xを求め、1からXまでのそれぞれの組み合わせを求め合計する。xが定まった時の組み合わせの求め方は以下の式になる。
ここで、mxはxが定まった時のappleの合計とorangeの合計の大きい方を示し、mnは小さい方を示す。Sはx*Nを示す。具体例を用いて式を説明する。mx=7、mn=6、x=9の場合を考える。この時の組み合わせは、以下のようになる。
6 3
5 4
4 5
3 6
2 7
この時のパターン数を求めるためには、左側か右側の最小値と最大値を求める必要がある。上に示した式は右側の最小値と最大値を求めている。右側の最大値はSかmxとなり、最小値はS-mnか0になる。
計算量
