C - Standing On The Shoulders
問題
考えたこと
どの並び順でも一番上の頭以外の高さは不変です。なので頭の高さが一番大きい人を上に配置すればよいです。
コードはaを足していく過程でbを引いたり足したりすることで入れ替えてます。
ACコード
n = int(input())
big_a, big_b = map(int, input().split())
ans = big_b
for i in range(n - 1):
a, b = map(int, input().split())
if b - a > big_b - big_a:
# いままで一番大きい頭だったbig_bをなかったことにし、big_aのほうを足す
ans -= big_b
ans += big_a
# 新しいbを足す
ans += b
big_a, big_b = a, b
else:
ans += a
print(ans)
D - Permutation Subsequence
問題
考えたこと
入力例３を考えてみます。
まず、数字の選び方です。図１のように$P_i$を自然数が順番に並ぶよう$i$が小さい順に選んでいきます。（降順、昇順関係なし）
次に、図２のように$1 \sim 5$まで選んだ時を考えてみます。緑色の小さいほうが$i_1$、大きいほうが$i_k$となるので答えは $i_k - i_1 = 8$となります。
では、入力例３の答えはどうなるのでしょうか？図３を見てみましょう。答えは $i_k - i_1 = 5$となります。
ここまでを見るとわかるように自然数が順番に並ぶよう$P_i$を選び、その中の最小の$i$と最大の$i$の差が答えとなります（これが$i_1$と$i_k$）。
そこで、私はこの問題の答えを図４のように$(p[i], i)$をリストとして格納しなおし$p[i]$でソートし、$P_i = 1 ~ N$まで探索することで、最小の$i_k - i_1$を求めました。
これを実現するために$i$の格納先としてSortedListというものを用いて、次に進むごとに前の要素を削除、次の要素を追加し、$i_k - i_1$は$SortedList[0] = i_1$、$SortedList[-1] = i_k$という性質を使って取り出していきました。
参考
ACコード
from sortedcontainers import SortedList
n, k = map(int, input().split())
p = list(map(int, input().split()))
p_idx = [(p[i], i + 1) for i in range(n)]
p_idx.sort()
sl = SortedList([])
for i in range(k):
sl.add(p_idx[i][1])
ans = min(float("inf"), sl[-1] - sl[0])
for i in range(k, n):
sl.add(p_idx[i][1])
sl.discard(p_idx[i - k][1])
ans = min(ans, sl[-1] - sl[0])
print(ans)
E - Clique Connect
問題
考えたこと
最小全域木は重みが最小の辺を貪欲に追加していき、その総和が答えとなります。ただし、追加する時点でそれらの頂点が連結である場合は追加しません。
最小全域木の解法を前提のもとこの問題を解いていきます。入力例の図のようにすべての辺をつなごうとすると$\sum K_i \leq 4 \times 10^5$より間に合いません。※例えば、1 2 3の入力で(1, 2), (1, 3), (2, 3)とすると間に合わない。そこで、最小全域木はすでに連結である場合辺を追加しなくていいという性質を用いて、$A_{i,j - 1}$と$A_{i, j}$を$j = K_i$までつないでいくことで解くことができます。
ACコード
class UnionFind:
def __init__(self, N: int) -> None:
self.N = N
self.par = [-1 for _ in range(N)]
self.siz = [1 for _ in range(N)]
def root(self, x: int) -> int:
while True:
if self.par[x] == -1:
break
x = self.par[x]
return x
def unite(self, u: int, v: int) -> None:
RootU = self.root(u)
RootV = self.root(v)
if RootU != RootV:
if self.siz[RootU] < self.siz[RootV]:
self.par[RootU] = RootV
self.siz[RootV] += self.siz[RootU]
else:
self.par[RootV] = RootU
self.siz[RootU] += self.siz[RootV]
def same(self, u: int, v: int) -> bool:
# 同じ根かどうか
return self.root(u) == self.root(v)
def root_list(self) -> set:
# 親のsetを取得
return {self.root(i) for i in range(self.N)}
def count_root_v(self) -> list:
# 各根に対する頂点の数を求める
count_v = [0] * self.N
for i in range(self.N):
count_v[self.root(i)] += 1
return count_v
n, m = map(int, input().split())
UF = UnionFind(n)
g = dict()
# g[連結したい頂点のtuple] = 重み
for _ in range(m):
k, c = map(int, input().split())
a = list(map(int, input().split()))
for i in range(1, k):
u, v = a[i - 1] - 1, a[i] - 1
edge_pair = (u, v) if u < v else (v, u)
if g.get(edge_pair, -1) == -1:
g[edge_pair] = c
else:
g[edge_pair] = min(g[edge_pair], c)
g = sorted(g.items(), key=lambda x: x[1]) # 重みが小さい順にソート
ans = 0
for uv, c in g:
u, v = uv
if UF.same(u, v) is False:
UF.unite(u, v)
ans += c # 連結した重みの総和
print(ans if len(UF.root_list()) == 1 else -1) # 親が二つ以上の時はgが連結でないので-1
感想
Eは完全に鉄則のおかげで解けた！感謝