AtCoder Beginner Contest 441 (Promotion of Engineer Guild Fes)F,G問題メモ

AtCoder Beginner Contest 441 (Promotion of Engineer Guild Fes)

F - Must Buy

問題文

ある店に $N$ 個の商品が売られています。
- 商品 $i$ $(1\leq i\leq N)$ の値段は $P_i$ 円で、価値は $V_i$ です。どの商品も $1$ つずつしか存在しません。
高橋君は、値段の合計が $M$ 円以下となる範囲でいくつかの商品を選びます。
このとき、$1\leq i\leq N$ それぞれについて、商品 $i$ が以下の $3$ つの分類のどれに該当するか判定してください。
- 分類 A: $M$ 円以下で選んだ商品の価値の合計を最大にするには、その商品を必ず選ばなければならない。
- 分類 B: $M$ 円以下で選んだ商品の価値の合計を最大にするには、その商品を選んでも選ばなくてもよい。
- 分類 C: $M$ 円以下で選んだ商品の価値の合計を最大にするには、その商品を決して選んではならない。

制約

$1\leq N\leq 1000$
$1\leq M\leq 5\times 10^4$
$1\leq P_i\leq M$
$1\leq V_i\leq 10^9$
入力はすべて整数

解法

ナップサック問題の応用。
まずは、何を示せば「その商品を必ず選ばなければならない」と言えるのか、をちゃんと理解しないと始まらない。

以下の①②を考えて、

①商品 $i$ を選ばなかった場合の最大価値
- $i$ 以外の $N-1$ 個の商品から、$M$ 円以下で選ぶ時の最大価値
②商品 $i$ を選ぶ場合の最大価値
- $i$ 以外の $N-1$ 個の商品から、$M-P_i$ 円以下で選ぶ時の最大価値 $+V_i$

①<②ならA、①=②ならB、①>②ならCとなる。

しかし、ナップサックは「全体のDPを求めておいて、後から $i$ を選ばなかったことにする」みたいなことはできない。
当然、$i$ ごとに毎回 $O(N)$ かけるわけにもいかない。

代わりに、前からと後ろからのDPを保存しておいて、「$1～i-1$ の結果と $i+1～N$ の結果をマージする」という解法が使える。

前計算として、以下を $i=N,N-1,...$ の順に求めておく。

$\mathrm{DP_{backward}}[i,j]:=i～N$ のアイテムを使って、$j$ 円以下で達成できる最大価値

$i=1,2,...,N$ の順に、以下のDPを計算していく。

$\mathrm{DP_{forward}}[i,j]:=1～i$ のアイテムを使って、$j$ 円以下で達成できる最大価値

それと同時に、$i$ について答えを求める。

①
- $j=0～M$ について、$\mathrm{DP_{forward}}[i-1,j] + \mathrm{DP_{backward}}[i+1,M-j]$ の最大値
②
- $j=0～M-P_i$ について、$\mathrm{DP_{forward}}[i-1,j] + \mathrm{DP_{backward}}[i+1,M-j-P_i]$ の最大値 $+ V_i$

前後からのDPの計算、および答えを求めるパート、いずれも $i$ ごとに $O(M)$ なので、全体 $O(NM)$ で求められる。

いつもナップサックは破壊的更新で解いていたので、途中も全て記録する $(i,j)$ 2次元のナップサックをおこなったとき、一部の $j$ について更新し忘れが発生して、時間ロスした。

$j=0,1,...,M-P_i$ について以下のように更新するとき

$\mathrm{DP_{backward}}[i,j+P_i] =\max(\mathrm{DP_{backward}}[i,j+P_i], \mathrm{DP_{backward}}[i+1,j]+V_i)$

$j=0,1,...,P_i-1$ については、$i+1$ のままの値をちゃんと継承しなきゃいけない。忘れがち。

$\mathrm{DP_{backward}}[i,j] = \mathrm{DP_{backward}}[i+1,j]$

Python3

def solve(n, m, items):
    bwd = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n - 1, -1, -1):
        p, v = items[i]
        for j in range(m - p, -1, -1):
            bwd[i][j + p] = max(bwd[i + 1][j + p], bwd[i + 1][j] + v)
        for j in range(p):
            bwd[i][j] = bwd[i + 1][j]

    fwd = [0] * (m + 1)
    ans = []
    for i in range(n):
        p, v = items[i]

        not_use_best = 0
        for j in range(m + 1):
            not_use_best = max(not_use_best, fwd[j] + bwd[i + 1][m - j])
        use_best = 0
        for j in range(m - p + 1):
            use_best = max(use_best, fwd[j] + bwd[i + 1][m - j - p])
        use_best += v

        if not_use_best < use_best:
            ans.append('A')
        elif not_use_best == use_best:
            ans.append('B')
        else:
            ans.append('C')

        for j in range(m - p, -1, -1):
            fwd[j + p] = max(fwd[j + p], fwd[j] + v)

    return ''.join(ans)


n, m = list(map(int, input().split()))
items = [list(map(int, input().split())) for _ in range(n)]
ans = solve(n, m, items)
print(ans)

G - Takoyaki and Flip

問題文

$N$ 枚の皿が左から右に一直線状に並んでいます。
はじめ、どの皿も表を上にして置かれており、どの皿にもたこ焼きが置かれていません。
次の $3$ 種類のクエリを合計 $Q$ 回処理してください。
- タイプ $1$：整数 $L,R,X$ が与えられる。
  - $i=L,L+1,\ldots,R$ に対して、皿 $i$ が表を上にして置かれている時のみ、皿 $i$ にたこ焼きを $X$ 個置く。
- タイプ $2$：整数 $L,R$ が与えられる。
  - $i=L,L+1,\ldots,R$ に対して、皿 $i$ にたこ焼きが $1$ 個以上置かれていた場合、皿 $i$ に置かれているたこ焼きをすべて食べる。その後、皿 $i$ をひっくり返す。
- タイプ $3$：整数 $L,R$ が与えられる。
  - 皿 $L,$ 皿 $L+1,\ldots,$ 皿 $R$ にわたる、置かれているたこ焼きの個数の最大値を出力する。

制約

$1\le N\le2\times10 ^ 5$
$1\le Q\le2\times10 ^ 5$
すべてのクエリにおいて、$1\le L\le R\le N$
タイプ $1$ のクエリにおいて、$1\le X\le10 ^ 9$
タイプ $3$ のクエリが存在する。
入力はすべて整数

解法

実行制限時間の制約が厳しめだった。（Pythonは、AC提出がほぼ全てCodon）
想定外の解法の防止などもあるのかもしれないが、もうちょっと長くしてくれると嬉しい。。。3秒でも良くない？

範囲更新クエリがいっぱいあるので、とりあえず遅延セグ木に乗るかどうかをまず検討する。
その結果、やっぱり乗るのでよかったね、という問題。

クエリ1,2を処理するには、各区間を表すセグ木のノードにどのような情報を持たせれば良いか？を考える。

全体として
- クエリ3に答えるために、区間内の「たこ焼きの最大値」は必要
クエリ1
- 区間内の表の皿に一律に $X$ 個のたこ焼きを追加する
- 表の皿が1枚でもあれば、最大値は $X$ 増える。0枚なら増えない。
- →「表の皿の枚数」があれば適切に処理できる。
クエリ2
- 「たこ焼きの最大値」は一律 $0$ になる。
- 「表の皿の枚数」を適切に更新するため、「区間長」が必要となる。

よって、（たこ焼き最大値, 表の皿の枚数, 区間長）があればよさそう。

作用素同士のマージも考える。
クエリ2が来たら、たこ焼きは全て消えるのでそれまでのクエリ1は全て意味が無くなる。重要なのは、

クエリ2が来たかどうか。来た場合は回数の偶奇
最後のクエリ2が来てからの、クエリ1による $X$ の総和

作用素はこの2つで表せば、少し複雑なものの作用素同士のマージも計算できる。

Python3

class LazySegmentTreeInjectableForCodon:
    """ Codon でコンパイル可能な遅延セグ木

    * ジェネリクス型などまだ未対応のものが多いので、型指定は省略。
    * int.bit_length の代わりに int.__ctlz__ を使って log2 を計算（そのため通常Pythonでは動かない）
    * identity_data, identity_lazy は、生成関数ではなく、イミュータブルな（コピーしたら別オブジェクトとなる）値を直接渡す。
      * 別に生成関数でもいいのだが、Codon では、data, lazy の型が決まっているなら、list より tuple で実装した方が速い。
    """

    def __init__(self,
                 n: int,
                 identity_data,
                 identity_lazy,
                 operation,
                 mapping,
                 composition,
                 ):
        self.n = n
        self.depth = 64 - n.__ctlz__()
        self.offset = 1 << self.depth
        self.identity_data = identity_data
        self.identity_lazy = identity_lazy
        self.operation = operation
        self.mapping = mapping
        self.composition = composition
        self.data = [identity_data] * (self.offset << 1)
        self.lazy = [identity_lazy] * self.offset

    def init(self, aaa):
        for i in range(self.n):
            self.data[i + self.offset] = aaa[i]
        for i in range(self.offset - 1, 0, -1):
            self.update(i)

    def push(self, i: int) -> None:
        if i < self.offset:
            data = self.data
            lazy = self.lazy
            lz = lazy[i]

            lch = i << 1
            rch = lch + 1
            data[lch] = self.mapping(data[lch], lz)
            data[rch] = self.mapping(data[rch], lz)
            if lch < self.offset:
                lazy[lch] = self.composition(lazy[lch], lz)
                lazy[rch] = self.composition(lazy[rch], lz)
            lazy[i] = self.identity_lazy

    def update(self, i: int) -> None:
        lch = i << 1
        rch = lch + 1
        self.data[i] = self.operation(self.data[lch], self.data[rch])

    def all_apply(self, i: int, d) -> None:
        self.data[i] = self.mapping(self.data[i], d)
        if i < self.offset:
            self.lazy[i] = self.composition(self.lazy[i], d)

    def propagate(self, l: int, r: int) -> None:
        for i in range(self.depth, 0, -1):
            if ((l >> i) << i) != l:
                self.push(l >> i)
            if ((r >> i) << i) != r:
                self.push((r - 1) >> i)

    def range_update(self, l: int, r: int, d) -> None:
        l += self.offset
        r += self.offset
        self.propagate(l, r)

        l2 = l
        r2 = r
        while l < r:
            if (l & 1) == 1:
                self.all_apply(l, d)
                l += 1
            if (r & 1) == 1:
                r -= 1
                self.all_apply(r, d)
            l >>= 1
            r >>= 1
        l = l2
        r = r2

        for i in range(1, self.depth + 1):
            if ((l >> i) << i) != l:
                self.update(l >> i)
            if ((r >> i) << i) != r:
                self.update((r - 1) >> i)

    def range_query(self, l: int, r: int):
        l += self.offset
        r += self.offset

        self.propagate(l, r)
        sml = self.identity_data
        smr = self.identity_data
        while l < r:
            if (l & 1) == 1:
                sml = self.operation(sml, self.data[l])
                l += 1
            if (r & 1) == 1:
                r -= 1
                smr = self.operation(self.data[r], smr)
            l >>= 1
            r >>= 1
        return self.operation(sml, smr)

    def point_set(self, p: int, d) -> None:
        p += self.offset
        for i in range(self.depth, 0, -1):
            self.push(p >> i)
        self.data[p] = d
        for i in range(1, self.depth + 1):
            self.update(p >> i)

    def point_get(self, p: int):
        p += self.offset
        for i in range(self.depth, 0, -1):
            self.push(p >> i)
        return self.data[p]

    def debug_print(self) -> None:
        i = 1
        while i <= self.offset:
            print(*map('{: 4d}'.format, self.data[i:i * 2]))
            i <<= 1
        i = 1
        while i <= self.offset:
            print(*map('{: 4d}'.format, self.lazy[i:i * 2]))
            i <<= 1


def solve(n, q, queries):
    def merge(a, b):
        return (a[0] + b[0], a[1] + b[1], max(a[2], b[2]))

    def mapping(b, a):
        a0, a1 = a
        b0, b1, b2 = b
        if a0 == 1:
            b1 = b0 - b1
            b2 = 0
        elif a0 == 2:
            b2 = 0
        if b1 > 0:
            b2 += a1
        return (b0, b1, b2)

    def composition(b, a):
        if a[0] == 0:
            return (b[0], a[1] + b[1])
        if b[0] % 2 == 0:
            return (a[0], a[1])
        if a[0] == 1:
            return (2, a[1])
        return (1, a[1])

    lst = LazySegmentTreeInjectableForCodon(
        n, identity_data=(0, 0, 0), identity_lazy=(0, 0),
        operation=merge, mapping=mapping, composition=composition)
    init = [(1, 1, 0)] * n
    lst.init(init)

    buf = []
    for query in queries:
        if query[0] == 1:
            _, l, r, x = query
            l -= 1
            lst.range_update(l, r, (0, x))
        elif query[0] == 2:
            _, l, r = query
            l -= 1
            lst.range_update(l, r, (1, 0))
        else:
            _, l, r = query
            l -= 1
            _, _, ans = lst.range_query(l, r)
            buf.append(ans)

    return buf


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

目次

AtCoder Beginner Contest 441 (Promotion of Engineer Guild Fes)F,G問題メモ

F - Must Buy

問題文

制約

解法

G - Takoyaki and Flip

問題文

制約

解法