AtCoder Beginner Contest 435 E,F,G問題メモ

AtCoder Beginner Contest 435

Fまでは比較的簡単だったので、そこまでの速解き勝負となった人も多そう。
簡単というか、「頻出のデータ構造さえ知っていれば、それに問題を当てはめる発想は比較的思いつきやすい」というか。

E - Cover query

問題文

$N$ 個のマスが左右一列に並んでいます。最初、すべてのマスは白く塗られています。
$Q$ 個のクエリが与えられるので、順に処理してください。
- $2$ つの整数 $(L_i,R_i)$ $(1\leq L_i\leq R_i\leq N)$ が与えられる。
- マス $L_i, L_i+1, \ldots, R_i$ をすべて黒く塗る。
- このとき、元々白く塗られていたマスは新しく黒く塗られ、元々黒く塗られていたマスはそのままとなる。
その後、（$N$ 個のマスのうち）白く塗られているマスの個数を求める。

制約

$1\leq N\leq 10^9$
$1\leq Q\leq 2\times 10^5$
$1\leq L_i\leq R_i\leq N$
入力はすべて整数

解法

座標圧縮して遅延セグメント木。

$N$ が大きくなければ、以下のような遅延セグメント木で解ける。

最初、$N$ 個の要素（マス）を全て $1$ で初期化する
クエリ $i$ では、$[L_i,R_i]$ を $0$ で上書き更新する
その後、全体の総和を出力する

今回は $N$ が大きいのでそのままでは無理だが、座標圧縮すれば大丈夫。

マスを0-indexedとする。
「$0$」「$N$」「$L_i-1$ または $R_i$ として出現する数」の集合を小さい順に $0=A_0 \lt A_1 \lt ... \lt A_k=N$ とする。

$i=0,1,...,k-1$ に対し、マスの区間 $[A_i,A_{i+1})$ は常に同じ色となるので、まとめて更新できる。

最初、$k$ 個の要素（区間）をそれぞれ $(A_{i+1}-A_i)$ で初期化する
クエリ $i$ では、$L_i,R_i$ に相当する $A$ の添字を $l,r$ として、$[l,r)$ を $0$ で上書き更新する
その後、全体の総和を出力する

Python3

from operator import add

from atcoder.lazysegtree import LazySegTree


def solve(n, q, queries):
    coords = {0, n}
    for l, r in queries:
        coords.add(l - 1)
        coords.add(r)
    coords = sorted(coords)
    coord_mapping = {x: i for i, x in enumerate(coords)}

    mapping = lambda a, b: 0 if a else b
    composition = lambda a, b: a or b
    init = [x1 - x0 for x0, x1 in zip(coords, coords[1:])]

    lst = LazySegTree(add, 0, mapping, composition, False, init)

    buf = []
    for l, r in queries:
        l -= 1
        li = coord_mapping[l]
        ri = coord_mapping[r]
        lst.apply(li, ri, True)
        buf.append(lst.all_prod())
    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)))

解法2

上記の座標圧縮はクエリの先読みが必須となる。

先読みができないという場合は、公式Editorial のように、「区間を順序付き集合で管理する」テクが使える。

F - Cat exercise

問題文

$N$ 個のキャットタワーが左右一列に等間隔で並んでいます。
- 左から $i$ 番目 $(1\leq i\leq N)$ のタワーの高さは $P_i$ です。
- ここで、$(P_1,P_2,\ldots,P_N)$ は $(1,2,\ldots,N)$ の並び替えとなっています。
- また、左から $i$ 番目のタワーと $j$ 番目のタワーの間の距離を $\lvert i-j\rvert$ で定義します。
猫が一匹おり、最初、高さ $N$ のキャットタワーの上にいます。
高橋君はタワーを一つ選んで撤去することを繰り返すことで、この猫を運動させたいです。
高橋君がタワーを撤去するとき、猫は以下のように移動します。
- 撤去するタワーの上に猫がいない場合、猫は移動しません。
- 撤去するタワーの上に猫がおり、かつそのタワーと左右に隣接するタワーのうち少なくとも一方が存在するとき、撤去されるタワーからスタートして隣接するタワーへの移動を繰り返して到達できるタワーのうち、撤去されるタワーを除いて最も高いタワーに猫が移動します。このとき、移動前と移動後のタワーの間の距離だけ移動が発生します（移動前後および途中のタワーの高さは関係しません）。
- 撤去するタワーの上に猫がおり、かつそのタワーと左右に隣接するタワーが存在しないとき、猫は高橋君の腕の中に飛び込み、運動はここで終了となります。このときには移動は発生しません。

ここで、撤去したタワーの間は詰めることはありません。すなわち、最初の時点で左から $i$ 番目のタワーと隣接しているタワーは（存在すれば）左から $(i-1)$ 番目と $(i+1)$ 番目のタワーのみであり、その後他のタワーの撤去によって新しく他のタワーと隣接するようになることはありません。
運動が終了するまでの猫の移動距離の合計としてあり得る最大の値を求めてください。

制約

$1\leq N\leq 2\times 10^5$
$(P_1,P_2,\ldots, P_N)$ は $(1,2,\ldots,N)$ の並び替えである。
入力はすべて整数

解法

F問題にしては比較的素直な観察でDPが見える。

$\mathrm{DP}[h]:=$ 高さ $h$ のタワーの上に猫がいる状態における、猫の移動距離の最大値

単純に、高さ $h$ のタワーを「タワー $h$」とする。

まず最初、タワー $N$ には移動距離 $0$ の状態でいる。

P   5  3  4  1  2
DP  0  -  -  -  -

タワー $4$ には、タワー $5$ から移動することで到達できる。その時、移動距離は $2$ となる。

P   5  3  4  1  2
DP  0  -  2  -  -

タワー $3$ には2通りの方法がある。

タワー $4$ に猫がいる状態から、タワー $4$ を撤去して移動させる
猫がタワー $5$ にいる状態で、先にタワー $4$ を除いておいてから、タワー $5$ を撤去する

$i$ までの移動距離は「$\mathrm{DP}[移動元のタワー] + そこからの移動距離$」で計算できる。
今回の場合、タワー $4$ からの方が大きくなる。

P   5  3  4  1  2
DP  0  3  2  -  -

次、タワー $2$ へは、実はタワー $4$ からしか移動することがない。
$3$ や $5$ から移動するには、高さの制約上、その前に $4$ が撤去されている必要があるが、そうすると「隣接するタワーへの移動を繰り返して到達可能」という制約を満たせなくなる。

P   5  3  4  1  2
DP  0  3  2  -  4

タワー $1$ へはタワー $2$ か $4$ から移動でき、$2$ からの方が大きくなる。

P   5  3  4  1  2
DP  0  3  2  5  4

答えは、DPの値の中で最大の $5$ となる。

以上のシミュレーションから、タワー $h$ には、以下のどちらかからのみ遷移できる、ということがわかる。

タワー $h$ より左で $h$ より高いタワーのうち、最も近いタワー（存在すれば）
タワー $h$ より右で $h$ より高いタワーのうち、最も近いタワー（存在すれば）

$\mathrm{DP}[h]$ を $h$ の大きい方から確定させていく過程で、 SortedSet などに既にチェックしたタワーの存在する位置 $i$ を放り込んでおき、現在着目中のタワー $h'$ の位置 $i'$ で二分探索すれば、左右から遷移元とできるタワーの位置を得ることができる。

Python3

from sortedcontainers import SortedSet


def solve(n, ppp):
    pos = [0] * n
    ppp = [p - 1 for p in ppp]
    for i, p in enumerate(ppp):
        pos[p] = i

    dp = [0] * n
    ss = SortedSet()
    for h in range(n - 1, -1, -1):
        i = pos[h]
        ri = ss.bisect(i)
        li = ri - 1
        tmp = 0
        if li >= 0:
            l = ss[li]
            tmp = max(tmp, dp[l] + (i - l))
        if ri < len(ss):
            r = ss[ri]
            tmp = max(tmp, dp[r] + (r - i))
        ss.add(i)
        dp[i] = tmp

    ans = max(dp)
    return ans


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

G - Domino Arrangement

問題文

$1$ から $N$ の番号がついた $N$ 個のマスがあります。最初、どのマスも色が塗られていません。
$M$ 種類の色があり、$i$ 番目の色ではマス $L_i,L_i+1,\ldots,R_i$ のうち好きなマスを好きな個数塗ることができます。
以下の条件を満たす色の塗り方は何通りあるか、$998244353$ で割った余りを求めてください。
- どのマス $i$ についても、そのマスに色が塗られているならば、マス $i-1,i+1$ のうちちょうど一方がマス $i$ と同じ色で塗られている。
- ただし、マス $0,N+1$ はどの色にも塗られていないとみなす。

制約

$1\leq N,M \leq 5\times 10^5$
$1\leq L_i \leq R_i \leq N$
入力は全て整数

解法

かなり遷移が複雑な包除原理DP。
方針はわかっても、時間内に実装できず。

問題文を要約すると、「隣り合う2マスを1組として同じ色で塗ってね」「違う色は隣接してもいいけど、同じ色の組は隣接させないでね」となる。

OK            NG
□●●■■□  □●□■●■
□●●□●●  □●●●●□

大まかな方針としては、

$\mathrm{DP}_{イメージ}[i]:=$ マス $i$ までの塗り方の個数
- ※マス $i$ が塗られていないか、塗られているとしたら右側のマスになっているもののみ数える

のようなDPで、塗らない場合は1マス前、塗る場合は2マス前から｛区間的に有効な色数｝倍で遷移する、というようなものが思いつくが、厄介なのが「最後に塗った色と同じ色を塗る遷移はできない」という点になる。上記のDPは区別すべき状態が混ざってしまっている。

かといって最後に塗った色で場合分けすると状態数も遷移も $M$ 倍の $O(NM^2)$ となるので全然無理。

代わりに、「同じ色の組が隣接してしまっている箇所数」毎に数えて包除原理を適用することを考える。

$\mathrm{DP}_{仮}[i,j]:=$ マス $i$ までの隣接を許した塗り方のうち、同じ色の組が隣接している箇所が少なくとも $j$ 個あるような塗り方の個数

最終的に $\mathrm{DP}_{仮}[N]$ の $j$ が偶数を正、奇数を負で足し合わせると答えとなる。

ここで、$j$ を素直に持つと状態数が $O(N^2)$ 必要になるが、最終的に必要なのは正と負の差分なので、

$\mathrm{DP}[i]:=\mathrm{DP}_{仮}[i]$ のうち「$j$ が偶数のもの」－「$j$ が奇数のもの」

のようにすると情報を圧縮できる。

遷移は、以下のように明示的に隣接させる箇所を一気に塗ることを考える。
たとえば $i-6$ からの遷移は、■■■■■■ のように、 3組連続して同じ色で塗る（2箇所、連続する箇所を増やす）ような塗り方をすることを表す。

ある色 c についての遷移

       |----色cが有効な区間--------->.... 
 i-10    i-8    i-6    i-4    i-2    i
          |      |      |      `-正--^
          `- 負 -`- 正 -`--- 負 -----'    ← DP[i-○] から DP[i] への寄与の正負

ただこれ、色によって有効な区間が変わるのだが、色ごとに遷移させていたら位置 $i$ ごとに $O(M)$ かかるし、 $i-2,i-4,...$ を素直に遡っていたらさらに $O(N)$ かかる。

これをまとめて持っておくことで高速化する。
つまり、現在有効な全ての色、全ての位置からの寄与の合計を、計算済みの値として持っておく。

$T[i]:=\mathrm{DP}[i+2]$ への、全ての色・全ての位置（$i,i-2,i-4,...$）からの寄与の合計

もし $T$ を適切に管理・更新できるなら、以下のように簡単に遷移が計算できるようになる。

$\mathrm{DP}[i]=\mathrm{DP}[i-1]+T[i-2]$
- ※$\mathrm{DP}[i-1]$ は、色を塗らない場合の遷移

$T$ の更新を考える。仮に $i$ と $i+2$ で有効な色が変わらない場合、寄与の合計は以下のようになる。

T[i-2] に含まれるDPのindexと寄与の正負
     i-10   i-8    i-6    i-4    i-2    i
色1          負     正     負     正
色2                 正     負     正
色3   正     負     正     負     正
 
T[i] に含まれるDPのindexと寄与の正負
     i-10   i-8    i-6    i-4    i-2    i    i+2
色1          正     負     正     負    正
色2                 負     正     負    正
色3   負     正     負     正     負    正

よって、以下で計算できることが分かる。

$T[i] = (\mathrm{DP}[i]×有効な色数) - T[i-2]$

実際には、$i$ から $i+2$ にかけて、新たに有効になる色、有効な区間が終わる色がある。
その差分を考える。

有効な色が変わる場合の、T[i] に含まれるDPのindexと寄与の正負
     i-10   i-8    i-6    i-4    i-2    i    i+2
色1          ×     ×     ×     ×             ←終わる
色2                 負     正     負    正
色3   負     正     負     正     負    正
色4                                     正       ←始まる

開始する分に関しては、（$T[i]$ を計算する前に）$L_j = i+1$ であるような $j$ の個数だけ、有効な色数を増やせばよい。
$i$ からの遷移では、$i$ は既に塗りおえていて $i+1$ から塗ることを想定しているので、色は $i+1$ から有効であればよい。

終了する分に関しても、ひとまずは $R_j = i+1$ であるような $j$ の個数だけ、有効な色数を減らす。
$i+1$ で終了するような色は $i+2$ に遷移できないので、$i$ の時点で終了としてよい。

有効な色数を更新して計算した $T[i]$ には、しかし、終了する色の分の寄与（上図「×」印）が余分に含まれてしまっている。
終了する各色の開始位置まで遡っての、正負正負… の和を除きたい。

$i$ の偶奇別に、正負交互に $\mathrm{DP}[i]$ の累積和を取っておけば、任意の区間の正負交互の $\mathrm{DP}$ の和（交代和）を得られる。
終了する色の区間が $(L_j,R_j)$ だとして、$[L_j,i)$ の交代和を $T[i]$ から除けばよい。

ただし、$T[i]$ から除くのは「$i-2$ を負と扱う時」の交代和なので、適宜、正負反転させる。除く値の正負を取り違えないように注意。

また、終了する色の寄与は、別途 $T[i+1]$（$i$ と偶奇が異なる系統）からも除かなくてはならない。

これで $T$ を色ごとに $O(1)$、全体を通して $O(N+M)$ で更新できるようになったので、間に合う。

Python3

以下の実装では累積和に FenwickTree を使っているため $O(N+M \log{N})$ となっているが、これは単純にリストに置き換え可能。

class FenwickTreeInjectable:
    def __init__(self, n, identity_factory, func):
        self.size = n
        self.tree = [identity_factory() for _ in range(n + 1)]
        self.func = func
        self.idf = identity_factory
        self.depth = n.bit_length()

    def add(self, i, x):
        i += 1
        tree = self.tree
        func = self.func
        while i <= self.size:
            tree[i] = func(tree[i], x)
            i += i & -i

    def sum(self, i):
        i += 1
        s = self.idf()
        tree = self.tree
        func = self.func
        while i > 0:
            s = func(s, tree[i])
            i -= i & -i
        return s

    def lower_bound(self, x, lt):
        """
        累積和がx以上になる最小のindexと、その直前までの累積和

        :param lt: lt(a, b) で a < b ならTrueを返す関数
        """
        total = self.idf()
        pos = 0
        tree = self.tree
        func = self.func
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k > self.size:
                continue
            new_total = func(total, tree[k])
            if lt(new_total, x):
                total = new_total
                pos += 1 << i
        return pos + 1, total

    def debug_print(self):
        prev = 0
        arr = []
        for i in range(self.size):
            curr = self.sum(i)
            arr.append(curr - prev)
            prev = curr
        print(arr)


def solve(n, m, areas):
    if n == 1:
        return 1

    MOD = 998244353
    add = lambda a, b: (a + b) % MOD

    fwt_odd = FenwickTreeInjectable(n + 5, int, add)
    fwt_evn = FenwickTreeInjectable(n + 5, int, add)
    openings = [0] * (n + 1)
    closings = [0] * (n + 1)
    closing_pair = [[] for _ in range(n + 1)]
    for l, r in areas:
        if l == r:
            continue
        openings[l - 1] += 1
        closings[r - 1] += 1
        closing_pair[r - 1].append(l)
        closing_pair[r].append(l)

    nocolor = 1
    dp = [0] * (n + 1)
    mv = [0] * (n + 1)

    available = openings[0]
    dp[0] = 1
    mv[0] = available
    fwt_evn.add(0, 1)

    available += openings[1] - closings[1]
    dp[1] = 1
    mv[1] = available
    fwt_odd.add(1, 1)

    for i in range(2, n + 1):
        oe = i % 2
        pn = (i // 2) % 2

        colored = mv[i - 2]
        if pn == 0:
            colored = -colored % MOD

        dp[i] = nocolor + colored
        dp[i] %= MOD
        nocolor = dp[i]
        available += openings[i]
        available -= closings[i]
        tmp = dp[i] * available - colored

        for l in closing_pair[i]:
            if oe == 0:
                tmp2 = fwt_evn.sum(i) - fwt_evn.sum(l - 2)
            else:
                tmp2 = fwt_odd.sum(i) - fwt_odd.sum(l - 2)
            if pn == 0:
                tmp -= tmp2
            else:
                tmp += tmp2

        if pn == 1:
            tmp = -tmp
        mv[i] = tmp % MOD

        if oe == 0:
            if pn == 0:
                fwt_evn.add(i, dp[i])
            else:
                fwt_evn.add(i, -dp[i])
        else:
            if pn == 0:
                fwt_odd.add(i, dp[i])
            else:
                fwt_odd.add(i, -dp[i])

    return dp[n]


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

目次

AtCoder Beginner Contest 435 E,F,G問題メモ

E - Cover query

問題文

制約

解法

解法2

F - Cat exercise

問題文

制約

解法

G - Domino Arrangement

問題文

制約

解法