きままにものづくり

日々の気付いたことなんかを書いてます。

SRM601Div1Easy

問題

サイズNの2つの数列appleとorangeが与えられる。任意の数字xを選び、i番目のappleとorangeから合計x個を取り出す。これをNまで行う。この操作を行った時のappleの合計とorangeの合計の組み合わせの数を求めよ。

解法

appleとorangeの和の最小値Xを求め、1からXまでのそれぞれの組み合わせを求め合計する。xが定まった時の組み合わせの求め方は以下の式になる。
 min(mx, S) - max(S-mn, 0) + 1
ここで、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になる。

計算量

O(XN)
 X \leq 2*10^6
 N \leq 50

コード

広告を非表示にする