ユニークビジョンプログラミングコンテスト2023 クリスマス (AtCoder Beginner Contest 334) F,G問題メモ

ユニークビジョンプログラミングコンテスト2023 クリスマス (AtCoder Beginner Contest 334)

12/23開催なだけあって、クリスマスにちなんだ問題が多くてよき。

F - Christmas Present 2

問題

サンタが2次元座標上で $N$ 人の子どもたちにプレゼントを配る
サンタの家は $(S_x, S_y)$ に、子ども $i$ の家は $(x_i,y_i)$ にある
プレゼントを配る上での制約
- 子ども $1,2,...,N$ の順に届ける
- ソリにはプレゼントを $K$ 個までしか積めない。補充はサンタの家でのみできる
サンタが自分の家から出発し、全てのプレゼントを配り終えて自分の家に戻るまでの最短距離を求めよ
$1 \le K \le N \le 2 \times 10^5$

解法

ふんわりと、以下のようなDPでできそう。

$DP[i]$ （イメージ）= $i$ 軒目まで配り終えてサンタの家に戻った時の最短距離、みたいな値

$K$ 個までしか積めない＝最後に家に戻ったのが $K$ 軒前まででないといけない。
よって、 $DP[i]$ を求めたいとき、（DP配列をセグメント木などで実装して） $DP[i-K]～DP[i-1]$ の最小値を得たら $DP[i]$ が求まる、というようなことがしたい。

ただ、それだと上記の定義のままではダメ。
たとえば3軒目を訪ねるとき（ $DP[3]$ を埋めるとき）

DP[0]:  サ→①→②→③→...
        ~~                             ←DP[0]の値が示す移動

DP[1]:  サ→①→サ→②→③→...
        ~~~~~~~~~~                     ←DP[1]の値が示す移動
        
DP[2]:  サ→①→②→サ→③→...
        ~~~~~~~~~~~~~~                 ←┬小さい方がDP[2]の値が示す移動
  または                                 │
        サ→①→サ→②→サ→③→...      │
        ~~~~~~~~~~~~~~~~~~             ←┘

※サ: サンタの家

DPの示す値の最終位置がサンタの家だと、そこから3軒目に行くまでの距離がそれぞれ異なってしまうので、比較できない。

最終位置は、 $DP[3]$ を求める上では3軒目である必要がある。よって、DPを以下で定義しなおして、

$DP[i,j]=j$ 軒目の後に取りに戻って、そこからは取りに戻らず $j+1,...,i$ 軒目を順に訪れるまでの最短距離

DP[3,0]:  サ→①→②→③→...
          ~~~~~~~~~~~~~~

DP[3,1]:  サ→①→サ→②→③→...
          ~~~~~~~~~~~~~~~~~~

DP[3,2]:  サ→...→②→サ→③→...
          ~~~~~~~~~~~~~~~~~~~

これなら同条件で比較でき、 $DP[3,0]～DP[3,2]$ の最小値が、3軒目に配るまでの最短距離となっている。

次、1つ進めて $DP[4,*]$ を求めたいとき、

DP[4,0]:  サ→①→②→③→④→...
          ~~~~~~~~~~~~~~~~~~

DP[4,1]:  サ→①→サ→②→③→④→...
          ~~~~~~~~~~~~~~~~~~~~~~

DP[4,2]:  サ→...→②→サ→③→④→... （一例）
          ~~~~~~~~~~~~~~~~~~~~~~~

DP[4,3]:  サ→.......→③→サ→④→... （一例）
          ~~~~~~~~~~~~~~~~~~~~~~~

$DP[4,0]～DP[4,2]$ に関しては、 $DP[3,0]～DP[3,2]$ に新たに③→④の距離を加算すればよい。
$DP[4,3]$ に関しては、 $DP[3,*]$ の最小値に ③→サ→④ の距離を加算した値を新規追加すればよい。

これで4軒目までの最短距離も求められた。後は繰り返し。

実装上は $i$ の次元は省略して破壊的に更新していくとして、「区間加算更新」と「区間最小値クエリ」を処理できる遅延評価セグメント木でDPを実装すれば $O(N \log{N})$ で解ける。

$N+1$ 軒目に便宜的にサンタの家を入れておけば、 $i=N+1$ まで回した後の $DP[N]$ が答え。

Python3

        
          
          
              
              from operator import add
from typing import TypeVar, Generic, Callable, List
 
T = TypeVar('T')
U = TypeVar('U')
 
 
class LazySegmentTreeInjectable(Generic[T, U]):
    def __init__(self,
                 n: int,
                 identity_data: Callable[[], T],
                 identity_lazy: Callable[[], U],
                 operation: Callable[[T, T], T],
                 mapping: Callable[[T, U], T],
                 composition: Callable[[U, U], U],
                 ):
        self.n = n
        self.depth = n.bit_length()
        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() for _ in range(self.offset << 1)]
        self.lazy = [identity_lazy() for _ in range(self.offset)]
 
    @classmethod
    def from_array(cls,
                   arr: List[T],
                   identity_data: Callable[[], T],
                   identity_lazy: Callable[[], U],
                   operation: Callable[[T, T], T],
                   mapping: Callable[[T, U], T],
                   composition: Callable[[U, U], U],
                   ):
        ins = cls(len(arr), identity_data, identity_lazy, operation, mapping, composition)
        ins.data[ins.offset:ins.offset + ins.n] = arr
        for i in range(ins.offset - 1, 0, -1):
            ins.update(i)
        return ins
 
    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: U) -> 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: U) -> 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) -> T:
        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: T) -> 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) -> T:
        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('{: 4f}'.format, self.data[i:i * 2]))
            i <<= 1
        i = 1
        while i <= self.offset:
            print(*map('{: 4f}'.format, self.lazy[i:i * 2]))
            i <<= 1
 
 
n, k = map(int, input().split())
sx, sy = map(int, input().split())
direct = [0]
sequence = []
px, py = 0, 0
for _ in range(n):
    x, y = map(int, input().split())
    direct.append(((sx - x) ** 2 + (sy - y) ** 2) ** 0.5)
    sequence.append(((px - x) ** 2 + (py - y) ** 2) ** 0.5)
    px = x
    py = y
direct.append(0)
sequence.append(0)
sequence[0] = 0
 
identity_data = lambda: float('inf')
identity_lazy = float
operation = min
mapping = add
composition = add
 
dp = LazySegmentTreeInjectable(n + 1, identity_data, identity_lazy, operation, mapping, composition)
dp.point_set(0, direct[1])
for i in range(1, n + 1):
    l = max(0, i - k)
    best = dp.range_query(l, i)
 
    dp.point_set(i, best + direct[i] + direct[i + 1])
    dp.range_update(l, i, sequence[i])
 
ans = dp.point_get(n)
print(ans)

            

        
      

G - Christmas Color Grid 2

問題

$H \times W$ の、白黒で塗られたグリッドが与えられる
黒を、1つだけ一様ランダムに選んで白にする
縦横につながった黒を1つの連結成分とする（ナナメ不可）とき、連結成分数の期待値を求めよ
$1 \le H,W \le 1000$

解法

期待値の分母は「初期状態の黒マス数」でわかりきっているので、分子である「各黒マスを消したときの連結成分数の総和」が求まればよい。

黒マスを頂点と見なし、隣接した黒の間に辺を張ったグラフで、関節点と橋を求める。

これらは、lowlink という概念で、1回のDFSでまとめて求められる。

橋/関節点(LowLink) | Luzhiled’s memo

初期状態の連結成分数を $C$ とする。

関節点でない場合

「関節点＝そいつを消したら連結成分数が増える頂点」なので、逆に関節点でなければ連結成分は増えず $C$ のまま変わらない。

ただしそいつが、元から1マスで1つの連結成分を構成していた場合、1減って $C-1$ となる。

関節点の場合

関節点なら、そこから出ている辺の本数と、橋の本数を見る。

(a)全ての辺が橋なら、連結成分は「橋の本数-1」増えて  C+橋の本数-1

   ###            ###
    |
###-#-###  →  ###   ###
    |
   ###            ###


(b)そうで無い場合、橋があるなら、橋の本数分増える。 C+橋の本数

#####          #####      橋でない連結成分が1つ残ったまま、
#   |          #          橋の本数分だけ新たな連結成分ができる
###-#-###  →  ###   ###
    |
   ###            ###


(c)橋が0本の場合、必ず以下のような形となっている。
2本ずつ出る辺が、それぞれペアになってくっついている。

#####          #####
#   |          #
###-#-###  →  ###   ###
    |   #              #
    #####          #####

よって、この場合は真ん中を消すと2つに分かれ、連結成分数は1増えて C+1 となる。

(b)(c) の場合、連結成分の増減は、グリッドグラフに限った話である点に注意する。
この問題ではよいが、一般のグラフだと成り立たない。

グリッドグラフの最大次数が4であることを利用しているので、例えば三つ葉のクローバー（♣の茎を取った形）のようなグラフの真ん中（次数6）を消すと、橋が0本と (c) と似たような状況ではあるが3つに分かれる。

一般の場合、関節点と橋の情報だけでは計算できないが、それらを求める際に計算した、DFS木とlowlinkに立ち返ればチェックできる。（公式Editorial参照）

Python3

        
          
          
              
              from operator import add
from typing import TypeVar, Generic, Callable, List
 
T = TypeVar('T')
U = TypeVar('U')
 
 
class LazySegmentTreeInjectable(Generic[T, U]):
    def __init__(self,
                 n: int,
                 identity_data: Callable[[], T],
                 identity_lazy: Callable[[], U],
                 operation: Callable[[T, T], T],
                 mapping: Callable[[T, U], T],
                 composition: Callable[[U, U], U],
                 ):
        self.n = n
        self.depth = n.bit_length()
        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() for _ in range(self.offset << 1)]
        self.lazy = [identity_lazy() for _ in range(self.offset)]
 
    @classmethod
    def from_array(cls,
                   arr: List[T],
                   identity_data: Callable[[], T],
                   identity_lazy: Callable[[], U],
                   operation: Callable[[T, T], T],
                   mapping: Callable[[T, U], T],
                   composition: Callable[[U, U], U],
                   ):
        ins = cls(len(arr), identity_data, identity_lazy, operation, mapping, composition)
        ins.data[ins.offset:ins.offset + ins.n] = arr
        for i in range(ins.offset - 1, 0, -1):
            ins.update(i)
        return ins
 
    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: U) -> 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: U) -> 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) -> T:
        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: T) -> 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) -> T:
        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('{: 4f}'.format, self.data[i:i * 2]))
            i <<= 1
        i = 1
        while i <= self.offset:
            print(*map('{: 4f}'.format, self.lazy[i:i * 2]))
            i <<= 1
 
 
n, k = map(int, input().split())
sx, sy = map(int, input().split())
direct = [0]
sequence = []
px, py = 0, 0
for _ in range(n):
    x, y = map(int, input().split())
    direct.append(((sx - x) ** 2 + (sy - y) ** 2) ** 0.5)
    sequence.append(((px - x) ** 2 + (py - y) ** 2) ** 0.5)
    px = x
    py = y
direct.append(0)
sequence.append(0)
sequence[0] = 0
 
identity_data = lambda: float('inf')
identity_lazy = float
operation = min
mapping = add
composition = add
 
dp = LazySegmentTreeInjectable(n + 1, identity_data, identity_lazy, operation, mapping, composition)
dp.point_set(0, direct[1])
for i in range(1, n + 1):
    l = max(0, i - k)
    best = dp.range_query(l, i)
 
    dp.point_set(i, best + direct[i] + direct[i + 1])
    dp.range_update(l, i, sequence[i])
 
ans = dp.point_get(n)
print(ans)

            

        
      