Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 272 C問題 Max Even

AtCoder ABC272 ABC C問題 300 pts

B# 問題 atcoder.jp

提出解答

問題の概要

$N$ 個の相異なる整数 $A_1, \dots, A_N$ がある.

この $N$ 個から $2$ 個を選び和を偶数にできるか? 可能ならばその和の最大値を求めよ.

制約

$2 \leq N \leq 10^9$
$0 \leq A_i \leq 10^9$

解法

2つの整数 $a,b$ において, $a+b$ が偶数であることと, $a,b$ の偶奇が一致することは必要十分である.

よって, 次の2パターンに場合分けし, 各小問題を解き, 最終的に結果を合わせれば良い.

$A_1, \dots, A_N$ にある相異なる2つの奇数を2つ選ぶことは可能か?. 可能ならばその和を最大化せよ.
$A_1, \dots, A_N$ にある相異なる2つの偶数を2つ選ぶことは可能か?. 可能ならばその和を最大化せよ.

奇数の場合について, 奇数が1つしか存在ない場合は不可能である. 奇数が2つ存在する場合は1番大きい奇数と2番目に大きい奇数を取り出せば明らかに最大値になる.

偶数についても同様である.

これにより解答を $O(N)$ 時間で求めることができる.

ちなみに, "不可能である" が答えになるのは $N=2$ のときだけである ( $N \geq 3$ の場合は奇数, 偶数のうち少なくとも一方が2個以上存在する).