AtCoder Beginner Contest 218 C,F,G,H問題メモ
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
from itertools import dropwhile
def trim(sss):
for _ in range(4):
sss = list(dropwhile(lambda row: all(c == '.' for c in row), sss))
sss = list(zip(*reversed(sss)))
return sss
n = int(input())
sss = [tuple(input()) for _ in range(n)]
ttt = [tuple(input()) for _ in range(n)]
sss = trim(sss)
ttt = trim(ttt)
for _ in range(4):
if sss == ttt:
print('Yes')
break
sss = list(zip(*reversed(sss)))
else:
print('No')
F - Blocked Roads
問題
解法
計算量を正しく見積もり、経路復元できる最短経路探索をしましょう、という問題。
全辺長さ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
問題
解法
1つのオブジェクトを連れ回すDFS。
まず、コマの動きを理解する。
仮に頂点 $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を行う方法を採る。
として、オイラーツアーのように木を辿っていく過程で、頂点 $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
from heapq import heapify, heappop, heappush
n, r = map(int, input().split())
aaa = list(map(int, input().split()))
if r * 2 > n:
r = n - r
elif r * 2 == n:
print(sum(aaa))
exit()
q = [(-aaa[i] - aaa[i + 1], i, i + 1) for i in range(n - 2)]
heapify(q)
used = [False] * (n - 1)
lefts = list(range(-1, n - 1))
rights = list(range(1, n + 1))
ans = 0
while r:
a, i, j = heappop(q)
if used[i] or used[j]:
continue
ans += -a
used[i] = used[j] = True
ni = lefts[rights[j]] = lefts[i]
nj = rights[lefts[i]] = rights[j]
r -= 1
if ni == -1 or nj == n - 1:
continue
heappush(q, (-aaa[ni] - aaa[nj], ni, nj))
print(ans)