AtCoder Talent Quest 〜 今から28卒には脱出してもらいます〜予選 #2（AtCoder Beginner Contest 480）E,F,G問題メモ

AtCoder Talent Quest 〜 今から28卒には脱出してもらいます〜予選 #2（AtCoder Beginner Contest 480）

序盤からそこそこ難しい（手で解くのはできるけど、どう楽に実装に落とし込もうか？を迷う）問題が揃っていた印象。

E - Product-Bounded Arithmetic Sequences

• 以下の条件を全て満たす正整数列 $A=(A_1,\dots,A_{|A|})$ を良い数列と定めます。
  • $|A|\geq 3$
  • $A$ は等差数列である。即ち、全ての $1 \leq i \leq |A|-1$ について $A_{i+1}-A_{i}=A_2-A_1$
  • $A_2-A_1 \gt 0$
• 良い数列のうち、要素の総積が $N$ 以下であるものの個数を求めてください。
• なお、制約の条件下で答えが $10^{18}$ 以下となることが証明されます。

• $1 \leq N \leq 10^{18}$
• $N$ は整数

初項 $a$、交差 $d$、項数 $m$ の3つの要素を決めれば総積が決まる。

それぞれ、他の2つが最小であるときに取り得る値の範囲を考えると、（大体のオーダーで）

• $1 \le a \le 10^6$
• $1 \le d \le 10^9$
• $3 \le m \le 19$

よって、$(a, m)$ を全探索し、その中で $d$ をどこまで大きくできるか二分探索すればよい。

Python3

def solve(n):
    def prod_overflow(a, b, limit):
        if b == 0:
            return 0
        if a > limit // b:
            return -1
        return a * b

    ans = 0
    for a in range(1, 10 ** 6 + 1):
        for m in range(3, 20):
            t = a
            for k in range(1, m):
                t = prod_overflow(t, a + k, n)
                if t == -1:
                    break
            if t == -1:
                break
            l = 1
            r = 10 ** 9 + 5
            while l + 1 < r:
                mid = (l + r) // 2
                t = a
                for k in range(1, m):
                    t = prod_overflow(t, a + k * mid, n)
                    if t == -1:
                        break
                if t == -1:
                    r = mid
                else:
                    l = mid
            ans += l
            # print(f'{d=} {m=} {l=}')
    return ans

n = int(input())
ans = solve(n)
print(ans)

F - Cake Cutting

• $N$ 個のケーキがあり、 $i$ 個目のケーキの大きさは $A_i$ です。これらのケーキを $M$ 人に配ろうとしています。
• ケーキの大きさの総和 $A_1+\dots+A_N$ を $S$ とします。 ここで、 $S$ は $M$ の倍数であることが保証されます。
• あなたは、以下の操作を好きな順序で好きな回数( $0$ 回でもよい)行うことができます。
  • ケーキを $1$ つ選び、それを自由に $2$ つに切り分ける。
  • 切り分ける大きさは整数でなくてもよく、1つのケーキを何回切ってもよい。
• 操作後、ケーキを $M$ 人に配ります。どの人がもらうケーキの大きさの合計も $\frac{S}{M}$ となるようにするための、操作回数の最小値を求めてください。

• $1 \leq N \leq 20$
• $1 \leq M \leq 100$
• $1 \leq A_i \leq 10^9$
• $A_1+\dots+A_N$ は $M$ の倍数
• 与えられる数値は全て整数

次のように言い換えてイメージする。

• 長さ $A_1,A_2,...,A_N$ の棒を一列に並べて、左から $\frac{S}{M}$ の位置ごとに切っていく。

これで、多くとも必ず $M-1$ 回の操作で達成できることが分かる。
切ろうとしている位置が元から切れていた（棒の境界だった）場合、1箇所ごとに1回、操作回数を節約できる。

$A$ を適切に並べ替えることで、$\frac{S}{M}$ の倍数位置に境界が来る回数を最大にすればよい。

• $\mathrm{DP}[S]:=$ 集合 $S$ を適切に並べ替えることで $\frac{S}{M}$ の倍数位置に境界を作ることができる最大回数

（末尾も境界とした上で）$M-\mathrm{DP}[A]$ が答えとなる。

DPは、$S$ にまだ存在してない適当な1つを加えて $\frac{S}{M}$ の倍数になるなら $\mathrm{DP}[S | i] ← \mathrm{DP}[S]+1$ としていく遷移で、$O(N2^N)$ で解ける。

Python3

def solve(n, m, aaa):
    def iter_bit(bitset):
        while bitset:
            lsb = bitset & -bitset
            yield lsb
            bitset ^= lsb

    s = sum(aaa)
    t = s // m
    satisfied = [0] * (1 << n)
    remaining = [0] * (1 << n)
    for bitset in range(1, 1 << n):
        lsb = bitset & -bitset
        i = lsb.bit_length() - 1
        r = remaining[bitset ^ lsb] + aaa[i]
        d, r = divmod(r, t)
        satisfied[bitset] = satisfied[bitset ^ lsb] + d
        remaining[bitset] = r
    # print(f'{satisfied=}')
    # print(f'{remaining=}')
    INF = 1 << 60
    dp = [INF] * (1 << n)
    dp[0] = 0
    for bitset in range(1, 1 << n):
        best = INF
        for b in iter_bit(bitset):
            i = b.bit_length() - 1
            d, r = divmod(aaa[i], t)
            if r == 0:
                best = min(best, dp[bitset ^ b] + d - 1)
            else:
                r += remaining[bitset ^ b]
                if r <= t:
                    best = min(best, dp[bitset ^ b] + d)
                else:
                    best = min(best, dp[bitset ^ b] + d + 1)
        dp[bitset] = best

    return dp[-1]


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

G - Zonal Score Minimization

• 長さ $2$ 以上の正整数列のスコアをその数列の最大値と最小値の差で定義します。
• 長さ $N$ の正整数列 $A$ が与えられるので、$A$ を長さ $2$ 以上であるような $1$ つ以上の連続部分列に分割したときに各連続部分列のスコアの総和としてあり得る値の最小値を求めてください。
  • （例）$(3,1,4,1,5,9,2)$ を $[(3,1,4),(1,5),(9,2)]$ と分割したとき、スコアの総和は $(4-1)+(5-1)+(9-2)=14$

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

DPで考える。まずは、よくありがちなDP定義を仮定して考えてみると、

• $\mathrm{DP}_{仮}[i]:=i$ と $i+1$ の間で部分列を分割するとき、$i$ までにおけるスコアの総和の最小値

すると、更新は以下のようになる。$\max(A[i:j])$ は、$A_i～A_j$ の最大値を表すとする。

• $\mathrm{DP}_{仮}[i]=\min_{1 \le j \le i-2}\mathrm{DP}_{仮}[j] + \max(A[j+1:i]) - \min(A[j+1:i])$

i                           i
A       3   1   4   1   5   9
     ：                        ┐
    ... ] + [   max - min   ]  │
    ....... ] + [ max - min ]  │DP[i]はこの中の最小値
    ............] + [max-min]  │
    ................] + [   ]  ┘

DP[j]の最小値だけならセグメント木で取れるが、後半のmaxとminが絡むと厄介。

そこで、次の区間の暫定 max - min もDPの中に織り込んでやる。

• $\mathrm{DP}[j,i]:=$
  • $i$ より前で、最後に分割したのが $j$ と $j+1$ の間であるとき（$j+2 \le i$）、
  • 「$j$ までのスコアの総和の最小値」+「次の部分列の $i$ までの暫定スコア $\max(A[j+1:i]) - \min(A[j+1:i])$」

このままだとDPが2次元になってしまうが、データとしては $\mathrm{DP}[j]$ の1次元で持ったまま、$i$ を進める毎に更新していくことができる。 $\mathrm{DP}[j,i-1]$ と $\mathrm{DP}[j,i]$ の変化を考えると、

■A[i] が max(A[j+1:i-1]) を上回る場合
i   ... j  j+1         i-1 i
A        ]  3  1  4  1  5  9    これまでの max(3,1,4,1,5) を 9 は上回るため、
           ~~~~~~~~~~~~~~~      DP[j,i] = DP[j,i-1] + (新max(9) - ここまでのmax(5))

■A[i] が min(A[j+1:i-1]) を下回る場合
i   ... j  j+1         i-1 i
A        ]  8  7  4  9  6  1    これまでの max(8,7,4,9,6) を 1 は下回るため、
           ~~~~~~~~~~~~~~~      DP[j,i] = DP[j,i-1] + (ここまでのmin(4) - 新min(1))

■それ以外の場合
  変化無し                      DP[j,i] = DP[j,i-1]

なので、実装の上では $\mathrm{DP}[j]$ の1次元で持った上で、$i$ を進めるたびに差分更新していける。

また、今度は $i$ の方を固定して、$i$ で更新が生じるときに $j$ によって差分がどのようになるか考えると、（例としてmaxを更新する場合をあげるが、minも同様）

     i    ...  3   4   5   6   7  [8]   i=8について DP[*,8] を求めたい
     A    ...      9   1   4   2   7
DP[6, 8]                   ] + [   ]    7が最大値2を更新するので、  DP[6, 8] = DP[6, 7] + 7-2
DP[5, 8]               ] + [       ]    7が最大値4を更新するので、  DP[5, 8] = DP[5, 7] + 7-4
DP[4, 8]           ] + [           ]    7が最大値4を更新するので、  DP[4, 8] = DP[4, 7] + 7-4
DP[3, 8]       ] + [               ]    7は最大値9を更新しないので、DP[3, 8] = DP[3, 7]
                 :       :
i-1までのmax   9 |   4   |  2

$i=8$ に対し、$j=6$（$=i-2$）から $j$ を遡っていくたびに、「最後の部分列の $i$ より前の部分に含まれる max（★）」は、単調非減少となる。 上例では、★は $j=6$ で $2$、$j=5,4$ で $4$、$j=3$ 以前で $9$ となる。

★は、$i-1$ から $A$ を遡った時、累積 max を更新した直後の $j$ で切り替わる。 更新されない間は、$\mathrm{DP}[j,i-1]$ から $\mathrm{DP}[j,i]$ への変化量は、連続した $j$ に対して同じになるので、遅延セグ木などでまとめて更新できる。

max が更新される箇所は、スタックを使うことで $O(N)$ で管理できる。 スタック末尾の値を $t$ とし、$t \lt A_i$ である間 pop し、$t$ が最大値であった区間（スタックにindexも一緒に積んでおくと特定可能）に $A_i - t$ を加算すればよい。

遅延セグ木で区間更新する回数は上記で pop が発生する回数に等しい。よって全体 $O(N\log{N})$ で求められる。

   A    ...      9   1   4   2   7
               :               :     最大値が4,2だった区間は、iでの更新後、等しく7が
iまでのmax   9 |       7       |   ←新しい最大値となるので i+1以降、更新はまとめておこなえる

Python3

from operator import add

from atcoder.lazysegtree import LazySegTree


def solve(n, aaa):
    INF = 1 << 60

    merge = min
    mapping = add
    composition = add
    lst = LazySegTree(merge, INF, mapping, composition, 0, n + 2)
    lst.set(0, abs(aaa[0] - aaa[1]))

    if aaa[0] == aaa[1]:
        min_stack = [(-INF, -1), (aaa[1], 1)]
        max_stack = [(INF, -1), (aaa[1], 1)]
    elif aaa[0] < aaa[1]:
        min_stack = [(-INF, -1), (aaa[0], 0), (aaa[1], 1)]
        max_stack = [(INF, -1), (aaa[1], 1)]
    else:
        min_stack = [(-INF, -1), (aaa[1], 1)]
        max_stack = [(INF, -1), (aaa[0], 0), (aaa[1], 1)]

    aaa.append(0)
    aaa.append(0)

    for i in range(2, n + 1):
        a = aaa[i]
        best = lst.prod(0, i - 1)
        lst.set(i, best + abs(aaa[i] - aaa[i + 1]))

        r = i - 1
        while min_stack[-1][0] >= a:
            b, j = min_stack.pop()
            if b > a:
                l = min_stack[-1][1] + 1
                lst.apply(l, r, b - a)
                r = l
        min_stack.append((a, i))

        r = i - 1
        while max_stack[-1][0] <= a:
            b, j = max_stack.pop()
            if b < a:
                l = max_stack[-1][1] + 1
                lst.apply(l, r, a - b)
                r = l
        max_stack.append((a, i))

    ans = lst.get(n)
    return ans


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