ABC410を振り返ります
今回はABCDEの5問回答でした。久しぶりの水色パフォーマンスでした。
D問題の問題文が良くわからず、先にE問題を取り掛かったところ60分くらいかけてうまく解けました。その時点で残り15分ほどだったのですが、D問題に戻り時間ギリギリに解くことが出来ました。
意外となんとかなるものですね...。
A - G1
競馬のG1レースは3歳以上・4歳以上など「以上」のものが多いのですが、この問題では「A以下」が出場できるそうです（おかげでちょっと混乱してしまった）。
N = int(input())
A = list(map(int, input().split()))
K = int(input())
# K歳で出場できるレースをカウント
count = 0
for i in range(N):
if A[i] >= K:
count += 1
print(count)
B - Reverse Proxy
素直にN個の箱(box_array)の配列を用意して、シミュレーションしました。配列は0始まりなので、そこだけ注意です。
N, Q = map(int, input().split())
X = list(map(int, input().split()))
box_array = [0] * N
answer = []
for i in range(Q):
x = X[i]
if x == 0:
# 最も中身が少ない箱を探して、入れる
min_value = min(box_array)
for j in range(N):
if box_array[j] == min_value:
box_array[j] += 1
answer.append(j + 1)
break
else:
# 箱Xにいれる
box_array[x - 1] += 1
answer.append(x)
print(*answer)
C - Rotatable Array
「素直にDequeを使ってシミュレーションする？」と思ったんですが、それだとタイプ3操作のときに入れ替えの回数が多すぎてTLEになります。
配列の先頭位置の変数を用意して、「タイプ3のときは、数列の先頭位置を変える」という操作を行うことで、解きました。
N, Q = map(int, input().split())
A = []
for i in range(N):
A.append(i+1)
start_index = 0 # 配列の中で現在の先頭はどこか
for i in range(Q):
query = list(map(int, input().split()))
if query[0] == 1:
# Ap を x に変更
index = (start_index + query[1] - 1) % N
A[index] = query[2]
elif query[0] == 2:
# Ap を print
index = (start_index + query[1] - 1) % N
print(A[index])
elif query[0] == 3:
# 配列の先頭を変える
start_index = (start_index + query[1]) % N
D - XOR Shortest Walk
最初、問題の意味がなんのことやらわかりませんでした。
冷静に読んでみると、グラフの通った経路をXORしておき、Goalにたどり着いたときの値がコスト(walk)だと、なんとなくわかりました。
通常のグラフ問題と同じく、幅優先探索で解けそうです。幅優先探索では計算量が不安だったんですけど、正解になりました。
N, M = map(int, input().split())
path = defaultdict(list)
for _ in range(M):
A, B, W = map(int, input().split())
path[A].append((B, W))
# 頂点にたどり着いたときの walkの値を記録
checked_walk = defaultdict(set)
# 幅優先探索
queue = deque()
queue.append((1, 0))
checked_walk[1].add(0)
min_walk = INF # ゴールまでの最小値。
while queue:
current, walk = queue.popleft()
# ゴールに着いたときは、最小値を更新する
if current == N:
min_walk = min(min_walk, walk)
# 次の経路を調査
for next_node, weight in path[current]:
# もし同じマスに同じwalkで到達していた場合、そこは探査しない
xor_value = walk ^ weight
if xor_value not in checked_walk[next_node]:
checked_walk[next_node].add(xor_value)
queue.append((next_node, xor_value))
if min_walk == INF:
print(-1)
else:
print(min_walk)
E - Battles in a Row
各モンスターに対して 魔力で倒す or 体力で倒す を深さ優先探索ですれば...と思ったんですが、モンスターが3000体いると2^3000 通りになってしまい、ダメそうです。
ここではDPで解くようにしました。
「横軸に体力、縦軸にモンスターN体め、値は魔力」の表を埋めていく感じです。体力・魔力を減らすのではなく、累積で使った体力・魔力を0から増やして記録するようにしました。
# 入力例1の場合(高橋君の体力は 10、魔力は 14)
1 [8, 9999, 9999, 9999, 9999, 0, 9999, 9999, 9999, 9999]
# 1体目は(体力0, 魔力8)か(体力5, 魔力0)を使って倒せる
2 [14, 9999, 9999, 9999, 9999, 6, 9999, 9999, 9999, 9999]
# 2体目までは(体力0, 魔力14)か(体力5, 魔力6)を使って倒せる
3 [23, 9999, 9999, 9999, 9999, 15, 9999, 14, 9999, 9999]
# 3体目までは(体力7, 魔力14)を使って倒せる。
# (体力0, 魔力23)と(体力5, 魔力15)は、魔力オーバのためだめ。
4 [122, 9999, 9999, 9999, 9999, 114, 9999, 113, 9999, 9999]
# 4体目はどうやっても体力・魔力を使い果たすので、倒せない
N, H, M = map(int, input().split())
monsters = []
for i in range(N):
monsters.append(list(map(int, input().split())))
# 横が体力、縦がモンスター
dp = [[INF] * (H + 1) for _ in range(N + 1)]
dp[0][0] = 0
end_line = 0
for i in range(1, N + 1):
monster_a, monster_b = monsters[i - 1]
# min(魔力を使って倒す or 体力を使って倒す)
for j in range(H + 1):
dp[i][j] = min(dp[i - 1][j] + monster_b, dp[i-1][j-monster_a] if j >= monster_a else INF)
# もし、その行の全パターンで魔力をMより使ってしまっていたら、そこで終了
min_mp_of_line = min(dp[i])
if min_mp_of_line > M:
end_line = i - 1
break
# 次のモンスターに移動
end_line = i
print(end_line)