AtCoder Beginner Contest 353 F,G問題メモ

AtCoder Beginner Contest 353

F - Tile Distance

問題

座標平面に $1 \times 1$ の小タイルと $K \times K$ の大タイルが市松模様状に敷き詰められている（詳細は問題ページ参照）
$(S_x+0.5,S_y+0.5)$ から $(T_x+0.5,T_y+0.5)$ への移動コストを求めよ
移動は上下左右に整数値ずつ進むことができ、新しいタイルに乗るたびにコストが1かかる
$1 \le K \le 10^{16}$

解法

コーナーケースの発見力が問われる問題。

まず、始点と終点が離れていたら、基本的には大タイルを通っていくのがコストを節約できる。

┼─┬─┬─┼─┴─┴─┼
│  │  │  │          │
├─┼─┼─┤          ├
│  │  │  │          │
├─┼─┼─┤          ├
│  │  │  →          │
┼─┴─┴↑┼─┬─┬─┼
│          │  │  │  │
┤          ├─┼─┼─┤
│          │  │  │  │
┤          ├─┼─┼─┤
│          │  │  │  │
┼─┬─┬─┼─┴─┴─┼

ナナメ移動をコスト2でおこなえるので、「ナナメ移動の距離は、グリッドを45度回転させてマンハッタン距離」の定石を使えば、すぐに求められる。

よって、可能性としては以下の最大17通りを試せばよい。

始点と終点が小タイルで近い場合、愚直に移動
以下の最大16通りの「始点・終点がともに大タイル」である移動について求め、出るまでのコストと合わせた中での最小値
- 始点が小タイルの場合、上下左右のいずれかの大タイルにまっすぐ出た先を新たな始点とする
- 終点が小タイルの場合、上下左右のいずれかの大タイルにまっすぐ出た先を新たな終点とする

ただし、 $K=2$ の場合に限り、2つ先のタイルへ移動する場合はまっすぐ突っ切っていく方が安くなる。（これが見つけづらい）

│  │  │      │
├─┼─┤      ├
│  │  →      │
┼─┴↑┼─┬↓┼
│      │  │  →  コスト4
┤      ├─┼─┤
│      →  →  →  コスト3
┼─┬─┼─┴─┼

始点終点座標を $K$ で割ったものを $(S_x',S_y'),(T_x',T_y')$ とする。
差分 $D_x'=|S_x'-T_x'|,D_y'=|S_y'-T_y'|$ とすると、 $\min(D_x',D_y')$ まではナナメ移動でおこない、余った分 $R=\max(D_x',D_y')-\min(D_x',D_y')$ をコスト $\dfrac{3}{2}R$ でまっすぐ突っ切ることで、最小の移動となる。

Python3

G - Merchant Takahashi

問題

$N$ 個の町が横一列に並び、 $i$ から $j$ への移動には通行料 $C \times |i-j|$ かかる
これから市場が $M$ 回、順番に開催され、商人の高橋君がいくつかに参加することを目論んでいる
- $i$ 回目の市場は町 $T_i$ で行われ、高橋君が参加すると $P_i$ の儲けを得られる
- $i$ 回目の市場の終了後にどの町にいても、高橋君は $i+1$ 回目の市場に参加できる
- お金は潤沢に持っており、通行料が払えなくなることはない
高橋君が利益（市場での儲け - 通行料）を最大化するように参加する市場を決めたとき、最大利益を求めよ
$1 \le N,M \le 2 \times 10^5$
$1 \le C \le 10^9$
$1 \le P_i \le 10^{13}$

解法

セグメント木DP。うまく式変形して、移動コストを織り込んだ形で管理する。

まず、素朴なDPを考えると、

$DP[i,j]=i$ 番目の市場終了後に、町 $j$ にいた場合の最大利益

みたいにして、 $i$ 番目の市場では“もらうDP”の考え方で以下のように更新できる。

$DP[i,T_i] \xleftarrow[\max]{} P_i + \max_j(DP[i-1,j]-C|T_i-j|)$

（以降、破壊的に更新することとして、DPの $i$ の次元は省略する）

この $max_j$ の部分は、 $T_i$ より $j$ が左か右かで場合分けすれば絶対値を外せて、

$\max_j(DP[j]-C|T_i-j|)$
$=\max(\max_{1 \le j \lt T_i}(DP[j]-CT_i+Cj), \max_{T_i \le j \le N}(DP[j]+CT_i-Cj))$
$=\max(-CT_i+\max_{1 \le j \lt T_i}(DP[j]+Cj), CT_i+\max_{T_i \le j \le N}(DP[j]-Cj))$

となるので、「① $DP[j]+Cj$ を載せたセグメント木」「② $DP[j]-Cj$ を載せたセグメント木」があれば、 $T_i$ を基準に左なら①、右なら②から区間最大値を得ることで、市場 $i$ の更新ができる。

これ、本番中ACが780人もいるのかぁ。。。

Python3

        
          
          
              
              class SegmentTreeInjectable:
    """
    単位元生成関数 identity_factory と二項演算関数 func を外部注入するセグメント木
 
    [生成]
    SegmentTreeInjectable(n, identity_factory, func)
    SegmentTreeInjectable.from_array(array, identity_factory, func)  # 既存の配列より作成
 
    [関数]
    add(i, x)               Aiにxを加算
    update(i, x)            Aiをxに書き換え
    get_range(a, b)         [a, b) の集約値を得る
    get_all()               全ての集約値を得る
    get_point(i)            Aiを得る
    leftmost(a, b, x, ev)   [a, b) の範囲で、ev(x, Ai)=True となる最も左の i を得る（前提条件あり）
    rightmost(a, b, x, ev)  [a, b) の範囲で、ev(x, Ai)=True となる最も右の i を得る（前提条件あり）
    debug_print()           深さ毎に整形して出力する
    """
 
    def __init__(self, n, identity_factory, func):
        n2 = 1 << (n - 1).bit_length()
        self.offset = n2
        self.tree = [identity_factory() for _ in range(n2 << 1)]
        self.func = func
        self.idf = identity_factory
 
    @classmethod
    def from_array(cls, arr, identity_factory, func):
        """ 既存の配列から生成 """
        ins = cls(len(arr), identity_factory, func)
        ins.tree[ins.offset:ins.offset + len(arr)] = arr
        for i in range(ins.offset - 1, 0, -1):
            l = i << 1
            r = l + 1
            ins.tree[i] = func(ins.tree[l], ins.tree[r])
        return ins
 
    def add(self, i, x):
        """
        Aiにxを加算
        :param i: index (0-indexed)
        :param x: add value
        """
        i += self.offset
        self.tree[i] = self.func(self.tree[i], x)
        self.__upstream(i)
 
    def update(self, i, x):
        """
        Aiの値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.offset
        self.tree[i] = x
        self.__upstream(i)
 
    def __upstream(self, i):
        tree = self.tree
        func = self.func
        while i > 1:
            i >>= 1
            lch = i << 1
            rch = lch | 1
            tree[i] = func(tree[lch], tree[rch])
 
    def get_range(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        tree = self.tree
        func = self.func
        result_l = self.idf()
        result_r = self.idf()
 
        l = a + self.offset
        r = b + self.offset
        while l < r:
            if r & 1:
                result_r = func(tree[r - 1], result_r)
            if l & 1:
                result_l = func(result_l, tree[l])
                l += 1
            l >>= 1
            r >>= 1
 
        return func(result_l, result_r)
 
    def get_all(self):
        return self.tree[1]
 
    def get_point(self, i):
        return self.tree[i + self.offset]
 
    def leftmost(self, a, b, x, ev):
        """
        [a, b) の範囲で、ev(x, 値) = True となる最初の index を得る。存在しない場合は-1。
 
        使用できる条件:
        [l, r) の集約値を y としたとき、ev(x, y)=True となることが、
        l <= i < r 内に ev(x, Ai)=True となる要素があることと等しい。（(func, ev) = (min,ge), (max,le) など）
        """
        tree = self.tree
        l = a + self.offset
        r = b + self.offset
        r_found = -1
        while l < r:
            if l & 1:
                if ev(x, tree[l]):
                    return self._leftmost_sub(l, x, ev)
                l += 1
            if r & 1:
                if ev(x, tree[r - 1]):
                    r_found = r - 1
            l >>= 1
            r >>= 1
 
        if r_found == -1:
            return -1
 
        return self._leftmost_sub(r_found, x, ev)
 
    def _leftmost_sub(self, i, x, ev):
        """
        tree-index i が示す範囲で、ev(x, Aj)=True となる最も左のarray-index j を得る
        （tree[i] が示す範囲には条件を満たすものが必ず存在する前提とする）
        """
        tree = self.tree
        while i < self.offset:
            l = i << 1
            if ev(x, tree[l]):
                i = l
            else:
                i = l + 1
        return i - self.offset
 
    def rightmost(self, a, b, x, ev):
        """
        [a, b) の範囲で、ev(x, 値) = True となる最後の index を得る。存在しない場合は-1。
 
        使用できる条件:
        [l, r) の集約値を y としたとき、ev(x, y)=True となることが、
        l <= i < r 内に ev(x, Ai)=True となる要素があることと等しい。（(func, ev) = (min,ge), (max,le) など）
        """
        tree = self.tree
        l = a + self.offset
        r = b + self.offset
        l_found = -1
        while l < r:
            if r & 1:
                if ev(x, tree[r - 1]):
                    return self._rightmost_sub(r - 1, x, ev)
            if l & 1:
                if ev(x, tree[l]):
                    l_found = l
                l += 1
            l >>= 1
            r >>= 1
 
        if l_found == -1:
            return -1
 
        return self._rightmost_sub(l_found, x, ev)
 
    def _rightmost_sub(self, i, x, ev):
        """
        tree-index i が示す範囲で、ev(x, Aj)=True となる最も右のarray-index j を得る
        （tree[i] が示す範囲には条件を満たすものが必ず存在する前提とする）
        """
        tree = self.tree
        while i < self.offset:
            l = i << 1
            if ev(x, tree[l + 1]):
                i = l + 1
            else:
                i = l
        return i - self.offset
 
    def debug_print(self):
        i = 1
        while i <= self.offset:
            print(self.tree[i:i * 2])
            i <<= 1
 
 
n, c = map(int, input().split())
 
NINF = -(1 << 60)
init = [0] + [NINF] * (n - 1)
sgt1 = SegmentTreeInjectable.from_array(init, lambda: NINF, max)
sgt2 = SegmentTreeInjectable.from_array(init, lambda: NINF, max)
 
m = int(input())
for _ in range(m):
    t, p = map(int, input().split())
    t -= 1
    res1 = sgt1.get_range(0, t + 1) - c * t
    res2 = sgt2.get_range(t + 1, n) + c * t
    res = max(res1, res2) + p
    sgt1.update(t, max(sgt1.get_point(t), res + c * t))
    sgt2.update(t, max(sgt2.get_point(t), res - c * t))
 
ans = NINF
for i in range(n):
    ans = max(ans, sgt1.get_point(i) - c * i)
 
print(ans)

            

        
      