ARC116 参加記録 - Xenous の精進記録

1完13分でした。
B問題高速化できず。。 $O(N^{2})$ から落とすことができませんでした。

A - Odd vs Even

愚直に思いつくのは、各ケースでの整数 $N$ の約数を求め、個数を数え上げることですが、 $N \leq 10^{18}$ と大きく、列挙が間に合いません。
そこで、 $N$ の正の奇数の約数と正の偶数の約数に法則がないか試しにいくつか見てみると、次のようなことがわかります。

$N$ が奇数ならば、奇数の約数の方が多い
が偶数のとき、
- $N$ の約数で、偶数が $2$ だけならば、偶数と奇数の数は同じになる。
- 偶数が $2$ の他にもあるならば、偶数の方が多い

$N$ が奇数のときは、約数も奇数しか存在しません。
$N$ が偶数で、約数の中で偶数が $2$ だけの場合、 $N = (偶数) \times (奇数)$ の形に必ず分解できます。片方が偶数ならもう片方は奇数にならなければいけないので、偶数と奇数の数は同じになります。
$N$ が偶数で、複数の偶数の約数をもつ場合は、 $N = (偶数) \times (偶数)$ の形も作ることができるため、偶数が多くなります。

B - Products of Min-Max

$A$ の部分集合 $B$ の最大値と最小値を考えるにあたって、 $B$ は $A$ の要素の順番によらずとってこれるので、まずは $A$ をソートします。
最小値と最大値だけ考えれば良く、その間に入る値は使っても使わなくても良いことになります。

例として 2 3 5 6 8 という数列を考えてみます。
最小値を固定したとき、求める値は次のようになります。

最小値を 2 として最大値を動かすとき、間に入る値について含む/含まないの $2$ 通りが要素数分あるので、このとき、
$\min{(B)} \times \max{(B)}$ は $2 \times (2 + 3 \times 1 + 5 \times 2^{1} + 6 \times 2^{2} + 8 \times 2^{3})$ と書けます。

同じようにして

最小値 3: $3 \times (3 + 5 \times 1 + 6 \times 2^{1} + 8 \times 2^{2})$
最小値 5: $5 \times (5 + 6 \times 1 + 8 \times 2^{1})$
最小値 6: $6 \times (6 + 8 \times 1)$
最小値 8: $8 \times 8$

これを愚直に書くと正しい答えは出せますが、計算量が $O(N^{2})$ なので、TLE となります。最大値側の計算を高速に行う必要があります。

どうやるかですが、最小値を 8 側から動かしたとき、次の部分に注目します。

最小値 6: $8 \times 1$
最小値 5: $8 \times 2 + 6 = 2 \times 8 + 6$
最小値 3: $8 \times 2^{2} + 6 \times 2^{1} + 5 = 2 \times ( 2 \times 8 + 6) + 5$

後ろ側から漸化式で各値を求めることができます。 $f_n = 2 f_{n-1} + a_n$ という形です。
この形であれば、各最小値での計算を $O(1)$ で行うことができます。

N = int(input())
A = list(map(int, input().split()))
A.sort()

ans = A[-1]*A[-1]
ans %= MOD

# 後ろから作っていく
atmp = 0
for i in range(N-1, 0, -1):
    atmp = (2*atmp + A[i]) % MOD
    ans += (A[i-1]*atmp) % MOD
    ans += A[i-1] * A[i-1]
    ans %= MOD

print(ans)

C - Multiple Sequences

後日がんばります。。

D - I Wanna Win The Game

同じく後日ときます。。