−目次

AtCoder Beginner Contest 218 C,F,G,H問題メモ
- C - Shapes
  - 問題
  - 解法
- F - Blocked Roads
  - 問題
  - 解法
- G - Game on Tree 2
  - 問題
  - 解法
- H - Red and Blue Lamps
  - 問題
  - 解法

AtCoder Beginner Contest 218 C,F,G,H問題メモ

AtCoder Beginner Contest 218

C - Shapes

問題

$N \times N$ の2つのグリッド $S,T$ が与えられ、各マスは '.' または '#' である
$S$ の '#' を平行移動や90度回転移動を繰り返して $T$ の '#' に一致させられるか判定せよ
$1 \le N \le 200$

解法

pythonなら2次元配列の90度回転は以下で行えるので、上下左右の空白行をトリムした後で4通り試せばよい。

aaa = [(0, 1, 2),
       (3, 4, 5)]

list(zip(*reversed(aaa)))
# ↓
# [(3, 0),
#  (4, 1),
#  (5, 2)]

reversedを無くせば行列の転置になるので、その用途でも使える。

Python3

F - Blocked Roads

問題

$N$ 頂点 $M$ 辺の有向グラフが与えられる
1辺は全て長さ1とする
各辺につき、その辺のみが使えなかったときの頂点 $1→N$ への最短距離を求めよ
$2 \le N \le 400$
$1 \le M \le N(N-1)$

解法

計算量を正しく見積もり、経路復元できる最短経路探索をしましょう、という問題。

全辺長さ1なので最短経路探索はBFSが使えて、その計算量は $O(M)$ 。

全辺に対して愚直にその辺が使えなかったときの答えを求めていては、 $O(M^2)$ 、つまり $O(N^4)$ かかるので無理。

だが、全ての辺が使える状態で1個最短経路 $P$ （距離 $d$ ）を見つけてしまえば、 $P$ 上の辺以外が使えない場合は $d$ が答えとなる。

問題は $P$ 上の辺が使えなくなった場合だが、これは最大 $N$ 頂点のパスなので多くとも $N-1$ 辺しか無い。
これらについては再計算しても、全体で $O(NM)$ なので間に合う。

経路復元つきのBFSは、「その頂点に最短でたどり着いたときの1つ前の頂点番号（または辺番号）」を各頂点、記録しておく。

ゴール $N$ までたどり着けたらそこから始点 $1$ まで逆順に辿ることで、復元できる。

そもそも最初の状態で $N$ までたどり着けない場合のコーナーケースに注意。

Python3

        
          
          
              
              from collections import deque
 
n, m = map(int, input().split())
links = [set() for _ in range(n)]
edges = []
for i in range(m):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    links[s].add(i)
    rev_links[t].add(i)
    edges.append((s, t))
 
INF = 1 << 60
trace = [-1] * n
result = [INF] * n
q = deque()
q.append(0)
result[0] = 0
g = n - 1
while q:
    v = q.popleft()
    if v == g:
        break
    for i in links[v]:
        u = edges[i][1]
        if result[u] <= result[v] + 1:
            continue
        result[u] = result[v] + 1
        trace[u] = i
        if u == g:
            break
        q.append(u)
    else:
        continue
    break
 
if result[g] == INF:
    print(*([-1] * m))
    exit()
 
shortest_edges = set()
u = g
while u != 0:
    i = trace[u]
    shortest_edges.add(i)
    u = edges[i][0]
 
d = result[n - 1]
for i in range(m):
    if i not in shortest_edges:
        print(d)
        continue
 
    tmp_result = [INF] * n
    tmp_result[0] = 0
    q = deque()
    q.append(0)
    while q:
        v = q.popleft()
        for j in links[v]:
            if i == j:
                continue
            u = edges[j][1]
            if tmp_result[u] <= tmp_result[v] + 1:
                continue
            tmp_result[u] = tmp_result[v] + 1
            if u == g:
                break
            q.append(u)
        else:
            continue
        break
    if tmp_result[g] == INF:
        print(-1)
    else:
        print(tmp_result[g])

            

        
      

G - Game on Tree 2

問題

$N$ 頂点の木、各頂点には値 $A_i$ が設定されている
太郎と次郎の2人がゲームをする
ルール
- 最初、頂点1にコマを置く
- 太郎から交互に、コマをまだ訪れたことのない、辺で繋がった頂点に動かす
- 動かせなくなったらスコアを計算する
  - スコアは、それまでに経由した頂点（頂点1含む）の $A_i$ の中央値
太郎はスコアを最大化、次郎は最小化したいとき、最終的なスコアを求めよ
$2 \le N \le 10^5$

解法

1つのオブジェクトを連れ回すDFS。

まず、コマの動きを理解する。

頂点1を根として見たときに、コマは今いる頂点の子頂点のどれかを選んで動かすしかない
動かせなくなるのは必ず葉
根からある頂点へ到達する経路は一意＝その時点で訪れている頂点群も一意

仮に頂点 $v$ までで経由した頂点の $A_i$ が $[2, 3, 5, 9]$ となっていて、次、次郎の手番で以下のような状況なら

    ：
    ⓥ
  ↙↓↘
⑧  ④  ①  (全て葉)

当然、次郎は中央値を最小化できる①の葉を選ぶ。この時中央値は $3$ になる。

つまり、 $v$ にコマを移動させた時点で、最終的な中央値は $3$ になる未来が確定する。

その1手手前を考えると、たとえば以下のような状況だったとき、

    ：
    ⓤ        u までで辿る頂点は [2, 5, 9]
  ↙↓↘
ⓥ  ⓦ  ③    v へ行くと中央値3が確定
：  ：        w へ行くと中央値5が確定
              ③へ行くと中央値4が確定

太郎はⓦを選ぶため、ⓤにコマを移動させた時点で中央値が $5$ になる未来が確定する。

このように、

まず、根からその頂点まで辿った時の多重集合を求める
葉から、その頂点にコマを進めた場合の最終的な中央値が確定していく

ので、これを実装する。

ただ、これを別々にやろうとすると各頂点に要素数 $O(N)$ 個の多重集合を持たせないといけなくなり、全体で $O(N^2)$ の空間が必要になる。

多重集合は1個で、これを更新しながらDFSを行う方法を採る。

$DP[v]=$ 頂点 $v$ にコマを進めたときの最終的な中央値

として、オイラーツアーのように木を辿っていく過程で、頂点 $v$ に訪れたら

$A_v$ を多重集合に加える
$v$ が葉頂点なら
- $DP[v]=$ 現在の多重集合の中央値
$v$ が葉頂点でないなら
- 各子頂点に進んだ場合の中央値をそれぞれ求める
- $DP[v]$ が確定する
  - コマを動かすのが太郎か次郎かは根からの距離で決まっている
  - $DP[v]$ は、太郎なら最大の子、次郎なら最小の子の $DP$ の値
親頂点に帰る前に、 $A_v$ を多重集合から削除する

ということをすると、メモリ上に保持する多重集合は1つで済む。

よって、この多重集合は、以下のようなデータ構造である必要がある。

特定の値を加える
特定の値を削除する
現時点の中央値を得る

std::multiset、Fenwick Tree、Binary Trie、2つのHeap Queueなどのデータ構造で管理できる。

Python3

        
          
          
              
              import sys
 
from operator import add, lt
 
sys.setrecursionlimit(2 * 10 ** 5)
 
 
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
 
    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)
 
 
n = int(input())
aaa = list(map(int, input().split()))
links = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    links[a].append(b)
    links[b].append(a)
 
aaa_list = sorted(set(aaa))
aaa_dict = {a: i for i, a in enumerate(aaa_list)}
 
fwt = FenwickTreeInjectable(len(aaa_list), int, add)
 
 
def dfs(v, p, depth, fwt: FenwickTreeInjectable):
    a = aaa[v]
    i = aaa_dict[a]
    fwt.add(i, 1)
 
    if v != 0 and len(links[v]) == 1:
        if depth % 2 == 0:
            j = fwt.lower_bound(depth // 2 + 1, lt)
            res = aaa_list[j]
        else:
            j1 = fwt.lower_bound(depth // 2 + 1, lt)
            j2 = fwt.lower_bound(depth // 2 + 2, lt)
            res = (aaa_list[j1] + aaa_list[j2]) // 2
        fwt.add(i, -1)
        return res
 
    if depth % 2 == 0:
        cmp = max
        res = -1
    else:
        cmp = min
        res = 1 << 60
 
    for u in links[v]:
        if u == p:
            continue
 
        res = cmp(res, dfs(u, v, depth + 1, fwt))
 
    fwt.add(i, -1)
 
    return res
 
 
ans = dfs(0, -1, 0, fwt)
print(ans)

            

        
      

H - Red and Blue Lamps

問題

横一列に並んだ $N$ 個のランプの $R$ 個を赤く、残りを青く光らせる
隣り合う2つのランプのペアは $N-1$ 個あるが、それぞれにつき「2つが異なる色で光っていたら $A_i$ 点」というスコアが決まっている
赤く光らせるランプを適切に決めて、スコアの総和を最大化せよ
$2 \le N \le 2 \times 10^5$
$1 \le A_i \le 10^9$

解法

色自体に固有の意味は無いので、赤を少ない方（多くない方）と固定してよい。

すると、スコアは全て正であることもあり、赤を隣り合わせること、端に配置することは必ず損することがわかる。

0:赤  1:青

[赤の連続]
1 1 0 0 1 0 1 1 1
 x o x o o o x x   ← o:スコアが得られるAiの位置
 
      v v v v
1 1 0 1 0 1 0 1 1  右側を、次に1が連続する手前まで反転。
 x o o o o o o x   0の個数、oの位置はそのまま、新たに2箇所、oが増える
     ~       ~
  v v
1 0 1 0 1 0 1 1 1  （または左側を同様に反転）
 o o o o o o x x   同上
 ~   ~

[端の赤]
0 1 0 1 0 1 1 1
 o o o o o x x

v v v v v v
1 0 1 0 1 0 1 1    端から、次に1が連続する手前まで反転
 o o o o o o x     0の個数、oの位置はそのまま、新たに1箇所、oが増える
           ~
（赤と青が同数の場合を除く。その場合は全てのAiを得られる）

従って赤の位置を決めると、その両隣の $A_i+A_{i+1}$ が得られることになる。問題を言い換えると

$A_1+A_2,A_2+A_3,A_3+A_4,...$ という数列を新たに $B_i$ とする
隣り合う2つの $B_i,B_{i+1}$ は同時に選べない
$B_i$ から $R$ 個選んで総和を最大化せよ

となる。

では言い換えた問題をどうやって解くか。

DPをするにも個数が決まっているので、DP[何個目まで見たか][何個選んだか][直前を選んだか] みたいになり、 $O(N^2)$ となってしまう。

一定の条件を満たすグラフについて、ちょうど $d$ 辺を使う最短経路を高速に求める方法があるらしい。

グラフで表すことは可能なので、それでも解ける（けど概念が難しい）。

かくなる上は貪欲に選びたいが、組み替えが発生しうる。

R=3

Ai  10  100  101  50  51  11  1  2  3
         |----|    |---|                 上位2つはこのペアだが...

     |---|    |----|   |---|             3つ選ぶとなると、こう選ぶべき

貪欲に選んだときのこの組み替えを、どう修正するか？

求めたいのはスコアの総和なので、それらがどのAiのペアとして足しあわされたものかはぶっちゃけ関係ない。
そしてよく見ると、組み替える場合に新しく加算されるスコアは、必ず既に選ばれた区間を挟んだ両隣となる。
つまり、「組み替える」行為を、「既に選ばれた区間の両隣のスコアを得る」と考える。

Ai  10  100  101  50  51  11  1  2  3
         |----|    |---|                 これとこれと
     |---------------------|             あと1つはこのペアを選んだと考えることができる

すると、以下の手順で解ける。

ペアのスコアの和 $A_i+A_j$ を優先度付きキュー（最大値を取り出す）で管理する。
最初は $A_1+A_2,A_2+A_3,...$ が入っている。

あるペアがキューから取り出されたとき、その元となった位置 $i,j$ が片方でも既に使われていたら、スキップ。

そうで無い場合、そのペアは答えに加算できる。
そのペアを挟んでまだ選ばれていない一番近い2つの $A_i,A_j$ を見つけ、その和を新たにキューに放り込む。

これを繰り返し、貪欲に選んだ $R$ 個の総和が答えとなる。

「まだ選ばれていない一番近い $i,j$ 」は、std::setを使わない代替テクニックの「配列・特殊アイデア系①」で紹介しているような方法で管理できる。

もちろん、std::setのように「ある値の前後の値を検索」と「ある値の削除」ができるデータ構造があればそれを使えばよい。

Python3