デンソークリエイトプログラミングコンテスト2025（AtCoder Beginner Contest 413）の解答等の速報的まとめ
配列Aの合計とMを比較する
A
n, m = map(int, input().split())
print("Yes" if sum(map(int, input().split())) m else "No")
文字を全部作成して、setで重複を省く
B
n = int(input())
s = [input() for _ in range(n)]
strings = set()
for i in range(n):
for j in range(n):
if i == j:
continue
strings.add(s[i] + s[j])
print(len(strings))
dequeにクエリ1をそのまま入れる
クエリ2で$c$と$k$の計算で個数を合計して値を求める
C
from collections import deque
q = deque()
for _ in range(int(input())):
com = list(map(int, input().split()))
if com[0] == 1:
c, x = com[1:]
q.append([c, x])
else:
k = com[1]
ans = 0
while q and k > 0:
c_i, x_i = q.popleft()
if c_i k:
ans += c_i * x_i
k -= c_i
else:
ans += k * x_i
c_i -= k
k = 0
q.appendleft([c_i, x_i])
print(ans)
今回考えないといけない公比$r$は
- $r>=1 : (1, 2, 4, 8, 16)$
- $r
- $r=-1 : (1, -1, 1, -1, 1)$
確認方法は
- 単純にソート
- 絶対値でソート
- 数が2種類かつ絶対値の等しいかつ個数差が1個以下
D
import collections
def check(lst):
for i in range(len(lst) - 1):
if lst[i + 1] * lst[0] != lst[1] * lst[i]:
return False
return True
def check2(lst):
counts = collections.Counter(lst)
if len(counts) == 2:
k_0, k_1 = counts.keys()
# print(k_0, counts[k_0], ":", k_1, counts[k_1])
if abs(k_0) == abs(k_1) and abs(counts[k_0] - counts[k_1]) 1:
return True
return False
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
if check(sorted(a)) or check(sorted(a, key=abs)) or check2(a):
print("Yes")
else:
print("No")
2のべき乗の幅で大小比較をするのはマージソートっぽく感じた
コードの一個目を比較して小さいほうを前にして返すようにしたらうまくいった
コードで$a_2$を前にするのは問題文の操作でいうと
- $a_1$を反転
- $a_2$を反転
- $a_1 + a_2$で反転
と一致する
E
def like_merge(a):
if len(a) 1:
return a
a_1 = like_merge(a[:len(a) // 2])
a_2 = like_merge(a[len(a) // 2:])
if a_1[0] a_2[0]:
return a_1 + a_2
else:
return a_2 + a_1
for _ in range(int(input())):
n = int(input())
p = list(map(int, input().split()))
print(*like_merge(p))
問題文は言い換えると、ゴールまでの最短距離を青木君がつぶすから次善のルートが何手でゴールに到達できるか全マス求める。
言い換えが間違っているのかコーディングが悪いのかできなかった
※追記
実装が良くなかったぽい
次善の探索をゴールから逆算していたが冗長なコードのどこかでバグっていたみたい
単純に、BFSで2回目に到達したらスコア加算&deque追加をしたらAC出来た
F
from collections import deque
h, w, k = map(int, input().split())
INF = float("inf")
field = [[INF] * w for _ in range(h)]
q = deque()
count = [[0] * w for _ in range(h)]
for _ in range(k):
r, c = map(lambda x:int(x) - 1, input().split())
field[r][c] = 0
q.append([r, c])
count[r][c] = 2
while q:
x, y = q.popleft()
for i, j in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
if 0 i h and 0 j w:
count[i][j] += 1
if count[i][j] == 2:
field[i][j] = field[x][y] + 1
q.append([i, j])
ans = 0
for i in range(h):
# print(field[i])
for j in range(w):
if field[i][j] INF:
ans += field[i][j]
print(ans)
問題文は、障害物を8方向で連結したときに右上と左下が連結するかといえる
よってそれを実装するが、UnionFindのコードは基本的にparentが対象の個数$n$と一致するので、今回の$n = h \times w$では制限にひっかかる
よって、parentをdictにしてfindで確認するときにデフォルト値を埋め込むようにすればうまくいく
G
class UnionFind:
def __init__(self, n):
self.n = n
self.parents = dict()
def find(self, x):
if x not in self.parents:
self.parents[x] = -1
if self.parents[x] 0:
return x
else:
self.parents[x] = self.find(self.parents[x])
return self.parents[x]
def union(self, x, y):
x = self.find(x)
y = self.find(y)
if x == y:
return
if self.parents[x] > self.parents[y]:
x, y = y, x
self.parents[x] += self.parents[y]
self.parents[y] = x
def size(self, x):
return -self.parents[self.find(x)]
def same(self, x, y):
return self.find(x) == self.find(y)
h, w, k = map(int, input().split())
if h == w == 1 or k == 0:
exit(print("Yes"))
UF = UnionFind(h * w + 2)
left = h * w
right = h * w + 1
for i in range(h - 1):
UF.union(left, (i + 1) * w)
UF.union(right, (i + 1) * w - 1)
for j in range(w):
UF.union(left, (h - 1) * w + j)
UF.union(right, j)
nums = set()
for _ in range(k):
r_i, c_i = map(lambda x:int(x) - 1, input().split())
n = r_i * w + c_i
for i, j in [(r_i + 1, c_i + 1), (r_i + 1, c_i), (r_i + 1, c_i - 1),
(r_i, c_i + 1), (r_i, c_i - 1),
(r_i - 1, c_i + 1), (r_i - 1, c_i), (r_i - 1, c_i - 1)]:
if 0 i h and 0 j w:
n_i = i * w + j
if n_i in nums:
UF.union(n_i, n)
nums.add(n)
print("No" if UF.same(left, right) else "Yes")
Views: 0
