AtCoder Regular Contest 116参加記（～C問題）

今回は面白い問題だらけです。あ、既出問題を見つけられるということはその問題の解法を理解しているということだから、そんなに気にすることではないと思います。
f:id:mmnkblog:20210329011049p:plain

A - Odd vs Even

完全既出だったらしい。こんなことがあっていいのか？

いったん制約を無視して愚直に解いてみる。正整数を素因数分解する場合、愚直に $\sqrt N$ まで割っていく方法で $O(\sqrt N)$ の計算量となる。約数を列挙する場合、各素因数ごとに何個選ぶかを考える。この時、 $N$ の素因数に $2$ が含まれていた場合、少なくとも $N$ の約数のうち半分は偶数である。

$N=18$ の例。
$\begin{array}{c|c|c|c} \times & 3^0 & 3^1 & 3^2 \\ \hline 2^0 & 1 & 3 & 9 \\ \hline 2^1 & 2 & 6 & 18 \end{array}$

さらに $N$ の因数に $4$ が含まれている場合、 $N$ の約数のうち半分以上が偶数となる。逆に、 $N$ の素因数に $2$ が含まれていない場合、 $N$ の約数が偶数となることはない。
よって、 $N$ を $2$ で割った余りと $4$ で割った余りを見ることで答えが求まる。今回は大丈夫だが、素因数の話題が出てきたときは $0$ や $1$ の扱いに注意し、必要なら場合分けして対処する。

計算量は、 $O(T)$ 。

B - Products of Min-Max

整数列 $A$ は順番を並べ替えても答えに影響しないので、昇順にソートする。こうすると、部分列 $B$ の最大値と最小値を決めたとき、その間にある各要素に関して $B$ に含めても含めなくても $\max (B) \times \min (B)$ の値は変わらない。 $B$ の最大値と最小値を全探索すると、計算量は $O(N^2\log N)$ となる。
さらに、最小値を固定したときの式を書き出して $\min (B)$ を括り出し、残った部分の式を他の最小値の場合と見比べると、その部分も効率的に更新できることがわかる。詳しい数式は公式解説に載っている。理解したいなら実際に式変形してみるのが早い。