ABC408を振り返ります
旅行に行っていたり、他の用事があったりで、3週間ぶりのABCです。
結果、A問題からC問題の3問正解で、レーティングは変わらずでした。ブランクがあった割にはC問題までは結構早く解けたので、レーティング現状維持はできました。
D問題も解きたかったのですが、TLEになってしまい解答が通らず...要復習ですね。（→ その後、D問題の回答を追記しました）
A - Timeout
最後に起きていた時間を記録しておき、肩叩きの時間 T[i] が、寝てしまう時間S以内に発生しているか...を全探索でチェックしました。
N, S = map(int, input().split())
T = list(map(int, input().split()))
# 最後に起きていた時間を更新
last_wake = 0
# 各T[i]についてしらべる
for i in range(N):
# 最後に起きていた時間からの経過時間がSより大きいなら、NG
if T[i] - last_wake > S:
print("No")
exit()
# 最後に起きていた時間を更新
last_wake = T[i]
print("Yes")
B - Compression
配列 A から set を作成すると、重複が無くなります。重複を除いたあとの値をsortして、出力すればokです。
N = int(input())
A = list(map(int, input().split()))
# list から set を作成(重複削除)
set_a = set(A)
# 重複を除いたものをソートする
sorted_a = sorted(set_a)
print(len(sorted_a))
print(*sorted_a)
C - Not All Covered
入力例1について、
- 砲台がカバーしている壁=1
- 砲台がカバーしていない壁=0
とすると、以下のような表ができる。
w1 w2 w3 w4 w5 w6 w7 w8 w9 w10
1 1 1 1 1 1 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 0 1 1 1 1 1 1
0 0 0 0 0 0 1 1 1 1
------------------------------
1 1 1 2 3 2 2 2 2 2
最小の手数で壁を突破するには、最も砲台のカバーが少ない壁を破る。
↓
各壁に対してカバーしている砲台数をカウントして、その最小値を求めれば良い。
砲台のカバー範囲を求める際、0 or 1 の配列をたくさん作るとTLEします。
ので、「Lの位置で+1, R+1の位置で-1する」ルールを使うと、目的の配列を少ない計算量で求められます。
Lの位置で+1, R+1の位置で-1する
+1 0 0 0 0 0 -1 0 0 0
0 0 0 +1 0 -1 0 0 0 0
0 0 0 0 +1 0 0 0 0 0
0 0 0 0 0 0 +1 0 0 0
------------------------------
プラスマイナスを足し合わせる
+1 0 0 +1 +1 -1 0 0 0 0
------------------------------
↓ 目的の配列が作れる
1 1 1 2 3 2 2 2 2 2
N, M = map(int, input().split())
LR = []
for _ in range(M):
l, r = map(int, input().split())
LR.append((l, r))
# 各砲台が、どこの壁をカバーしているか記録
walls = [0] * (N + 1)
for l, r in LR:
# L の位置でプラスして、R+1の位置でマイナスする
walls[l] += 1
if r + 1 <= N:
walls[r + 1] -= 1
# 各壁をカバーしている砲台数を求める
for i in range(1, N + 1):
walls[i] += walls[i - 1]
# カバーしている砲台数の最小値が答え
ans = min(walls[1:])
print(ans)
D - Flip to Gather (追加解答)
コンテスト中には解けなかったので、復習で追加回答しました。
解説を見ていると、どうやらDPで解くのがわかりやすかった様子。コンテスト中、DPもちらっと頭に浮かんだのですが、DPはあまり深く掘り下げずに他のやり方でやっていて、結局TLEでした。
求める数列が以下のどれかになれば良い。
- [0の連続 A][1の連続 B][0の連続 C]
- [0の連続 A][1の連続 B]
- [0の連続 A]
ということで、dpの配列は以下のように求めれば良い。
dp[数列の位置][A,B,Cのどの部分か] = その位置での回数の最小値
# [0,1]の配列を与えて、配列に対する最小の交換回数を返すメソッド
def count(s_list):
dp = [[0] * 3 for _ in range(len(s_list) + 3)]
# 0の位置は A のみ可能
dp[0][0] = 0
dp[0][1] = INF
dp[0][2] = INF
# 配列の位置を最後までループ
for i in range(len(s_list)):
s = s_list[i]
# A
dp[i + 1][0] = dp[i][0] + (0 if s == 0 else 1)
# B
dp[i + 1][1] = min(dp[i][0] + (0 if s == 1 else 1),
dp[i][1] + (0 if s == 1 else 1))
# C
dp[i + 1][2] = min(dp[i][1] + (0 if s == 0 else 1),
dp[i][2] + (0 if s == 0 else 1))
# A, B, Cの中で最小のものが答え
answer = min(dp[len(s_list)][0], dp[len(s_list)][1], dp[len(s_list)][2])
return answer
T = int(input())
for _ in range(T):
N = int(input())
S = list(map(int, input().strip()))
print(count(S))