AtCoder Beginner Contest 423 E,F問題メモ

AtCoder Beginner Contest 423

E - Sum of Subarrays

問題文

長さ $N$ の整数列 $A = (A_1, A_2, \ldots, A_N)$ が与えられます。
$Q$ 個のクエリが与えられるので、それぞれについて答えを求めてください。
$i$ 番目のクエリでは、整数 $L_i, R_i$ が与えられるので、 $\displaystyle\sum_{l = L_i}^{R_i}\sum_{r = l}^{R_i}\sum_{j = l}^{r} A_j$ の値を答えとして求めてください。

制約

$1 \leq N, Q \leq 3 \times 10^5$
$1 \leq A_i \leq 100$
$1 \leq L_i \leq R_i \leq N$
入力される値はすべて整数

解法

$i^2A_i, iA_i, A_i$ のそれぞれの累積和を持つことで解ける。

解説 - AtCoder Beginner Contest 423

解法2

毎度安心のセグメント木解法。

「セグ木にのせるもの」と「マージする方法」を考えればよい。
結論から言うと、区間 $x$ に以下の5つの情報を持たせるとできる。

$x_1$: 区間長
$x_2$: 区間の $A_i$ の総和
$x_3$: 区間の全ての部分列の総和の総和（求めたいもの）
$x_4$: 部分列のうち、左端要素を使うものの総和の総和
$x_5$: 部分列のうち、右端要素を使うものの総和の総和

 x
[ 1  2  3  4 ]

x4の対象となる部分列
  1
  1  2          x4 = (1)+(1+2)+(1+2+3)+(1+2+3+4) = 20
  1  2  3
  1  2  3  4

x5の対象となる部分列
           4
        3  4    x5 = (4)+(3+4)+(2+3+4)+(1+2+3+4) = 30
     2  3  4
  1  2  3  4

$a=(1,2,3),b=(4,5,6,7)$ とし、マージした区間を $c$ とすると、$c_1,c_2$ は自明な足し算で求められる。
$c_4$ は以下のようにして求められる。左右逆転して同様に $c_5$ も求められる。

[ 1  2  3  4  5  6  7 ]

c4の対象    a4
  1       ↙
  1  2
 _1__2__3_         b4
  1  2  3| 4     ↙
  1  2  3| 4  5
  1  2  3| 4  5  6
  1  2  3| 4  5  6  7
     ↑
   a2*b1

$c_3$ は、以下のようにして求められ、$a_3+b_3+a_5b_1+b_4a_1$ となる。

マージ境界をまたがないもの: a3, b3

またぐもの: 左右別にそれぞれがどれだけ寄与するかで考える

    a5             b4
        3      4
     2  3  ×  4  5
  1  2  3      4  5  6
               4  5  6  7

  a5 側の各部分列は、右をどこまで伸ばすかが b1 通りずつある → a5 * b1
  b4 側の各部分列は、左をどこまで伸ばすかが a1 通りずつある → b4 * a1

これでマージができるので、セグメント木に載せると $O((N+Q) \log{N})$ でできる。

Python3

from atcoder.segtree import SegTree


def solve(n, q, aaa, queries):
    def merge(a, b):
        a0, a1, a2, a3, a4 = a
        b0, b1, b2, b3, b4 = b
        c0 = a0 + b0
        c1 = a1 + b1
        c3 = a3 + a1 * b0 + b3
        c4 = b4 + b1 * a0 + a4
        c2 = a2 + b2 + a4 * b0 + b3 * a0
        return (c0, c1, c2, c3, c4)

    # (長さ, 区間和, 全体合計, 左端を使うものの合計, 右端を使うものの合計)
    init = [(1, a, a, a, a) for a in aaa]
    sgt = SegTree(merge, (0, 0, 0, 0, 0), init)
    ans = []
    for l, r in queries:
        result = sgt.prod(l - 1, r)
        ans.append(result[2])
    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)))

F - Loud Cicada

問題文

AtCoder 島には $N$ 種類のセミが生息しています。種類 $i$ のセミ ($1 \leq i \leq N$) は $A_i$ の倍数の年にのみ大量発生します。
$1$ 年から $Y$ 年までの $Y$ 年間のうち、ちょうど $M$ 種類のセミが大量発生する年が何回あるかを求めてください。

制約

$1 \leq M \leq N \leq 20$
$1 \leq Y \leq 10^{18}$
$1 \leq A_i \leq 10^{18}$ ($1 \leq i \leq N$)
入力される値はすべて整数

解法

素数ゼミをテーマとした問題。
包除原理っぽいが、いつもとはちょっと違い「ちょうど $M$ 種類」のものを求めたい。

いつもの包除原理なら $\displaystyle \sum_{S}(-1)^{|S|} f(S)$ とか（$f$ は適当な関数）で求められるが、これは「少なくとも1つの条件に当てはまる」$f(S)$ の合計を求めることになり、ここから「ちょうど $M$ 個の条件に当てはまる」場合は求まらない。

N=3 M=2
  ┌──┐      □□□
┌┼─┐│    □■■□    黒いとこだけのf(S)を求めたい
││┌┼┼┐  □■□■□
│└┼┼┘│  □□■□□
└─┼┘  │      □□□
    └──

あるセミの種類の集合 $S=\{i_1,i_2,...\}$ に対し、そいつらが揃って大量発生する周期は $\mathrm{LCM}(A_{i1},A_{i2},...)$ であり、 $Y$ 年間の中での発生回数は $C_S = \left \lfloor \dfrac{Y}{\mathrm{LCM}(A_{i1},A_{i2},...)} \right \rfloor$ である。

この時、LCMはまともに計算すると巨大になり得るので注意。
途中で $Y$ を超えたら $C_S=0$ に決まるので、計算を打ち切ってよい。

これらを、$|S| \ge M$ である全ての $S$ について計算しておく。

さらに、$|S|$ ごとに計算結果をまとめておく。$\displaystyle D_d = \sum_{|S|=d}C_S$

すると、答えは以下で求められる。

$\displaystyle \sum_{d=M}^{N}(-1)^{d-M} \binom{d}{M} D_d$

証明は「真の答え」と「$C_S$ を合計しただけのダブりを含んだ答え $D_d$」の間に計算式をたて、式変形することで導出できる。

解説 - AtCoder Beginner Contest 423

Python3

from math import gcd


def iter_bit(bitset):
    i = 0
    while bitset:
        if bitset & 1:
            yield i
        i += 1
        bitset >>= 1


def solve(n, m, y, aaa):
    def ncr(n, r):
        result = 1
        for i in range(r):
            result *= n - i
            result //= i + 1
        return result

    cases = [0] * (n + 1)
    lcm_memo = [0] * (1 << n)
    lcm_memo[0] = 1
    for bitset in range(1, 1 << n):
        bc = bitset.bit_count()
        lsb = bitset & -bitset
        lcm = lcm_memo[bitset ^ lsb]
        if lcm > y:
            lcm_memo[bitset] = lcm
            continue
        a = aaa[lsb.bit_length() - 1]
        g = gcd(lcm, a)
        lcm = lcm // g * a
        lcm_memo[bitset] = lcm
        cases[bc] += y // lcm

    ans = 0
    pn = 1
    for i in range(m, n + 1):
        ans += pn * cases[i] * ncr(i, m)
        pn *= -1
    return ans


n, m, y = map(int, input().split())
aaa = list(map(int, input().split()))
ans = solve(n, m, y, aaa)
print(ans)

目次

AtCoder Beginner Contest 423 E,F問題メモ

E - Sum of Subarrays

問題文

制約

解法

解法2

F - Loud Cicada

問題文

制約

解法