AtCoder Beginner Contest 393 E,F問題メモ

AtCoder Beginner Contest 393

帰省中のため慣れない環境でやってたら凡ミス連発してしまった。イレギュラー対応力が弱すぎる。

E - GCD of Subset

• 長さ $N$ の数列 $A=(A_1,A_2,\dots,A_N)$ と $N$ 以下の正整数 $K$ が与えられます。
• $i=1,2,\dots,N$ について次の問題を解いてください。
  • $A_i$ を含むように $K$ 個の要素を $A$ から選ぶ時、それらの最大公約数 (GCD) としてあり得る最大値を求めてください。

• $1 \leq K \leq N \leq 1.2 \times 10^6$
• $1 \leq A_i \leq 10^6$
• 入力される値は全て整数

まず、以下のような解法が思いつく。

• ①配列 $C=(C_1,C_2,...,C_{1000000})=(0,0,...,0)$ で初期化する。
• ②各 $A_i$ について、以下を処理する。
  • 約数を求める。全ての約数の集合を $D$ とする。
  • 各 $j \in D$に対し、$C_j+=1$ する。
• ③各 $A_i$ について、以下を処理する。
  • $j \in D$ のうち、$C_j \ge K$ となる最大の $j$ が、$A_i$ に対する答え。

この解法の最悪計算量は、$V(x)$ を $x$ 以下の数が持つ約数の個数の最大値として、少なくとも $NV(A_{\max})$ かかる。

だが、今回の制約では $V(10^6)=240$ なので、$N$ とあわせて $2.88 \times 10^8$ などとなり、厳しい。

TLE解法から以下の2つの高速化をおこなうことで、高速な言語ならACできる。

• (a) 約数列挙を高速なものにする（SPF）
• (b) 同じ $A_i$ はまとめて処理する。

(a) 正整数 $X$ の約数列挙は、試し割りでは $O(\sqrt{X})$ かかるが、より高速に行う方法がある。

• 素因数分解, 約数の種類数, 高速版 osa_k ～高速な素因数分解～ - perogram

事前計算 $O(A_{\max}\log{A_{\max}})$ かけることで、正整数 $X \le A_{\max}$ の約数列挙を $O(d(X))$ でおこなえる。
ただし $d(X)$ は $X$ の約数の個数。
$A_{\max}$ が大きくなく、素因数分解や約数列挙を何回もおこなう必要があるときに使える。

(b) 約数の個数が大きい $A_i$ の値は限られるので、同じ値はまとめて処理することで、1つあたりの平均計算量は抑えられる。
$1～10^6$ の約数の個数の総和は約 $1.4 \times 10^7$。
TLE解法の②③が、いずれもこのオーダーで処理できるようになるため、ざっくり $10^7$ の3～4倍?くらいの計算が可能な言語なら間に合うと見積もれる。

倍数関係・約数関係の高速ゼータ変換を使う。
この手法の名称は記事によって様々で決まったものはないが、「素数ゼータ変換」や「約数ゼータ変換」などと呼ばれている。

• ゼータ変換・素数ゼータ変換について - HackMD
• Zeta transform / Moebius transform （約数包除） | cplib-cpp

累積和を取る方向が逆なだけで、実装はとてもよく似ている。
これらの変換を使うと、以下のように答えを求められる。

• 配列 $C=(C_1,C_2,...,C_{1000000})=(0,0,...,0)$ で初期化する。
• 各 $i$ に対し、（約数全てではなく）$A_i$ そのものの箇所のみ1加算する。 $C_{A_i}+=1$
• $C$ に倍数関係のゼータ変換を施す。

これで、TLE解法の②の結果に相当するものが $O(N + A_{\max}\log\log{A_{\max}})$ で求まる。
さらに、

• 各 $C_i$ を、$K$ 以上であるものは $i$ に、それ以外は $0$ に置き換えた数列を $D$ とする。
  • 例) $K=3,C=(6,4,1,3,0,1,2,3,...)$ → $D=(1,2,0,4,0,0,0,8,...)$
• $D$ に約数関係のゼータ変換を施す。ただし「和」ではなく「max」版でおこなう。
  • つまり、変換後の $D_{12}$ は、変換前の $\max(D_1,D_2,D_3,D_4,D_6,D_{12})$ となる。
  • 加算をchmaxに置き換えるだけで正しく求まる。

すると、各 $D_i$ は「$i$ の約数のうち『$A$ の中に自身の倍数が $K$ 個以上ある』中で最大の数」を意味する値となり、これがまさに問題に対する答えとなる。

例) A=(3,4,6,7,12)  K=2

i         1  2  3  4  5  6  7  8  9 10 11 12
C変換前   0  0  1  1  0  1  1  0  0  0  0  1    各Aiに+1
C変換後   5  3  3  2  0  2  1  0  0  0  0  1    各iに対し、倍数関係にある箇所の値の総和をとる
D変換前   1  2  3  4  0  6  0  0  0  0  0  0    K=2 以上の箇所をindexに、他を0にする
D変換後   1  2  3  4  1  6  1  4  3  2  1  6    各iに対し、約数関係にある箇所の値のMAXをとる
求解            ^  ^     ^  ^              ^    Aの各値をindexとするD変換後の値が答え

Python3

def get_primes(n):
    """ nまでの素数リスト """
    candidates = [0, 1] * (n // 2 + 1)
    if n % 2 == 0:
        candidates.pop()
    candidates[1] = 0
    candidates[2] = 1
    for p in range(3, int(n ** 0.5) + 1, 2):
        if candidates[p]:
            for m in range(p * p, n + 1, 2 * p):
                candidates[m] = 0
    return [p for p, b in enumerate(candidates) if b]


def multiple_zeta(aaa, primes):
    n = len(aaa) - 1
    for p in primes:
        if p >= n:
            break
        for j in range(n // p, 0, -1):
            aaa[j] += aaa[j * p]
    return aaa


def divisor_zeta_max(aaa, primes):
    n = len(aaa) - 1
    for p in primes:
        if p >= n:
            break
        for j in range(1, n // p + 1):
            aaa[j * p] = max(aaa[j * p], aaa[j])
    return aaa


def solve(n, k, aaa):
    primes = get_primes(1_000_000)
    bbb = [0] * 1_000_001
    for a in aaa:
        bbb[a] += 1
    bbb = multiple_zeta(bbb, primes)

    ccc = [i if bbb[i] >= k else 0 for i in range(1_000_001)]
    ccc = divisor_zeta_max(ccc, primes)

    ans = []
    for a in aaa:
        ans.append(ccc[a])
    return ans


n, k = map(int, input().split())
aaa = list(map(int, input().split()))
ans = solve(n, k, aaa)
print('\n'.join(map(str, ans)))

F - Prefix LIS Query

• 長さ $N$ の整数列 $A=(A_1,A_2,\dots,A_N)$ が与えられます。
• $Q$ 個のクエリを処理してください。$i\ (1\leq i\leq Q)$ 番目のクエリは以下の通りです：
  • 整数 $R_i,X_i$ が与えられる。
  • 数列 $(A_1,A_2,\dots,A_{R_i})$ の（連続とは限らない）部分列であって、狭義単調増加であり、かつ全ての要素が $X_i$ 以下であるようなものの長さの最大値を求めよ。
  • なお、$X_i \geq \min\lbrace A_1, A_2,\dots,A_{R_i} \rbrace$ が保証される。

• $1\leq N,Q \leq 2\times 10^5$
• $1\leq A_i \leq 10^9$
• $1\leq R_i\leq N$
• $\min\lbrace A_1, A_2,\dots,A_{R_i} \rbrace\leq X_i\leq 10^9$
• 入力は全て整数

最長増加部分列（LIS）を求めるDPは有名だが、そのやっている内容の意味を考えればこの問題の解法も自然に導ける。

よくあるLISのDPは以下の通り。

• $\mathrm{DP}[i,j]:=(A_1,...,A_i)$ から長さ $j$ のLISを作るにあたって、末尾要素が取り得る最小値

• 83. 最長増加部分列（LIS）の長さを算出するアルゴリズムを丁寧に見る - イバコの生存記録

実際の実装では $i$ の次元は省略し、$j$ を添字とする1次元配列を破壊的に更新していく。
この1次元配列を $L$ とする。各時点の $L$ は狭義単調増加となっている。

クエリを先読みしておいて、$i=R_q$ までLISのDPを処理したタイミングでクエリ $q$ に答える。

その時点の $L$ 上を二分探索し、$L[j] \le X_q$ である最大の $j$ を探せば答えとなる。

計算量は $O((N+Q)\log{N})$

Python3

from bisect import bisect_left, bisect


def solve(n, q, aaa, queries):
    queries2 = [[] for _ in range(n)]
    for i, (r, x) in enumerate(queries):
        r -= 1
        queries2[r].append((i, x))
    lll = [0]
    ans = [0] * q
    for i, a in enumerate(aaa):
        j = bisect_left(lll, a)
        if j == len(lll):
            lll.append(a)
        else:
            lll[j] = a

        for qi, x in queries2[i]:
            k = bisect(lll, x) - 1
            ans[qi] = k
    return ans


n, q = map(int, input().split())
aaa = list(map(int, input().split()))
queries = [tuple(map(int, input().split())) for _ in range(q)]
ans = solve(n, q, aaa, queries)
print('\n'.join(map(str, ans)))