AtCoder ABC423 振り返り(緑コーダーがPythonでABCD問題)

ABC423を振り返ります

今回はABCDまで4問解答(2回ペナルティ)でした。
ちょっといいパフォーマンスが出て、ABC413以来ひさびさに緑色に復帰しました。
（復帰したので、今回から記事タイトルがちょっと変わっています。）

開始直後にトラブルがあって、5−6分ほど参加できなかったりもしたのですけども、諦めずにD問題まで解けたので良かったです。

間違えたのはB問題とC問題でした。
今回のB・C問題のような「部屋N+1の間にドアNがある」系の、植木算のような問題が昔から苦手で、数え上げでミスってしまう気がしてます...。

A - Scary Fee

「引き出し額 1000 円あたり C 円の手数料がかかる」ということは、残高から 1000 + C 円 何回引けるか、を考えれば良いです。

X, C = map(int, input().split())

# 1000 + C 円を引き出す回数
ans = X // (1000 + C)

# 1000 円単位に戻す
print(ans * 1000)

B - Locked Rooms

• 部屋0にいる人が、どこまでいけるか
• 部屋Nにいる人が、どこまでいけるか

をそれぞれ Set に保存します。両方の Set の和集合を取れば、2人が行ける部屋の数がわかります。

それを、部屋の数(N + 1)から引けば、誰も行けない部屋の数がわかります。

N = int(input())
L = list(map(int, input().split()))


# 部屋0にいる人が行ける部屋
left_set = set()
left_set.add(0)
for i in range(N):
    if L[i] == 0:
        left_set.add(i + 1)
    else:
        break

# 部屋Nにいる人が行ける部屋
right_set = set()
right_set.add(N)
for j in range(N-1, 0, -1):
    if L[j] == 0:
        right_set.add(j)
    else:
        break

# 両方の和集合
all_set = left_set | right_set
print(N + 1 - len(all_set))

C - Lock All Doors

1 1 0 0 1 1 0 R のような状態を考えます(Rが初期位置)。

• 左から3番目のドアを締めに行くので、[3-8] 間のドアを一回すべて開ける必要がある
  • → 初期位置 〜 一番左の0までの間にある 1の個数分、ドアを開ける操作
• 最後にドアをすべて閉める必要があるので、[3-8] 間のドアを閉める操作が必要です

つまり、操作回数は以下で求められます。

(初期位置から一番左の0までの間にある 1の個数) + (初期位置から一番左の0までのドアの個数)

これを左右両側で求めれば、答えになります。

---

(初期位置から一番左の0までの間にある 1の個数) は、都度計算するとTLEになるので、累積和を使って計算します。

INF = 10 ** 18

N, R = map(int, input().split())
L = list(map(int, input().split()))

# 左右両側の0のインデックスを探す
sum_l = []
sum_l.append(0)
min_zero_index = INF # 0の最小インデックス
max_zero_index = -1  # 0の最大インデックス
for i in range(N):
    sum_l.append(sum_l[-1] + L[i]) # 累積和 を計算
    if L[i] == 0:
        min_zero_index = min(min_zero_index, i)
        max_zero_index = max(max_zero_index, i)

left_count = 0
if min_zero_index < R:
    # Rより左側の個数を数える
    left_count = R - min_zero_index
    # Rより左側の1の個数を数える
    left_count += sum_l[R] - sum_l[min_zero_index + 1]

right_count = 0
if max_zero_index >= R:
    # Rより右側の個数を数える
    right_count = max_zero_index + 1 - R
    # Rより右側の1の個数を数える
    right_count += sum_l[max_zero_index] - sum_l[R]

print(left_count + right_count)

D - Long Waiting

待っているグループと、店内に入ったグループをそれぞれ優先度付きキューで管理します。
店内がいっぱいでは入れない場合は、入店済グループから退出処理を行い、空きを作ります。

import heapq

N, K = map(int, input().split())

wait_list = [] # 待っているグループ
exit_list = [] # 店内にいるグループ
heapq.heapify(wait_list)
heapq.heapify(exit_list)

enter_time = [0]*(N)
for i in range(N):
    a, b, c = map(int, input().split())
    heapq.heappush(wait_list, (a, b, c, i))

current_num = 0  # 店内の現在人数
current_time = 0 # 現在時刻

# 全グループが入店するまでループ
while wait_list:
    # 次のグループの待ち人数
    wait_num = wait_list[0][2]

    # 次のグループが入れるようになるまで、退出処理
    while wait_num > K - current_num:
        a, c, d = heapq.heappop(exit_list)
        current_time = a # 現在時刻を更新
        current_num -= c # 店内の人数を更新
    
    # 席が空いたので，店内にいれる
    a, b, c, idx = heapq.heappop(wait_list)
    current_time = max(current_time, a) # 現在時刻または到着時刻の遅い方に入店する

    # 退店時刻(current_time + b)でソートされるように、優先度付きキューに追加
    heapq.heappush(exit_list, (current_time + b, c, idx))

    # 店内の人数を更新
    current_num += c

print(*enter_time, sep="\n")