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)