ABC330 解説 (DE)

D - Counting Ls

問題

$S_{ij}=S_{ik}=S_{lj}=$o$(i \ne l, j \ne k)$ を満たす $(i,j,k,l)$ の組の個数を求める問題です。

解説

ここで、$1 \le i \le N$ に対して $S_{ix}=$oを満たす $x (1 \le x \le N)$ の個数を $H_i$、$1 \le j \le N$ に対して $S_{xi}=$oを満たす $x (1 \le x \le N)$ の個数を $W_i$ とおきます。
$S_{ij}=$oを満たす $(i,j)$ を固定すると $(k,l)$ の組の個数は、$k$ としてあり得るのは $k=j$ 以外の $H_i - 1$ 通り、$l$ としてあり得るのは $l=i$ 以外の $W_j - 1$ 通りなので、$(H_i - 1)(W_j - 1)$ 通りになります。

コード

Python

N = int(input())
S = [input() for _ in range(N)]

H = [0] * N
W = [0] * N
for i in range(N):
	for j in range(N):
		if S[i][j] == 'o':
			H[i] += 1
			W[j] += 1

ans = 0
for i in range(N):
	for j in range(N):
		if S[i][j] == 'o':
			ans += (H[i] - 1) * (W[j] - 1)

print(ans)

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
	int N;
	cin >> N;
	vector<string> S(N);
	for (int i = 0; i < N; i++) {
		cin >> S[i];
	}

	vector<int> H(N), W(N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (S[i][j] == 'o') {
				H[i]++;
				W[j]++;
			}
		}
	}

	long long ans = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (S[i][j] == 'o') {
				ans += (H[i] - 1) * (W[j] - 1);
			}
		}
	}

	cout << ans << '\n';
}

E - Mex and Update

問題

長さ $N$ の数列 $A$ をクエリごとに更新し、毎回 $mex$ を求める問題です。

解説

$A$ に含まれるそれぞれの整数の個数をmapなどで管理します。さらに、$A$ に含まれない整数をsetやSortedSetで管理します。そうすると、各クエリごとに $O(logN)$ で答えることができ、高速です。

コード

Python

sortedcontainersのSortedSetではTLEしました。
tatyamさんのSortedSetを窃盗 (Setだけに) したらACできたので、それを貼ります。ありがとうございます。

# https://github.com/tatyam-prime/SortedSet/blob/main/SortedSet.py
import math
from bisect import bisect_left, bisect_right
from typing import Generic, Iterable, Iterator, List, Tuple, TypeVar, Optional
T = TypeVar('T')

class SortedSet(Generic[T]):
	BUCKET_RATIO = 16
	SPLIT_RATIO = 24
	def __init__(self, a: Iterable[T] = []) -> None:
		a = list(a)
		n = self.size = len(a)
		if any(a[i] > a[i + 1] for i in range(n - 1)):
			a.sort()
		if any(a[i] >= a[i + 1] for i in range(n - 1)):
			a, b = [], a
			for x in b:
				if not a or a[-1] != x:
					a.append(x)
		bucket_size = int(math.ceil(math.sqrt(n / self.BUCKET_RATIO)))
		self.a = [a[n * i // bucket_size : n * (i + 1) // bucket_size] for i in range(bucket_size)]
	def __iter__(self) -> Iterator[T]:
		for i in self.a:
			for j in i:
				yield j
	def __reversed__(self) -> Iterator[T]:
		for i in reversed(self.a):
			for j in reversed(i): 
				yield j
	def __eq__(self, other) -> bool:
		return list(self) == list(other)
	def __len__(self) -> int:
		return self.size
	def __repr__(self) -> str:
		return "SortedSet" + str(self.a)
	def __str__(self) -> str:
		s = str(list(self))
		return "{" + s[1 : len(s) - 1] + "}"
	def _position(self, x: T) -> Tuple[List[T], int, int]:
		for i, a in enumerate(self.a):
			if x <= a[-1]: break
		return (a, i, bisect_left(a, x))
	def __contains__(self, x: T) -> bool:
		if self.size == 0: return False
		a, _, i = self._position(x)
		return i != len(a) and a[i] == x
	def add(self, x: T) -> bool:
		if self.size == 0:
			self.a = [[x]]
			self.size = 1
			return True
		a, b, i = self._position(x)
		if i != len(a) and a[i] == x: return False
		a.insert(i, x)
		self.size += 1
		if len(a) > len(self.a) * self.SPLIT_RATIO:
			mid = len(a) >> 1
			self.a[b:b+1] = [a[:mid], a[mid:]]
		return True
	def _pop(self, a: List[T], b: int, i: int) -> T:
		ans = a.pop(i)
		self.size -= 1
		if not a: del self.a[b]
		return ans
	def discard(self, x: T) -> bool:
		if self.size == 0: return False
		a, b, i = self._position(x)
		if i == len(a) or a[i] != x: return False
		self._pop(a, b, i)
		return True
	def lt(self, x: T) -> Optional[T]:
		for a in reversed(self.a):
			if a[0] < x:
				return a[bisect_left(a, x) - 1]
	def le(self, x: T) -> Optional[T]:
		for a in reversed(self.a):
			if a[0] <= x:
				return a[bisect_right(a, x) - 1]
	def gt(self, x: T) -> Optional[T]:
		for a in self.a:
			if a[-1] > x:
				return a[bisect_right(a, x)]
	def ge(self, x: T) -> Optional[T]:
		for a in self.a:
			if a[-1] >= x:
				return a[bisect_left(a, x)]
	def __getitem__(self, i: int) -> T:
		if i < 0:
			for a in reversed(self.a):
				i += len(a)
				if i >= 0: return a[i]
		else:
			for a in self.a:
				if i < len(a): return a[i]
				i -= len(a)
		raise IndexError
	def pop(self, i: int = -1) -> T:
		if i < 0:
			for b, a in enumerate(reversed(self.a)):
				i += len(a)
				if i >= 0: return self._pop(a, ~b, i)
		else:
			for b, a in enumerate(self.a):
				if i < len(a): return self._pop(a, b, i)
				i -= len(a)
		raise IndexError
	def index(self, x: T) -> int:
		ans = 0
		for a in self.a:
			if a[-1] >= x:
				return ans + bisect_left(a, x)
			ans += len(a)
		return ans
	def index_right(self, x: T) -> int:
		ans = 0
		for a in self.a:
			if a[-1] > x:
				return ans + bisect_right(a, x)
			ans += len(a)
		return ans

from collections import defaultdict
N, Q = map(int, input().split())
A = list(map(int, input().split()))
m = defaultdict(int)
s = SortedSet(list(range(N + 1)))
for i in A:
	m[i] += 1
	s.discard(i)
for _ in range(Q):
	i, x = map(int, input().split())
	i -= 1
	m[A[i]] -= 1
	if m[A[i]] == 0:
		s.add(A[i])
	A[i] = x
	m[A[i]] += 1
	s.discard(A[i])
	print(s[0])

C++

C++のsetでは順番が保たれるので簡単に最小値を求めることができます。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
   int N, Q;
   cin >> N >> Q;
   vector<ll> A(N);
   map<ll, ll> m;
   set<ll> s;
   for (int i = 0; i <= N; i++) {
   	s.insert(i);
   }
   for (int i = 0; i < N; i++) {
   	cin >> A[i];
   	if (s.find(A[i]) != s.end()) {
   		s.erase(A[i]);
   	}
   	m[A[i]]++;
   }
   while (Q--) {
   	ll i, x;
   	cin >> i >> x;
   	i--;
   	m[A[i]]--;
   	if (m[A[i]] == 0) {
   		m.erase(A[i]);
   		s.insert(A[i]);
   	}
   	A[i] = x;
   	m[A[i]]++;
   	if (s.find(A[i]) != s.end()) {
   		s.erase(A[i]);
   	}
   	cout << *s.begin() << '\n';
   }
}