トヨタ自動車プログラミングコンテスト2024#9（AtCoder Beginner Contest 370）F,G問題メモ

トヨタ自動車プログラミングコンテスト2024#9（AtCoder Beginner Contest 370）

F - Cake Division

• 円形のケーキがあり、ケーキは中心から外周への切り目によって $N$ 個の扇形のピースに分けられています。
• ピースおよび切り目には時計回りに $1, 2, \ldots, N$ の番号が付けられており、ピース $i$ の質量は $A_i$ です。
• このケーキを以下の条件を満たすように $K$ 人に分けます。
  • すべての人が $1$ つ以上の連続するピースを受け取る
  • 誰も受け取らないピースは存在しない
  • 上の $2$ つの条件を満たすという条件下で $\min(w_1, w_2, \ldots, w_K)$ が最大になるようにする
    • ただし、$i$ 番目の人が受け取るピースの質量の合計を $w_i$ とする
• 以下の2つを求めてください。
  • 条件を満たす分け方における $\min(w_1, w_2, \ldots, w_K)$ の値
  • 条件を満たすどのような分け方でも切られることのない切り目の個数

• $2 \leq K \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^4$
• 入力される値はすべて整数

ABCでもよく見る典型がいくつか組み合わさった問題。
自然な形で上手く組み合わさっているので、気付くとなかなか気持ちいい。

1人1人が受け取るピースの塊を、「分け前」と呼ぶことにする。

円形のケーキじゃなくて両端があるなら、大枠は典型90問の第1問目でも名高いこの問題に近くなる。

• 001 - Yokan Party（★4）

両端が分かっている場合、「全体を、$K$ 個以上の、質量 $x$ 以上の分け前に分割できるか？」が解ければ、$x$ を二分探索することで解ける。
これは端から「ピースの質量合計が $x$ 以上になったらそこですぐ切る」ことを繰り返せば、$O(N)$ で判定できる。

ただ、今回は端が決まっていないので、切り目 $1$ から切った場合は無理でも、他の切り目から始めたら行けるかもしれない。

i  1  2  3  4  5    K=3
A  6  8  6  4  3

x=8 は可能?
1から始めると、i=1,2 / 3,4 /（残りは8に満たない）で2個。NG
2から始めると、i=2 / 3,4 / 5,1   3個に分けられる。OK

$N$ 箇所全ての切り目から1回 $O(N)$ の判定を試すのは $O(N^2)$ で無理。

ただ、どこから始めても、その過程で「$i$ が分け前の開始ピースとなったら、どこまで続いて、次に切られるのはどこ」という関係性は変わらない。
例えば、上例では $i=3$ から始まった分け前は、共通して $3,4$ まで続き、次の分け前は $i=5$ から開始される。

分け前が $i$ から始まった場合の次の分け前の開始点を $x=8,i=3$ に対して $B_8[3]=5$ というように表現すると、$B_8=(3,3,5,7,7)$ となる。（1周を超える分でも番号は継続するとして）

すると $x$ を固定した場合の、各 $i$ に対する判定問題は 「$i$ を $B_x[i]$ に置き換える操作を $K$ 回行って、 最終的な $i$ が1周以内（＝$i+N$ 以下）に収まっていればよい」ということになる。

これはダブリングで高速化でき、全ての $i=1～N$ に対して $O(N \log{K})$ で求められる。

実装上のテクニックとして、OutOfIndex にならないよう $B_x$ は2周分+さらに末尾に $2N+1$ を追加しておき、 遷移後の値が $2N+1$ を超える場合は $2N+1$ で上限を切るとよい。
ダブリング中、$2N+1$ を超えそうになったら $2N+1$ でループするようになる。
1周以内に収まっているかの判定の最大値が $i=N$ から始まったときの「$2N$ 以下か？」であり、 $2N+1$ まで行ったらどの $i$ に対してもNGであることが確定するので、それ以上の具体的な値の情報は必要ない。

判定問題を満たす $i$ が1つでもある最大の $x$ が、答えの1つめ。

改めてダブリングによる $K$ 回遷移後の $i$ を求め、 1周以内に収まっていない $i$ の個数が答えの2つめ「そこで切ったら最大値を達成できない切り目」の個数となる。

Python3

from bisect import bisect_left
from itertools import accumulate


def get_limit(n, m, k, acc):
    block_limit = []
    block_limit2 = []
    lim = n * 2
    for i in range(n):
        nxt_block = bisect_left(acc, acc[i] + m)
        block_limit.append(nxt_block)
        block_limit2.append(min(lim, nxt_block + n))
    block_limit.extend(block_limit2)
    block_limit.append(lim)
    # print(f'{n=} {m=} {k=} {acc=} {block_limit=}')

    limits = list(range(n))
    while k:
        if k & 1:
            for i in range(n):
                limits[i] = block_limit[limits[i]]
        new_block_limit = []
        for i in range(n * 2 + 1):
            new_block_limit.append(block_limit[block_limit[i]])
        block_limit = new_block_limit
        # print(f'{limits=}')
        # print(f'{block_limit=}')
        k >>= 1
    return limits


def check(n, m, k, acc):
    limits = get_limit(n, m, k, acc)
    for i in range(n):
        if limits[i] <= i + n:
            return True
    return False


n, k = map(int, input().split())
aaa = list(map(int, input().split()))
acc = [0] + list(accumulate(aaa + aaa))

l = 1
r = sum(aaa) // k + 1
while l + 1 < r:
    m = (l + r) // 2
    if check(n, m, k, acc):
        l = m
    else:
        r = m

limits = get_limit(n, l, k, acc)
ans = 0
for i in range(n):
    if limits[i] > i + n:
        ans += 1

print(l, ans)

G - Divisible by 3

• 正整数 $n$ の正の約数の総和が $3$ で割り切れる時、$n$ を「良い整数」と呼びます。
• 正整数 $N, M$ が与えられます。
• 長さ $M$ の正整数列 $A$ のうち、 $A$ の要素の総積が $N$ 以下の良い整数になるものの個数を $998244353$ で割った余りを求めてください。

• $1 \leq N \leq 10^{10}$
• $1 \leq M \leq 10^5$
• $N, M$ は整数

「乗法的関数のPrefix-Sum」という手法を用いる。知らないと無理。知ってても本番中に考察して応用して実装するのは厳しい。

• 乗法的関数のprefix sum | Nyaan’s Library

$x=p_1^{e_1}p_2^{e_2}...$ と素因数分解できるとき、 約数の総和は $(1+p_1+p_1^2+...+p_1^{e_1})(1+p_2+p_2^2+...+p_2^{e_2})...$ で求められる。

この $(1+p+p^2+...+p^e)$ というパートは、

• $p=3$ のとき、絶対に3の倍数にはならない
• $p \equiv 1 \mod{3}$ のとき、$e \equiv 2 \mod{3}$ なら3の倍数。他は3の倍数でない。
• $p \equiv 2 \mod{3}$ のとき、$e \equiv 1 \mod{2}$ なら3の倍数。他は3の倍数でない。

となり、少なくともどれか1つの素因数とその指数 ($p_i, e_i)$ で $(1+p_i+p_i^2+...+p_i^{e_i})$ が3の倍数となってくれれば、$x$ は「良い整数」となる。

この判定法を用いて、$x=1～N$ に対し $x$ が良い整数である時のみ以下の問題を解くと、その総和が答えとなる。

• 総積が $x$ となるような、長さ $M$ の数列の個数を求めよ

これは $x$ の素因数毎に独立に考えることができて、例えば $x=360=2^33^25^1$ を例に取ると、

• 2を3つ、重複を許して $M$ 個の要素のどれかに振り分ける
• 3を2つ、重複を許して $M$ 個の要素のどれかに振り分ける
• 5を1つ、重複を許して $M$ 個の要素のどれかに振り分ける

これらの積で、${}_3\mathrm{H}_M \times {}_2\mathrm{H}_M \times {}_1\mathrm{H}_M$ で求められる。

だが、これは当然、$x$ を最大 $10^{10}$ 個 調べないといけないので、TLE。

正整数を引数に取る関数 $f(x)$ が次の条件を満たすとき、$f(x)$ は乗法的関数（Multiplicative Function）であるという。

• 互いに素な $a,b$ に対して、$f(ab)=f(a)f(b)$

上記の通り、「$g(x):=$ 総積が $x$ となるような、長さ $M$ の数列の個数」は、乗法的関数である。

このような乗法的関数の1から $N$ までの総和 $\displaystyle F(N)=\sum_{x=1}^{N}g(x)$ は、 後述するが高速に計算する手法がある。

今回は「良い整数」のみについて $g(x)$ を足し合わせないといけないので そのままは適用できないが、工夫すれば適用できるようになる。

まずは、良い整数の要素は除いて、$F(N)$ を求めることを考える。

特殊な $N$ 頂点の木でDPをするアルゴリズム。

N=25                       ①
       ,-----------------,-'`----,--,--,--,--,--,
      ②                ③       ⑤ ⑦ ⑪ ⑬ ⑲ ㉓
   ,--'`--,--,--,--,    /`,--,   ｜
  ④      ⑥ ⑩ ⑭ ㉒  ⑨ ⑮ ㉑  ㉕
  /`,--,  ｜
 ⑧ ⑫ ⑳ ⑱
 /\
⑯㉔

• 木の生成規則
  • 頂点 $1$ を根とする根付き木である
  • 頂点 $v$（$v \ge 2$）は、「$v$ を最大の素因数で割った値」の頂点を親に持つ
    • ㉑ $= 3 \times 7$ は、最大の素因数 $7$ で割った③を親に持つ
    • ⑱ $= 2 \times 3^2$ は、最大の素因数 $3$ で割った⑥を親に持つ

以下、$\mathrm{Lpf}(x):=x$ の最大の素因数 とする。

親から子への視点で整理すると、 頂点 $v$ は「$\mathrm{Lpf}(v) ～ \lfloor \frac{N}{v} \rfloor$」の間の素数を $v$ にそれぞれかけた番号の子を持つ。

• ②は、$\mathrm{Lpf}(2)=2 ～ \lfloor \frac{N}{2} \rfloor = 12$ 間の素数 $(2,3,5,7,11)$ を自身にかけた④⑥⑩⑭㉒の子を持つ。
• ③は、$\mathrm{Lpf}(3)=3 ～ \lfloor \frac{N}{3} \rfloor = 8$ 間の素数 $(3,5,7)$ を自身にかけた⑨⑮㉑の子を持つ。

仮に（$N$ が大きいので実際には無理だが）$N$ 以下の全ての素数 $p=2,3,5,...$ につき $g(p)$ が計算済みであり、 累積和を取ることで、任意の区間の「素数のみの $g(p)$ の和」が $O(1)$ で求められるとする。

• $F_{\mathrm{prime}}(N) := 1$ から $N$ までのうち、素数のみの $g(p)$ の和
• $G(l,r):=l$ より大きく $r$ 以下の数のうち、素数のみの $g(p)$ の和（$= F_{\mathrm{prime}}(r) - F_{\mathrm{prime}}(l)$）

すると、乗法的関数の性質「互いに素なら、$g(ab)=g(a)g(b)$」を利用すると、 たとえば②の子④⑥⑩⑭㉒（それぞれ2に2,3,5,7,11がかけられた数）のうち、

• ④だけは、②にも含まれる素因数がかけられ $g(4) = g(2)g(2)$ とは限らないので、個別の計算をする。
• ⑥以降は、木の生成規則から、確実に②とは互いに素な数がかけられている。
  • よって、$g(6)+g(10)+g(14)+g(22)$ は、$g(2) \times G(2,12)$ でまとめて求められる。

これは、$v=$ ③や⑧など、他の内部ノード（葉以外の頂点）でも $G$ を使って同様のことが言え、

• $v$ と同じ素因数がかけられる唯一の子は、個別計算
• それより大きい素数がかけられた数は、内部ノードを $v$ として、$g(v) \times G(\mathrm{Lpf}(v), \lfloor \frac{N}{v} \rfloor)$ でまとめて計算

という処理を全ての内部ノードについて行うことで、$x=1～N$ の全ての $g(x)$ の総和が求められることになる。
葉ノードは個別処理する必要が無い、というのがこのアルゴリズムの肝となる。

で、実際にこの木において内部ノードの数は少なく、$N=10^{10}$ に対して $6.3 \times 10^6$ 程度で済むらしい。

これで、「$G$：ある区間の素数だけの $g(x)$ の和」が求められれば、現実的な時間で $F(N)$ を求められることがわかった。

肝心の $G$ をどうやって求めるか。
$N \le 10^{10}$ のような制約で、$N$ 以下の全ての素数に対して $g(p)$ なんて求められない。

よく考えると、Black Algorithm の過程で実際に必要とされる $G(l,r)$ の $l,r$ の値って、実はそんなに多くない。

内部ノード $x$ の処理を考えるとき、必要となる $l,r$ は

• $l$ は、$x$ の最大の素因数。
  • $x$ は内部ノード（子を持っている）前提なので、$x \mathrm{Lpf}(x) \le N$。
  • $x$ も当然 $\mathrm{Lpf}(x)$ を素因数に持っているので、$l = \mathrm{Lpf}(x) \le \sqrt{N}$
• $r$ は、$\lfloor \frac{N}{x} \rfloor$
  • つまり「$Q(N):=N$ を何らかの整数で切り捨て除算した値として取り得る数」しか $r$ にならない。
  • たとえば $Q(57)=(1,2,3,4,5,6,7,8,9,11,14,19,28,57)$
  • これは、前半 $k=1～\sqrt{N}$ に対して後半が $\frac{N}{k}$ としてそれぞれ対応する関係にあり、約 $2\sqrt{N}$ 個しかない。

$l$ の値の範囲は $r$ に内包されるので、結局、$Q(N)$ に含まれる各数 $q_i$ について $F_{\mathrm{prime}}(q_i)$ が求められれば、 Black Algorithm の過程で必要な $G(l,r)$ に対して全て答えられるということになる。

で、乗法的関数においてこれをするのがLucy DPとなる。

• 素数の個数や和を高速に計算できるLucy DPをやさしく説明 #Python - Qiita

今回は、良い整数だけを数えなければならない。

Black Algorithm で $x$ の子の $g(*)$ をまとめて足し上げる時に、

• $\mathrm{Lpf}(x)$ 未満の素因数により、$x$ の約数が3の倍数となることが確定している場合
  • つまり、$\mathrm{Lpf}(x)$ 未満の素因数 $p$ とその指数 $e$ で、$(1+p+p^2+...+p^e)$ が3の倍数となるものが存在する
  • この場合、$x$ の子も全て良い整数であることが確定しているので、全て足し上げて良い。
• $\mathrm{Lpf}(x)$ によってのみ、$x$ の約数が3の倍数となる場合
  • 一番左の子（$x \times \mathrm{Lpf}(x)$）は、個別に確認の必要がある。
  • 一番左の子以外は、$\mathrm{Lpf}(x)$ によって良い整数であることが確定するので、全て足し上げて良い。
• $x$ が良い整数でない場合
  • 一番左の子は、個別に確認する。
  • 一番左の子以外は、「3で割って2余る素数 $p$ をかけた子に対してのみ、$g(xp)$ を足し上げる」ことになる。
    • $x$ と互いに素な $p$ に対して $xp$ が良い整数になるには、$(1+p)$ が3の倍数となる必要があるため。

よって、$G$ に加えて「$H(l,r):=l$ より大きく $r$ 以下の、3で割って2余る素数のみの $g(p)$ の総和」があれば、 良い整数に限定した数え上げも可能となる。

$H$ は、Lucy DPで「素数全体」に加え 「3で割って1余る素数の個数」「3で割って2余る素数の個数」に分けて管理していくと、上手く計算できる。

Black Algorithm 上でDFSをするにあたり、

• $g(x)$
• $\mathrm{Lpf}(x)$ とその指数 $e$
• 既に $\mathrm{Lpf}(x)$ 未満の素因数により $x$ が良い整数であることが確定しているフラグ

などを持ちながらおこなうとよい。

Python3