2021-04-26

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

Aがわからない状態でウンコする最悪ムーブ
f:id:mmnkblog:20210322053311p:plain

A - Two Choices

この問題いつみても解けません。マジで苦手です。解説頑張って書こうとしたけど何もまとまりません。ごめんなさい。
愚直に解こうとすると $O(N^2)$ なので何かしらの工夫が必要というところはわかりました。逆に言うとそれ以外なにもわかってません。（ブログ公開が遅れたのもこの問題のせい）

AtCoderの公式YouTubeチャンネルにあがっているすぬけさんの解説がわかりやすかったですが、あの解説を文章で書けないです。解説目当てで来た人はこちらを見てください。
youtu.be

まずは判定問題を考える。
$A$ の各要素が定数だと仮定すると、行列 $C$ より $B$ も一意に定まる。これを言い換えれば、行列 $C$ の $i$ 行目の各要素から $A_i$ を引けば、すべての行は $B$ に一致するということである。つまり、もし解を構成できるならば、 $C_{i, j}$ から $C_{i, j+1}$ までの増分を $K_{i, j}$ として書き出すと、各行の増分は等しくなる（ $K_{i, j} = K_{i', j}$ ）。逆に、各行の増分が等しいなら、先ほどの議論より $A$ と $B$ が存在することが言える。ただしこのままだと負整数も要素に含まれているので、数列の最小値を引いて0以上にする必要がある。

計算量は、 $O(N^2)$ 。

C - ℕ Coloring

こういう、2つの要素間に条件が発生するような問題は、 $N$ 頂点の無向グラフを考えると良い性質が見えることがある。

$i$ 番目の頂点に整数 $i$ を書き込み、 $i$ が $j$ の約数なら頂点 $i$ と $j$ に辺を張る。このとき、問題文の条件は
「辺で結ばれた2頂点に異なる色を塗る必要があるときの、使用する色の数の最小化（とその色の塗り方）」
ということができる。これはグラフの彩色問題と呼ばれる有名な問題だが、NP困難（効率的に解くアルゴリズムが知られていないという意味のはず）の問題である。ということは、辺の貼られ方に特徴があるはずだ。

頂点 $1$ を最小の正整数である色 $1$ で塗ることとする。
頂点 $1$ は他の全ての頂点と隣接しているので、他の頂点が色 $1$ で塗られることはない。頂点 $2$ と頂点 $3$ は隣接していないので、それぞれの頂点を色 $2$ で塗る。この時、頂点 $2$ を除く $2$ の倍数の頂点は色 $1$ でも色 $2$ でも塗れないことがわかる。 $3$ の倍数に関しても同じ。 $2$ のべき乗の頂点だけ考えると、頂点 $4$ は色 $3$ で、頂点 $8$ は色 $4$ で、…という風に、指数の増加に比例して色の種類数も増えていく。
つまり、ある頂点 $n$ が $n=p^x\times q^y\times r^z\times \dots$ という風に素因数分解できるとき、頂点 $n$ の色は $\max(x, y, z, \dots) + 1$ であることがわかる。これを $N$ 以下の整数すべてに対して求めてやればよい。これは例えばエラトステネスの篩を用いた素因数分解などで $O(N\log N)$ で解くことができる。

感想

A問題よりB問題やC問題の方が簡単だと思います

2021-04-24

AtCoder Beginner Contest 199（Sponsored by Panasonic）参加記（～C問題）

競プロ解説参加記

早解きしかできなかった
f:id:mmnkblog:20210424224915p:plain

A - Square Inequality

こういう、一見そのまま解くだけに見える問題を素直に実装すると、たいてい何らかの罠にはまる。たとえば、

愚直に計算すると実行時間制限に間に合わない
計算途中でオーバーフローする
割り算や平方根の計算時に小数の誤差が発生する
コーナーケースが存在する（0除算など）

などが考えられる。今回は上記のどれにも当てはまらないので、単純に不等式評価を行うだけ。A問題なのでこれでACできる。
計算量は $O(1)$ 。

B - Intersection

解 $x$ の候補の最小値は $A_{\min}$ 、最大値は $B_{\max}$ であるので、解 $x$ を全探索して条件を満たすかどうか全探索してカウントする。
計算量は $O(N B_{\max})$ 。

ちなみに、別解が存在する。条件式より、解 $x$ の範囲は $A_{\max}\le x \le B_{\min}$ となる。逆に、この範囲にある整数 $x$ はすべて条件を満たすので、答えは $B_{\min} - A_{\max} + 1$ となる。
こちらの計算量は $O(N)$ で、はじめの解法より高速。

C - IPFL

これは、先ほど挙げた罠のうち、「愚直に計算すると実行時間制限に間に合わない」問題。というか競プロの問題の９割がこれである。
クエリの数が最大で $3\times 10^5$ 個あるため、各クエリに対して高速に回答する必要がある。
クエリ $1$ では、文字を交換するだけなので、計算量は $O(1)$ である。
クエリ $2$ では、長さ $N$ の文字列を交換するので、計算量は $O(N)$ である。
なので例えば、すべてのクエリがクエリ $2$ だった場合などを考えると、愚直な解法の計算量は $O(NQ)$ となってしまいTLEする。

ところで、クエリ $2$ を偶数回連続で処理すると元の文字列に戻る。連続で処理しなくても、クエリ $1$ で操作されなかった文字 $S_i$ に関しては、クエリ $2$ が偶数回処理されれば元の位置 $i$ に、奇数回処理されれば位置 $(i+N)\bmod {2N}$ に移動することがわかる。さらに、クエリ $2$ を奇数回処理したあとにクエリ $1$ を処理するのは、クエリ $2$ での反転を一度無視して、クエリ $1$ で与えられた値 $A, B$ に対して文字 $S_{(A+N)\bmod {2N}}, S_{(B+N)\bmod {2N}}$ を交換した後にクエリ $2$ を処理するのと同じである。
つまり、クエリ $2$ は最後に一度だけ処理すればよく、クエリ $1$ を処理する時点での「本来何回クエリ $2$ を処理しているか」がわかれば、全体として $O(N+Q)$ の計算量で全てのクエリを処理できる。

感想

Dが難しかった

2021-04-19

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

競プロ解説参加記

600点問題が解けると嬉しい！！
f:id:mmnkblog:20210418231705p:plain

A - God Sequence

各要素が正の整数である二つの数列 $a, b$ を考えることにする。この時、数列 $a$ の要素の総和と数列 $b$ の要素の総和が等しくなれば良い。 $A=B$ のとき明らかに、 $a_i = b_i$ とすることで条件を満たすことができる。

$A\lt B$ （数列 $a$ より数列 $b$ の方が長い）と仮定する。（逆ならswapする）
この時数列 $b$ の要素を $b_i = i$ となるように決めると、数列 $a$ の最後の要素を除いて $a_i = i$ とし、最後の要素を $a_A = \sum_{k=A}^{B} k$ とすることで条件を満たすことができる。最後の要素で数値を調整するイメージ。

計算量は $O(A+B)$ 。

B - ARC Wrecker

階数が同じビルがあった場合、どんな操作をしてもそれらのビルの階数は等しいままである。よって回数が同じビルはひとまとめにしておく。以降、すべての $A_i$ に重複が無いものとして考える。ついでに数列 $A$ を昇順に並び替えておく。

$X$ として選ぶ数字は数列 $A$ の要素のどれかとしてよい。また、 $X=A_i$ としたとき、少なくとも $A_i$ の値は $1$ 減るため、 $A_i$ は最大でも $A_i$ 回しか選べない。

実験するとわかるが、操作の順番は結果に関係しない。つまり「各 $i$ について、 $X=A_i$ を何回選ぶか」という情報だけわかればよい。さらに、 $X=A_i$ とした場合、 $i \le j$ を満たすすべての $j$ について、 $A_j$ の値は $1$ 減る。先ほど昇順にソートした理由はこれで、 $A_i$ が小さい順から「何回 $A_i$ を選ぶか」を決めていくことで数え上げることができる。

$X$ に $A_i$ を $k$ 回選ぶとすると、 $A_i$ と $A_{i+1}$ は共に $k$ ずつ減る。 $A_i$ の値が変わらないような $X$ に $A_{i+1}$ を選ぶ回数の最大値は、 $(A_{i+1} - k) - (A_i - k) + 1 = A_{i+1} - A_i + 1$ 回である。この数値は $k$ によらず一定である。
よって $(A_1 + 1)\times \prod_{ i = 1 }^{N-1} (A_{i+1} - A_i + 1)$ が答え。計算量はソートがボトルネックとなり、 $O(N\log N)$ 。

C - Tricolor Pyramid

文字を選ぶ操作をなにかの演算として表現したい。各文字を $0, 1, 2$ で置き換えて演算結果を表にまとめる。二つの数を $a, b$ としたとき、演算結果は $-(a+b)\bmod 3$ と表せる。

左から $i$ 番目の整数を $a_i$ とすると、最上段の整数に含まれる各 $a_i$ の個数は二項係数を用いて表せる。具体的に、最上段の整数は $(-1)^{N-1} \times \sum_{i=1}^{N} ({}_{N-1} \mathrm{ C }_i \times a_i) \bmod 3$ である。なので素直にこの式を計算すればよいが、 $\bmod 3$ 上の ${}_{N-1} \mathrm{ C }_i$ の値を求める方法がわからなかった。

http://www.junko-k.com/collo/collo29.htm
上のサイトを見ながら考えたところ、 $N-1$ を $3^k$ で割った余りで場合分けすることで $O(\log N)$ で求められることに気が付いた。なのでその場合分けを丁寧に書いて計算し解答。計算量は $O(N\log N)$ 。

ちなみにコンテスト後にTwitterを眺めていたところ、この方法は「Lucasの定理」という名前がついていて、 $3$ 進数での各桁の数字をもとにして計算するらしい。コンテスト中に定理を導出した自分すげえ！（素直）

感想

最強学生コンで失ったレートをほとんど取り返したので満足。

2021-04-18

第二回日本最強プログラマー学生選手権参加記（～E問題）

競プロ解説参加記

脳みそ、うごけー！（動かない）
f:id:mmnkblog:20210417182131p:plain

A - Competition

難しすぎないか…？最初に考えた方針が「両方の肉を同じだけ買ったときの金額で考える」ものだったが上手くいかず、一度B問題を解きに行って戻ってきた。スーパー高橋で売っている肉の $1$ gあたりの価格は $Y\div X$ で求められる。同様に、スーパーすぬけで売っている肉の $1$ gあたりの価格は（解である $Z$ g当たりの価格を $A$ とすると） $A\div Z$ で求められる。この二つの式の大小関係を式で表すと、
$\dfrac{Y}{X} \gt \dfrac{A}{Z}$
となる。さらに式変形して、
$\dfrac{YZ}{X} \gt A$
となる。この式の左辺は定数なので、 $A$ は一通りに定まる。割り算の扱いに注意。計算量は、 $O(1)$ 。

B - Xor of Sequences

制約より、数列 $A, B$ に含まれる整数の範囲は $1$ 以上 $1000$ 以下である。この範囲に含まれる整数が解の条件を満たすかを全探索する。
数列に同じ整数が重複することはないという制約があるため、整数を $x$ とすると、数列 $A, B$ に含まれる $x$ の個数がちょうど $1$ 個なら条件を満たしているといえる。（ちなみにこの処理を、整数 $x$ を見つけるたびに真理値型のフラグに対してtrueとのXORを取るという処理に変えると、最終的なフラグの値がそのまま解となる。）
これを $1000$ 回繰り返す。計算量は、 $O(N A_{\max})$ 。

C - Max GCD 2

ユークリッドの互除法での2数の関係から考えてみるとわかりやすい。
整数 $x, y$ の最大公約数が $d$ であるとき、 $x, y$ はともに $d$ の倍数である。 $A$ 以上 $B$ 以下の区間内に $d$ の倍数が $2$ 個以上存在すれば、 $x$ と $y$ の最大公約数が $d$ となるような $(x, y)$ を選ぶことができる。これは、「 $A$ 以上の整数のうち $d$ の倍数の最小値」に $d$ を加えた値が $B$ 以下かどうかを判定すればよい。
$d$ として考えられる値の最小値は $1$ 、最大値は $\dfrac{B}{2}$ であるので、制約よりこれらの間にある整数を全探索しても間に合う。計算量は、 $O(B)$ 。

D - Nowhere P

これ以降の問題は解けていない。
何か簡単な数式で解を表現できるらしいが、そこまで至らなかった。
コンテスト中の方針としては、「とても良い列」ではない列のほうをカウントして全体から引く作戦で考えていたが、数列を重複して数えてしまう沼にハマって抜け出せなかった。

E - Level K Palindrome

レベル $K$ の回文として考えられる文字列の長さの最小値を考える。最小の長さを持つレベル $K$ の回文は、レベル $1$ の回文aを、間に何も挟まずに組み合わせていくことで作れる。この時の長さは、 $2^{K-1}$ である。よって、高橋君が持っている文字列の長さを $N$ とすると、 $N \ge 2^{K-1}$ を満たしている必要がある。ついでにいうと $K$ が $19$ 以上だと確実にimpossibleである。
さらに、レベル $K$ の回文を2つのレベル $K-1$ の回文に分解するとき、 $N$ が偶数なら2分割、 $N$ が奇数なら間に一文字挟んで2分割、となるしかないので、その文字列を構成するレベル $k$ （ $0\le k \le K$ ）の回文の長さは一意に定まる。レベル $0$ の回文の長さも決まるが、このときどの文字を変えるのが最適なのかがよくわからなかった。レベル $0$ の回文は回文であってはいけないという制約が邪魔だった。

感想

レートが50下がって気分も下がったが初めてお酒を飲んで全部忘れたのでOK

2021-04-12

AtCoder Beginner Contest 198参加記（～E問題）

競プロ解説参加記

コーナーケースに気を付けろ！！
　　　　　
f:id:mmnkblog:20210411231102p:plain

A - Div

A君が得るお菓子の個数を $A$ 個、B君が得るお菓子の個数を $B$ 個とすると、 $B=N-A$ という等式が成り立つ。この式から、 $A$ を固定すると $B$ は $1$ 通りに定まること、 $A, B$ がともに正の整数でなければならないことを考えると、 $A$ が取りうる範囲 $1\le A\le N-1$ の中にある整数の個数、つまり $N-1$ が答えとなる。計算量は、 $O(1)$ 。

ちなみに制約がゆるいので、brainfuckでも簡単なif文の処理が書ければ解ける。

B - Palindrome with leading zeros

問題文中の操作は、「 $N$ を文字列としてみたときの末尾から連続している0をすべて削除する」と言い換えられる。こうすることで、操作後の文字列 $N'$ が回文かどうかを一度判定するだけで答えが求まる。 $N=0$ のときの処理に注意。計算量は $O(\log N)$ 。

C - Compass Walking

$2$ 歩歩くことで、ユークリッド距離が $2R$ 以内の点に移動することができる。また、 $x$ 歩以下で到達できる範囲は、原点から距離が $xR$ 以内の範囲である。このことから、解 $x$ を二分探索して求めることができる。
ただし、 $1$ 歩歩くことで到達できるのは原点からちょうど $R$ 離れている点だけであるので、二分探索して得られた解が $x=1$ だった場合にのみ、原点からの距離で場合分けする。

二分探索について。ルートを使うと小数誤差にやられる危険性があるので、整数のまま計算する。具体的には、距離の大小さえわかればよく、距離は負の値を取らないので、距離の2乗をそのまま比較する。式は以下の通り。

$X^2 + Y^2 \le x^2 R^2$

また、解の最大値は $2\times 10^5$ 程度と見積もれるが、距離の2乗で比較する方針だと上式の右辺が最大で $4\times10^{20}$ となりオーバーフローするので、二分探索するときの解の最大値は $2\times 10^5\div r$ とした。こうすると右辺は単に $x^2$ となる。計算量は $O(\log (X+Y))$ 。

コンテスト中はこれで十分だが、より厳密に議論すれば二分探索を用いなくても $O(1)$ で答えを求めることができる（公式解説より）。考察をサボれるときはサボることも大事。

D - Send More Money

条件がごちゃごちゃ書いてあるが、普通に覆面算を解くだけの問題。各英小文字に一桁の整数を割り当てるので、文字の種類数が $11$ 以上ある場合は解なし。

文字の種類数が $10$ 以下だった場合、各文字に整数を割り当てる方法を全通り試す。文字の種類数を $a$ とすると、 ${}_10 \mathrm{ P }_a$ 通り試せばよいことになる。C++のnext_permutation関数に長さ10の順列を与えてループを回し、順列の先頭 $a$ 個だけをみて実際に文字に割り当て、 $N_1 + N_2 = N_3$ が成立するか確かめる。計算量は $O(N!)$ 。

E - Unique Color

与えられるグラフは木であるので、 $2$ 頂点間を結ぶパスは必ず $1$ つだけ存在する。もちろんそのパスが最短である。また、木の頂点 $1$ から頂点 $x$ までのパス上に頂点 $y$ が含まれていた場合、そのパスに頂点 $1$ から頂点 $y$ までのパスが完全に含まれている。

以上のことより、頂点 $1$ からDFSをして「よい頂点」でない頂点を探すこととする。具体的には、DFSをしながら通った頂点の色をメモしていき、頂点 $x$ の色がすでに登場しているなら答えから外す、ということをしていけばよい。

メモするための道具として集合（set、挿入・削除がともに $O(\log N)$ ）を用いたがTLEしてしまった。setのかわりにunordered_setを使ってみたが変わらず。しかもこの方法はメモリも大量に使うため非常に重い。
もう少し考えると、DFSで戻ってくるとき「どのタイミングで色 $c$ が使われなくなったか」は「どのタイミングで初めて色 $c$ が使われたか」の解と等しいため、setを使わず、bool配列で管理することができる。
計算量は、 $O(N)$ 。

F - Cube

むずすぎ

感想

青パフォだったのでうれしいけど、Eでの2ペナがもったいないと思った

2021-04-08

キャディプログラミングコンテスト2021(AtCoder Beginner Contest 193)解法メモ（全問題）

競プロ解説参加記

タイトルが長すぎる

リアルタイムで参加できなかったコンテストのブログが抜けてて気になったので、暇なときに解き直してブログを書くことにしました。

A - Discount

算数。割合の計算は比を使った式で書くとわかりやすいと個人的に思う。
$A:100 = B:x$
と考えてもいいし、
$A:B = 100:x$
と考えてもいい。どちらにせよ
$x = \dfrac{100B}{A}$
という式になる。比を使った式の好きなところはこういうところ。

何パーセント引きか聞かれているので、 $100 - \dfrac{100B}{A}$ が答え。計算量は $O(1)$ 。

B - Play Snuke

1軒しかお店が無いとする。このとき、 $A$ 分かけてお店に着いた時、スヌケマシンの在庫は $\max (X-A, 0)$ である。在庫が $1$ 以上のとき、つまり $X-A$ が $1$ 以上のときに限り $P$ 円でスヌケマシンを買うことができる。

お店が $N$ 軒に増えた場合でも各店舗での購入条件と購入金額はかわらない。また、どのお店を選んでも、その選択が影響することはないので、スヌケマシンを買うことができるお店のうち一番安く買えるお店での購入金額を求めればよい。計算量は $O(N)$ 。

C - Unexpressed

事象 $A$ とその余事象 $A^c$ の和は全事象 $\Omega$ である。
「 $a^b$ と表せないもの」＝「全体」 $-$ 「 $a^b$ と表せるもの」
なので、「 $a^b$ と表せるもの」の個数をカウントする。

「 $a^b$ と表せるもの」の個数を上から評価する（最大値を見積もる）。
$a$ を固定したとき、 $b$ を増やすと $a^b$ も増加する。よって、 $1 \le a^b \le N$ を満たす $b$ の個数は $b = \log_a N$ である。
$2 \le b$ に注意すると、 $a$ は最大で $\sqrt N$ 程度まで大きくなるので、全体の個数としては $\sqrt N \times \log_2 N$ 程度となる。（上から評価しているので、 $a=2$ として計算した。）
この値は $N=10^5$ のときでもおよそ $1.6 \times 10^6$ であるため、 $(a, b)$ の組を全探索しても実行時間制限に間に合うことがわかった。

カウントするときは重複やオーバーフローに注意して実装する。重複を避けるにはC++のsetなどを用いる。 $a=\lfloor N \rfloor$ で探索を打ち切る処理を忘れるとTLEするので注意。計算量は $O(\sqrt N \log N)$ 。

D - Poker

かなり考えることが多いので順を追って考察する。

まず、「高橋君の勝つ確率」は $\dfrac{高橋君が勝つパターンの数}{全てのパターンの数}$ で求められる。ここで言う「すべてのパターン」とは、すでに表向きになっていて裏向きのカードとして選ばれることのない $8$ 枚を除いた $9K-8$ 枚から $2$ 枚（高橋君の裏向きのカード $1$ 枚と青木君の裏向きのカード $1$ 枚）を選ぶ方法を指す。よって分母は ${}_{9K-8} \mathrm{ C }_2$ となる。

高橋君に配られた裏向きのカードを $x$ 、青木君に配られた裏向きのカードを $y$ と置く。高橋君が勝つパターンの数をカウントしたい。裏向きのカードが何の数かわかれば手札の点数を求めることができるが、ここで $9K-8$ 枚の中から $2$ 枚選ぶような全探索をすると $O(K^2)$ の計算量となってしまうので実行時間制限に間に合わない。しかし、 $(x, y)$ の組み合わせとしては $81$ 通りしかないので、 $x$ と $y$ を決めたとき $(x, y)$ が選ばれるのは何通りか求められれば、高橋君が勝つパターンの数も高速に求められる。

整数 $i$ が書かれたカードの残り枚数を $C_i$ とする。 $x=y$ なら、 $C_x$ 枚の中から $2$ 枚選ぶので ${}_{C_x} \mathrm{C}_2 = C_x(C_x - 1)$ 通りである。 $x\neq y$ なら、 $C_x$ 枚の中から $1$ 枚、 $C_y$ 枚の中から $1$ 枚それぞれ選ぶので $C_xC_y$ 通りである。高橋君の手札の点数が青木君の手札の点数より高い場合にこの通り数をそのままカウントに加えることで、確率を求めることができる。

計算量は、手札の枚数を $N$ 、カードに書かれた整数の種類数を $C$ として $O(N+C^3)$ 。この問題では $N=5, C=9$ であるため十分高速に動作する。

E - Oversleeping

電車の停止する区間は周期的に訪れ、 $\bmod (2X+2Y)$ 上で一定である。高橋君の起きる区間も同様に、 $\bmod (P+Q)$ 上で一定である。
ここで、中国剰余定理（CRT）を活用する。この定理は、
「 $a$ で割ると $p$ 余り、 $b$ で割ると $q$ 余る整数 $x$ は $\bmod (\mathrm{lcm}(a, b))$ 上にちょうど1つだけ存在する」
ということを言っている。さらに、この解となる整数 $x$ を構成する効率的なアルゴリズムが知られていて、 $O(\log(a+b+p+q))$ で動作する。実装には拡張ユークリッドの互除法を用いることが多いが、atcoder libraryに実装されているcrtをそのまま用いることもできる。

制約より、 $Y$ と $Q$ が小さいことがわかる。よって、電車が停止してから $i$ 秒後のタイミングと、高橋君が起きてから $j$ 秒後のタイミングが初めて一致するときがいくつか求め、 $(i, j)$ の組を全探索して最小値を求めればよい。具体的には、以下の2つの合同式を同時に満たす解 $x$ の最小値を、 $0\le i\lt Y, 0\le j\lt Q$ の範囲で全探索する。

$x \equiv X+i \pmod{2X+2Y}$
$x \equiv P+i \pmod{P+Q}$

計算量は、 $O(YQ\log(X+Y+P+Q))$ 。

F - Zebraness

まだ解けていないが、工夫することでフローの問題に帰着できるらしい。

感想

はじめてCRTを学んだが、そこまで難しくなくて食わず嫌いしていたなーと思った。ちなみにCRTは条件式が3本以上あっても解を求めることができる。

2021-03-29

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)$ を括り出し、残った部分の式を他の最小値の場合と見比べると、その部分も効率的に更新できることがわかる。詳しい数式は公式解説に載っている。理解したいなら実際に式変形してみるのが早い。