はじめに

先日2023/07/01、 CodeQUEEN 2023 予選 (AtCoder Beginner Contest 308) の方に参加しました。

今回は、本コンテストのA~F問題について、復習を兼ねた解き直しと私なりの簡単な解説を記していこうと思います。

A - New Scheme

問題文：https://atcoder.jp/contests/abc308/tasks/abc308_a

解法

問題文の条件をひとつずつ丁寧に吟味していきます。

for文などによる単純な繰り返し処理を行い、No になる条件に着目すると比較的考えやすいです。

解答例（PyPy3）

提出先：https://atcoder.jp/contests/abc308/submissions/43177444

ABC308_A.py

s = list(map(int, input().split()))
n = 8

for i in range(n):
	if(i < n - 1 and s[i] > s[i + 1]):
		print("No")
		break
	if not(100 <= s[i] <= 675 and s[i] % 25 == 0):
		print("No")
		break
else:
	print("Yes")

B - Default Price

問題文：https://atcoder.jp/contests/abc308/tasks/abc308_b

解法

高橋くんが食べた各料理の皿について、その色に対応する値段を調べれば良いです。

連想配列を用いることにより、皿の色と値段を比較的楽に対応付けられます。

ただし、$D_{1}, D_{2}, \dots, D_{M}$ のいずれとも異なる色の皿の値段が一律 $P_{0}$ 円であることに注意が必要です。

解答例（PyPy3）

提出先：https://atcoder.jp/contests/abc308/submissions/43178198

ABC308_B.py

n, m = map(int, input().split())
c = list(map(str, input().split()))
d = list(map(str, input().split()))
p = list(map(int, input().split()))

dish = { x : y for x, y in zip(d, p[1:]) }

ans = sum(dish[x] if(x in dish) else p[0] for x in c)
print(ans)

C - Standings

問題文：https://atcoder.jp/contests/abc308/tasks/abc308_c

解法

一見、問題文で与えられた成功率をそのままソートすれば良さそうに思えますが、実際にこれを行うと、数値誤差によって WA となります（参考：kyopro_friends氏による解説）。

これを回避する方法は色々ありますが、今回はPythonで自作クラスと順序関係を定義してソートを行う方法を解説します。

Pythonの自作クラスについてソートを行う方法として、例えば __lt__ メソッドを定義するものがあります。

具体的には、下のコードに示すように、引数として self と other （ともに Prob クラスで生成されたインスタンス）を受け取り、self < other が真となるような条件を記述すれば良いです。

Prob.py

class Prob:
	def __init__(self, i, a, b):
		self.i = i
		self.a = a
		self.b = b

	def __lt__(self, other):
		key = self.a * (other.a + other.b) - other.a * (self.a + self.b)
		if(key == 0):
			return (self.i < other.i)
		return (key > 0)

今回、異なる整数 $i, j$ $(1 \leq i, j \leq N)$ に対して、 $$ \dfrac{ A_{i} }{ A_{i} + B_{i} } > \dfrac{ A_{j} }{ A_{j} + B_{j} } $$ が成り立つことは、 $$ A_{i} (A_{j} + B_{j}) - A_{j} (A_{i} + B_{i}) > 0 $$ が成り立つことと同値であり、上式による判定を行えば数値誤差が生じることはありません。

また、 $$ A_{i} (A_{j} + B_{j}) - A_{j} (A_{i} + B_{i}) = 0 $$ が成り立つ場合は、問題文の通り $i, j$ の大小比較を行えば良いです。¹

以上の方法でソートを行う場合、Pythonの sort 関数で採用されているアルゴリズムが TimSort であることから、平均計算量は $O(N \log N)$ であり、本問では十分高速です。

解答例（PyPy3）

提出先：https://atcoder.jp/contests/abc308/submissions/43178540

ABC308_C.py

import sys
input = sys.stdin.readline

class Prob:
	def __init__(self, i, a, b):
		self.i = i
		self.a = a
		self.b = b

	def __lt__(self, other):
		key = self.a * (other.a + other.b) - other.a * (self.a + self.b)
		if(key == 0):
			return (self.i < other.i)
		return (key > 0)


n = int(input())
lis = []
for i in range(1, n + 1):
	a, b = map(int, input().split())
	lis.append(Prob(i, a, b))
lis.sort()

ans = [prob.i for prob in lis]
print(*ans)

D - Snuke Maze

問題文：https://atcoder.jp/contests/abc308/tasks/abc308_d

解法

文字列 snuke には重複する英小文字がないため、グリッド上で単純なDFS/BFSを行えば良いです。

グリッドの境界と s → n → u → k → e → s → n → $\cdots$ の順に辿ることに注意し、今までに到達したマスの情報を持ちつつ探索を行いましょう。

計算量は $O(H W)$ であり、本問では十分高速です。

解答例（PyPy3）

提出先：https://atcoder.jp/contests/abc308/submissions/43179243

ABC308_D.py

h, w = map(int, input().split())
s = list(input() for _ in [0] * h)

if(s[0][0] != 's'):
	print("No")
	exit(0)

visited = { 0 }
snuke = { t : i for i, t in enumerate("snuke") }
stk = [(0, 0, 0)]
delta_x = [1, 0, -1, 0]
delta_y = [0, 1, 0, -1]
while(stk):
	x_now, y_now, c_now = stk.pop()
	if(x_now == h - 1 and y_now == w - 1):
		print("Yes")
		break
	for dx, dy in zip(delta_x, delta_y):
		x_next, y_next = x_now + dx, y_now + dy
		if not(0 <= x_next < h and 0 <= y_next < w):
			continue
		c_next = (c_now + 1) % 5 
		v_next = x_next * w + y_next
		if(v_next in visited or s[x_next][y_next] not in snuke or c_next != snuke[s[x_next][y_next]]):
			continue
		visited.add(v_next)
		stk.append((x_next, y_next, c_next))
else:
	print("No")

E - MEX

問題文：https://atcoder.jp/contests/abc308/tasks/abc308_e

解法

まず、$S$ が文字列のままだと少し扱いづらいので、M を $0$、E を $1$、X を $2$ と対応付けた数列 $S' = (S_{1}', S_{2}', \dots, S_{N}')$ に変換します。

次に、$\mathrm{mex}(A_{i}, A_{j}, A_{k})$ の値は集合 $\{ A_{i}, A_{j}, A_{k} \}$ のみに依存し、この集合としてあり得るものは $2^{3} = 8$ 通りしか存在しないので、これに着目した数え上げを行います。

このとき、$(S_{i}', S_{j}', S_{k}') = (0,1,2)$ を満たすという条件から、本問の答えを ABC211 C - chokudai のように動的計画法によって求めます。

任意の $i \in \{ 1,2,\dots,N \}$, $j \in \{ 1,2,3 \}$, $T \subset \{ 0,1,2 \}$ に対して、 $$ \mathrm{dp}[i][j][T] = | \{ (x_{1}, x_{2}, \dots, x_{j}) \mid 1 \leq x_{1} < x_{2} < \cdots < x_{j} \leq i \text{ かつ } S_{ x_{k} }' = k - 1 \text{ } (k \in \{ 1,2,\dots,j \}) \text{ かつ } T = \{ A_{ x_{1} }, A_{ x_{2} }, \dots, A_{ x_{j} } \} \} | $$ とすると、これは $i = 1,2,\dots,N$ の順に、次のように更新できます。

以下、$\mathrm{dp}[i][j][T]$ で数え上げの対象となる数列の集合（上式右辺の $|\bullet|$ の中身）を $D(i,j,T)$ とし、任意の $j, T$ について $\mathrm{dp}[0][j][T] = 0$ とします。

まず、$S_{i}' = 0$ のとき、新たに $(x_{1})=(i) \in D(i,1,\{ A_{i} \} )$ が数え上げの対象となるので、 $$ \mathrm{dp}[i][1][\{ A_{i} \}] = \mathrm{dp}[i-1][1][\{ A_{i} \}] + 1 $$ と更新できます。

続いて $S_{i}' \neq 0$ のとき、数列の要素数を $1$ だけ増加する、すなわち M → E → X の流れを一文字分更新することを考えます。

具体的には、任意の $P \subset \{ 0,1,2 \}$ について、 $$ \mathrm{dp}[i][S_{i}'][P] = \mathrm{dp}[i-1][S_{i}'][P] + \sum_{ Q \subset \{ 0,1,2 \} \text{ かつ } P = Q \cup \{ A_{i} \} } \mathrm{dp}[i-1][S_{i}'-1][Q] $$ と更新します。

最後に、上記以外の $\mathrm{dp}[i][j][T]$ については $$ \mathrm{dp}[i][j][T] = \mathrm{dp}[i-1][j][T] $$ と更新します。

このとき、本問の答えは $$ \sum_{ T \subset \{ 0,1,2 \} } \mathrm{dp}[N][3][T] \times \mathrm{mex} \ T $$ と求められます。

以上より、計算量 $O(N)$ で本問を解くことができます。

解答例（PyPy3）

提出先：https://atcoder.jp/contests/abc308/submissions/43179877

ABC308_E.py

n = int(input())
a = list(map(int, input().split()))

MEX = { c : i for i, c in enumerate("MEX") }
s = [MEX[c] for c in input()]

m = 3
dp = [[0] * (1 << m) for _ in [0] * m]
for i in range(n):
	dp_next = dp[:]
	if(s[i] == 0):
		dp_next[0][1 << a[i]] += 1
		continue
	for j in range(1 << m):
		for k in range(1 << m):
			if(j != (k | (1 << a[i]))):
				continue
			dp_next[s[i]][j] += dp[s[i] - 1][k]
	dp = dp_next[:]

def mex(bit):
	for i in range(m + 1):
		if((bit >> i) & 1):
			continue
		return i

ans = sum(dp[m - 1][bit] * mex(bit) for bit in range(1 << m))
print(ans)

F - Vouchers

問題文：https://atcoder.jp/contests/abc308/tasks/abc308_f

解法

本問は、使用したクーポンの値引き額の総和を最大化する問題に言い換えることができ、どの商品にどのクーポンを使用するかは全く気にしなくて良いです。

また、定価 $x$ 円の商品に対してクーポン $k$ が使用可能ならば、$x \leq y$ を満たす任意の整数 $y$ について、定価 $y$ 円の商品に対してもクーポン $k$ が使用可能です。

よって、本問は次のような貪欲法によって解くことができます。計算量は $O((N + M) \log M)$ です。

$N$ 個の商品を定価の昇順に並び替える。
各商品を定価の昇順に見る（着目する商品を $x$ とする）。商品 $x$ で初めて使用可能になるクーポンが存在するならば、これらを値引き額の降順に優先度付きキューに追加する。
優先度付きキュー内に存在するクーポンのうち、商品 $x$ に対して使用可能なものが存在するならば、優先度付きキューからこれを取り出し、商品 $x$ に対して使用する。
上記 2. 3. の操作を、$N$ 個の商品すべてについて繰り返す。

解答例（PyPy3）

提出先：https://atcoder.jp/contests/abc308/submissions/43180263

ABC308_F.py

from heapq import heappush, heappop

n, m = map(int, input().split())
p = sorted(map(int, input().split()))
l = list(map(int, input().split()))
d = list(map(int, input().split()))

coupon = sorted([(x, -y) for x, y in zip(l, d)], key = lambda tup : -tup[0])
que = []
ans = sum(p)
for x in p:
	while(coupon and x >= coupon[-1][0]):
		heappush(que, coupon.pop()[1])
	if not(que):
		continue
	ans += heappop(que)

print(ans)

感想

個人的に、FよりもEの方が圧倒的に難しかった（chokudai DP 苦手）
今回のような早解き6完回で安定してパフォーマンスを出せるようになりたい

Pythonで sort 関数などを用いる場合は、安定ソートが行われるため、このような場合分けは不要です。 ↩