ABC425を振り返ります
今回はABCDまで4問解答でした。レーティングは微増でした。
B問題、C問題で結構時間を取られてしまい、D問題を解いた頃には終了間際でした。水色を目指すには、スピードアップが必要ですね。
A - Sigma Cubes
問題のとおりに計算式を作って実装しました。
計算式にシグマが入ると分かりにくいですね...。
こういうときは、入力例/出力例を読むと、実装のヒントになります。
N = int(input())
answer = 0
for i in range(1, N + 1):
s = (-1) ** i
s *= i ** 3
answer += s
print(answer)
提出 #69647047 - ユニークビジョンプログラミングコンテスト2025 秋（AtCoder Beginner Contest 425）
B - Find Permutation 2
B問題としては結構難しかったような...。
N=4なら、[1,2,3,4]を並べ替えたようなPを作れるか？という問題です。
数列Aの中に、重複する数字があったら、Noを出力します。
例 [-1 2 2 3] のような場合は [1,2,3,4] の並べ替えを表現できないので、"No"です。
それ以外の場合は数列を作れます。
-1 は、1~Nの中でまだ使われていない数字の中で一番小さいものを使うようにしました。
N = int(input())
A = list(map(int, input().split()))
# すでに使われている数字を記録
used_set = []
for a in A:
if a == -1:
continue
# 使われている数字重複していたら終了
if a in used_set:
print("No")
exit()
else:
used_set.append(a)
numbers = [i for i in range(1, N + 1)] # 1~Nまでの数字
number_idx = 0
answer = []
for i in range(len(A)):
if A[i] == -1:
# -1のとき、使われていない数字の中で一番小さいものを使う
while numbers[number_idx] in used_set:
number_idx += 1
answer.append(numbers[number_idx])
number_idx += 1
else:
# -1でないとき、そのまま使う
answer.append(A[i])
print("Yes")
print(*answer)
提出 #69659405 - ユニークビジョンプログラミングコンテスト2025 秋（AtCoder Beginner Contest 425）
C - Rotate and Sum Query
クエリ1では、「先頭からC個を取り出して、末尾に移動する」操作をまともに実施すると、計算量が多くなってTLEします。
そこで、offsetという変数を用意して、実際に配列を変更せずに、どこが先頭かを管理するようにしました。
クエリ2では、区間の和を都度求めると、計算量が多くなってTLEします。
そこで、あらかじめ数列Aの累積和を求めておき、区間和を簡単に求められるようにしました。
N, Q = map(int, input().split())
A = list(map(int, input().split()))
# 累積和を求める
sum_a = [0]
for i in range(N):
sum_a.append(sum_a[-1] + A[i])
offset = 0 # 先頭のインデックスを管理する変数
for i in range(Q):
query = list(map(int, input().split()))
if query[0] == 1:
# クエリ1: 先頭からC個を取り出して、末尾に移動する
# 実際に配列を変更せず、offsetを更新するだけにする。
# 配列を飛び出したら、先頭に戻るようにNで割った余りをとる
offset += query[1]
offset = offset % (N)
else:
# クエリ2: 区間和を求める
L, R = query[1], query[2]
L = L - 1 # 0-indexedに変換
R = R - 1
total = 0 # 答え
if offset + L < N and offset + R < N:
# どちらもAの中に収まる
total += sum_a[offset + R + 1] - sum_a[offset + L]
elif offset + L < N and offset + R >= N:
# leftはAの中に収まるが、rightはAの外に出る
total += sum_a[N] - sum_a[offset + L] # LからAの最後まで
total += sum_a[(offset + R + 1) % (N)] # Aの最初からRまで
else:
# どちらもAの外に出る
# LからRまでの長さを計算する
total += sum_a[(offset + R + 1) % (N)] - sum_a[(offset + L) % (N)]
print(total)
提出 #69672127 - ユニークビジョンプログラミングコンテスト2025 秋（AtCoder Beginner Contest 425）
D - Ulam-Warburton Automaton
白色の全マス目を一つずつチェックしていくと、計算量が多そうです。
そこで逆に考えて、「黒色のマス目を広げられるか？」という視点で考えました。
これであれば、黒色のマス目の4方向を探索して、チェックしていけば良いということになります。
黒色のマス目を幅優先探索で広げていきます。
H, W = map(int, input().split())
# 盤面を@で囲む
S = []
S.append('@' * (W + 2))
for _ in range(H):
S.append('@' + input() + '@')
S.append('@' * (W + 2))
# 黒色のマス目を記録
black_set = set()
for i in range(H + 2):
for j in range(W + 2):
if S[i][j] == '#':
black_set.add((i, j))
move_count = 0 # 移動回数
que = deque() # 幅優先探索のためのキュー
for black in black_set:
que.append((black[0], black[1], move_count))
new_black_set = set() # 今回の移動で新たに黒色になったマス目
moves = [(1, 0), (-1, 0), (0, 1), (0, -1)] # 4方向
while len(que) > 0:
i, j, mc = que.popleft()
# 移動回数が増えたら、new_black_setをblack_setに追加して、new_black_setを初期化
if mc != move_count:
move_count = mc
black_set |= new_black_set
new_black_set = set()
# 4方向を探索
for move in moves:
ni = i + move[0]
nj = j + move[1]
# 盤面外、黒色、すでに今回の移動で黒色になったマス目はスルー
if S[ni][nj] == '@':
continue
if (ni, nj) in black_set:
continue
if (ni, nj) in new_black_set:
continue
# 4方向のうち、黒色のマス目がちょうど1つだけなら、(ni,nj)を黒色にする
neighbour_black_count = 0
for move2 in moves:
nni = ni + move2[0]
nnj = nj + move2[1]
if (nni, nnj) in black_set:
neighbour_black_count += 1
if neibour_black_count == 1:
que.append((ni, nj, mc + 1))
new_black_set.add((ni, nj))
# 黒色のマス目の数を出力
print(len(black_set))
提出 #69683960 - ユニークビジョンプログラミングコンテスト2025 秋（AtCoder Beginner Contest 425）