AtCoder Beginner Contest 262 C問題 Min Max Pair
問題
提出解答
問題の概要
以上
以下の整数からなる長さ
の整数列
が与えられる.
以下を満たす整数の組 の個数を求めよ.
制約
解法
に対して,
を以下を満たす整数
の個数とする.
このとき, 最終解答は である.
の値で場合分けする.
の場合:
である. そして,
という条件と合わせることにより,
であることも導ける. 逆に,
であるような整数
は全て条件を満たす. 従って,
は
を満たす整数
のうち,
を満たす整数の個数である.
の場合: このとき,
である. 従って,
である. これから, 可能な
は高々
つであることがわかる. そして, これは
かつ,
と同値になる. よって,
は
ならば,
, そうでなければ
である.
ここで, となる整数
を
,
となる整数
を
とすると, 答えは
である. よって, 各 に対して,
であるかをみて, そうでなければ
かつ
を満たすかどうかを見れば良い. 計算量は
時間である.