モノグサプログラミングコンテスト2022（AtCoder Beginner Contest 238）F,G問題メモ

モノグサプログラミングコンテスト2022（AtCoder Beginner Contest 238）

Monoxerは、主に暗記学習について生徒・先生両者の負担を減らし効率化できるという学習用アプリ。
教育現場に売り込みたいにしてはちょっとネーミングが変という感じがしないでもない。 （むしろこういう方が印象に残ったりするのかな）

F - Two Exams

• $N$ 人が2回の試験を受け、1回目は $P_i$、2回目は $Q_i$ の順位を得た
  • 同率はいないので、$P,Q$ はそれぞれ $1～N$ の順列
• ここから以下の条件を満たして $K$ 人を選ぶ方法の個数を $998244353$ で割ったあまりで求めよ
• 条件
  • ある人 $x$ が選ばれていないとき、$x$ より2回の試験でともに順位が低い人が選ばれていてはいけない
  • たとえば $(P_i,Q_i)=(3,2)$ の人が選ばれず、$(5,6)$ の人が選ばれていることがあってはいけない
• $1 \le N \le 300$

2次元座標に落としたとき、自分より左下の人は全て選ばれている必要がある。

 |  ⑤           数字は人の番号
Q|      ③
 |④             ③が選ばれるには、①と④がともに選ばれていないといけない
 |    ①         ⑤が選ばれるには、④が選ばれていないといけない
 |        ②
 +-----------P

$P$ 基準でソートして、上位（左）から選ぶか選ばないかDPすることを考える。

DPでたとえば③を選ぶか選ばないか決める段階になったとき、 ③より左下にある点が全て選ばれている場合のみ、選ぶという遷移をすることができる。
要はこれまで処理された中で、$Q_i$ が $Q_3$ より小さい点が全て選ばれている必要がある。

ぱっと見、これまでに何を選んだかの全ての情報がないと判定できないように思えるが、 よく考えると「今までに選んでいない、一番小さい $Q_i$」がわかれば、③を選べるかどうかを判定するには十分である。

よって、以下のDPを組めばよい。

• $DP[i][j][k]=i$ 番目まで処理して、$j$ 個選んで、選んでいない中で最小の $Q_i=k$ である場合の数

なかなか、こういうまとめ方をするDPは見たことなかった。

Python3

import os
import sys

import numpy as np


def solve(inp):
    n = inp[0]
    k = inp[1]
    ppp = inp[2:2 + n]
    qqq = inp[2 + n:]
    MOD = 998244353

    yyy = np.zeros(n + 1, np.int64)
    yyy[0] = n
    for i in range(n):
        yyy[ppp[i]] = qqq[i] - 1

    dp_from = np.zeros((k + 1, n + 1), np.int64)
    dp_to = np.zeros((k + 1, n + 1), np.int64)
    dp_from[0, n] = 1
    for i in range(n):
        y = yyy[i + 1]
        for j in range(min(i, k) + 1):
            for l in yyy[:i + 1]:
                if j < k and l > y:
                    dp_to[j + 1, l] += dp_from[j, l]
                dp_to[j, min(l, y)] += dp_from[j, l]

        dp_to %= MOD
        dp_from, dp_to = dp_to, dp_from
        dp_to.fill(0)

    return dp_from[k, :].sum() % MOD


SIGNATURE = '(i8[:],)'
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', SIGNATURE)(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit(SIGNATURE, cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(ans)

G - Cubic?

• 長さ $N$ の正整数列 $A_1,...,A_N$ が与えられる
• $Q$ 個のクエリを処理せよ
• クエリ
  • $L_i,R_i$ が与えられる
  • $A_{Li} \times A_{Li+1} \times ... \times A_{Ri}$ が立方数（何らかの整数の3乗）かどうか判定せよ
• $1 \le N,Q \le 2 \times 10^5$
• $1 \le A_i \le 10^6$
• 実行制限時間: 3sec

計算量を気にしなければ、

• $A_i$ に出現する素因数毎に、どこに何個、素因数として出現したかの累積和を取っておく
• 累積和を使えば、素因数毎に、$L_i～R_i$ の総積に含まれる個数を $O(1)$ で計算できる
• クエリが来たら、全素因数につき、$L_i～R_i$ の総積に含まれる個数が3の倍数かチェック

とすればよい。

 i  (0) 1  2  3  4  5  6  7  8
 A      7 49 30  1 15  8  6 10
-------------------------------
p=2  0  0  0  1  1  1  4  5  6
p=3  0  0  0  1  1  2  2  3  3
p=5  0  0  0  1  1  2  2  2  3
p=7  0  1  3  3  3  3  3  3  3

L,R=4,6
p=2 のとき、4-1 = 3   OK
p=3 のとき、2-1 = 1   NG  → 立方数ではない

L,R=3,8
p=2 のとき、6-0 = 3
p=3 のとき、3-0 = 3
p=5 のとき、3-0 = 3
p=7 のとき、3-3 = 0       → ALL OK!

だがこれだと $10^6$ 以下の素数は $78498$ 個で、この全てが同時に出現する可能性があるので、約 $78498(N+Q)$ 回の計算&メモリが必要になり間に合わない。

まぁ、このほとんど全てが出現するような場合、そもそも全体の総積に1～2個しか含まれない素数が多くなるので、 それを除けば実質的な個数は減るかもしれないが、それでも厳しい。
$100$ 個程度だとギリギリ間に合わなくもないかも知れないが、さすがにそこまで減ることはなさそう。

そこで、複数の素数を同時に上手く管理する方法を考える。

ある区間に含まれる何らかの個数が「2」の倍数かどうかを求めたい場合、 上記の累積和の代わりに、出現位置に'1'を立てての累積XORを使える。XORが0なら偶数。

ある区間の個数が3の倍数かどうかを求めたい場合も同様に、2bitを利用すれば累積XORを使える。

• 1番目に出現した場所に「1（0b01）」を立てる
• 2番目に出現した場所に「2（0b10）」を立てる
• 3番目に出現した場所に「3（0b11）」を立てる
• 以降繰り返し

こうすると、どこから始めてもちょうど個数が3の倍数になったときだけ、XORが0になる。

1つの素数につき2bitずつ使うので、1つの64bit整数で31～32個の素数を管理できる。
高速な言語なら素因数31個ごとにまとめるだけで通るかもしれない。

しかし、Pythonとかでは不安なので、より高速化する。

1番目の素数を1,2bit目、2番目の素数を3,4bit目、、、31番目の素数を61,62bit目に当てはめる。
ここで32番目の素数をまた1,2bit目から始め、1番目の素数とまとめてしまう。

当然、これは誤った結果を返しうるが、ループを29個、30個、31個などずらしてその全てでチェックすれば、 さすがに誤った結果を返す可能性は十分低くなる。

そうすると、1つの値だけのチェック(xループずらし数回)で済むので、十分高速になる。

たとえばループを29,30,31の3パターンで試す場合に誤るテストケースはどんなものがあるか？

本当にYes（立方数）である場合は総XORは必ず0となり、Noと誤判定することはないので、誤るのは本当はNoなのにYesとなってしまうケース。

同じbitを共有する素数の区間XORを個別に計算したら、 個々で見ると0でないのに、全体のXORを取ると0になってしまう、 そんなことが全てのbit位置で発生していることになる。

$i$ 番目の素数を $p_i$ とし、ある区間の $p_1$ についての個別XORが 01 だったとする。

総XORが全体で0となり誤判定が生じる場合、たとえば以下を全て満たしている場合が当てはまる。

• 29でループするチェックに対し、$p_{30}$ も 01
• 30でループするチェックに対し、$p_{31}$ も 01
• 31でループするチェックに対し、$p_{32}$ も 01

すると、29でループする時に $p_{31},p_{32}$ とbitを共有するのは別の素数（たとえば $p_2,p_3$）なので、 これも 01 でなくてはならず、、、と連鎖することになる。
こうなるとさすがに全てで整合性を取るのはきつそう。

ただ、たとえば $LCM(29,30,31) = 26970$ なので、 $p_{26971}$ はどのチェックでも $p_{1}$ と同じbitを共有してしまい、これが 01 だと全チェックをすり抜けてしまう。

また、$p_{1}～p_{53940}$ の全てが 01 だったりしてもすり抜ける。

そもそも、そうなること自体が相当珍しいが、、、
チェックにたとえば23を加え、4つでチェックすれば $LCM(23,29,30,31)=620310$ となり、$10^6$ 以下の素数の個数を超えるので撃墜は確実に防げる。

これでももしかすると上手く撃墜ケースが作れるのかも知れないが、具体的にわからん。

多倍長が可能な言語では、まとめなくても全ての素数を個別に扱うこともできるっちゃできる。

ただし、それだとさすがに素数の個数が多くなったときにMLEとなった。
そういうケースは素数1つ当たりの出現回数は少ないことが想定できるので、 全体で2個以下しか出現しなかった素数は絶対に不可能として、bitを割り当てない、とする。

不可能な素数は出現位置を記録し、それを含むようなクエリが与えられた場合は問題無用でNoにすればよい。

まぁでもこの回避方法が読まれていた場合、最低限の3回ずつ多数の素因数が出てくるテストケースは作れるので、単に見逃されただけだったり。

• Zobrist_hashing
• 競技プログラミングにおけるハッシュ問題まとめ - はまやんはまやんはまやん

複数の要素の状態（パリティ）を同時に管理したいとき、要素ごとに乱数を対応させ、そのXORで判定する方法をZobrish Hashというらしい。

先ほどは、2bitを「ある1つの素数の区間内の個数 mod 3」を表現するのに使ったが、ここでは2つの適当な乱数を使う。

素数ごとに64bit以下の異なる正整数を2つ選ぶ。素数 $p$ について、$r_p,s_p$ とすると、

• 1回目の出現時は $r_p$
• 2回目の出現時は $s_p$
• 3回目の出現時は $r_p \ XOR \ s_p$
• 4回目の出現時は $r_p$
• …

として累積XORを取ると、2bitを使ったときと同様に、個数がちょうど3の倍数になったときだけ XOR が0になる。

複数の素因数による $r_p,s_p$ が混ざっても、全てが3の倍数になれば総XORは0になるので、容易に判定できる。

本当の答えはNoなのにYesと判定されるケースは、 「個別でXOR計算したら0にならない複数個の素数が、偶然打ち消しあって全体では0になってしまう」ような場合だが、 乱数なので64個ある総XORの各bitが0,1のどちらになるかは $\dfrac{1}{2}$ で、それがたまたま全て0になるのは $\dfrac{1}{2^{64}}$ と概算でき、十分低い。

テストケース $2 \times 10^6$ 個が全て通るのは、$\left ( \dfrac{2^{64}-1}{2^{64}} \right )^{2000000} \simeq 0.9999999999998915797828000059$ となり、ほぼ大丈夫なことがわかる。
それでも不安なら、複数回繰り返せばよい。

2bitずつ割り当てる方法は規則的なのでもしかしたら上手い撃墜ケースがあるかもしれないが、Zobrish Hashのように乱数を使うことで、より頑健になる。

クエリ平方分割手法の1つ、Mo's Algorithmを使っても解けるらしい。

• Mo's algorithm(クエリ平方分割)の話 - Qiita

ところで、XORとかを考える前に、まず $N$ 個の整数の素因数分解をしなければならない。

$\sqrt{A_i}$ までの素数で1個1個試し割っていくという 通常の?素因数分解では、1000以下の素数の個数 $168 \times N$ の計算が必要になりそれだけで厳しい。

$A_i$ の上限がそれなりに小さい（1次元配列を持てる程度）場合、SPFを使うことで1つあたり $O(\log{A_i})$ で求められる。そちらの方が高速。

• 複数のクエリの素因数分解を高速に処理する - Qiita

Python3

import sys
from collections import defaultdict
from itertools import accumulate


def get_spf(n):
    """ nまでの各数を割り切る一番小さな素数 """
    spf = list(range(n + 1))
    for i in range(2, n + 1, 2):
        spf[i] = 2
    for p in range(3, int(n ** 0.5) + 1, 2):
        if spf[p] == p:
            for m in range(p * p, n + 1, 2 * p):
                if spf[m] == m:
                    spf[m] = p
    return spf


def prime_factorize(x, spf):
    """ xを素因数分解、(素数, 個数)の配列で返す """
    factors = []
    prev = -1
    cnt = 0
    while x > 1:
        if spf[x] == prev:
            cnt += 1
        else:
            if prev != -1:
                factors.append((prev, cnt))
            prev = spf[x]
            cnt = 1
        x //= spf[x]
    if prev != -1:
        factors.append((prev, cnt))
    return factors


input = sys.stdin.buffer.readline
n, q = map(int, input().split())
aaa = list(map(int, input().split()))

spf = get_spf(1000000)
appeared_primes = defaultdict(lambda: [[], 0])
prime_factors = []
for i, a in enumerate(aaa):
    pf = prime_factorize(a, spf)
    prime_factors.append(pf)
    for p, cnt in pf:
        appeared_primes[p][0].append(i)
        appeared_primes[p][1] += cnt

possible_primes = []
impossible = [0] * (n + 1)
for p, (locs, cnt) in appeared_primes.items():
    if cnt <= 2:
        for i in locs:
            impossible[i + 1] = 1
    else:
        possible_primes.append(p)

acc_impossible = list(accumulate(impossible))

primes_index = {p: i for i, p in enumerate(possible_primes)}
primes_count = [0] * len(possible_primes)

dp = [0]

for i, pf in enumerate(prime_factors):
    if impossible[i + 1] > 0:
        dp.append(0)
        continue

    cur = 0
    for p, cnt in pf:
        if cnt == 0:
            continue
        i = primes_index[p]
        for _ in range(cnt):
            cur ^= (primes_count[i] + 1) << (2 * i)
            primes_count[i] = (primes_count[i] + 1) % 3
    dp.append(dp[-1] ^ cur)

ans = []
for _ in range(q):
    l, r = map(int, input().split())
    l -= 1

    if acc_impossible[l] != acc_impossible[r]:
        ans.append('No')
        continue

    if dp[l] ^ dp[r] == 0:
        ans.append('Yes')
    else:
        ans.append('No')

print('\n'.join(map(str, ans)))