Atcoder ABC230 振り返り

　バーチャルで参加しました(224位)．緑diffのDを解けたので良かったです．ただ後で他人のコードを見ると自分のコードがぐちゃぐちゃだと感じるので更なる精進が必要です．

A - AtCoder Quiz 3【AC】

　pythonはfstringで0埋めをしてくれる機能があります．

N = int(input())
if N <= 41:
    print(f"AGC{N:03}")
else:
    print(f"AGC{N+1:03}")

B - Triple Metre【AC】

Tはoxxという3文字のループなので，Sが含まれてるかどうかの判別は，Tの1文字目~len(S)文字目，Tの2文字目~len(S)+1文字目，Tの3文字目~len(S)+2文字目のみを調べれば良いと分かります．

S = input()
T = "oxx"*10**5

i = 0
while i <= 3:
    if T[i:i+len(S)] == S:
        print("Yes")
        break
    i += 1
else:
    print("No")

C - X drawing【AC】

　結構難しかった．取り得る全てのkに対して.を#に書き換えていては時間が足りません．(Q−P+1)×(S−R+1)≤3×10^5という制約があるので，実際に表示するマス目だけ書き換えるように，頑張ってrangeの範囲を決めます．

N, A, B = map(int, input().split())
P, Q, R, S = map(int, input().split())

masu = [["." for _ in range(S-R+1)] for _ in range(Q-P+1)]

for k in range(max(P-A, R-B, max(1-A, 1-B)), min(Q-A, S-B, min(N-A, N-B))+1):
    masu[A+k-P][B+k-R] = "#"

for k in range(max(P-A, B-S, max(1-A, B-N)), min(Q-A, B-R, min(N-A, B-1))+1):
    masu[A+k-P][B-k-R] = "#"

for i in masu:
    print("".join(i))

D - Destroyer Takahashi【AC】

　貪欲法を使います．左から順に壁を壊していくとすると，(左から見て)壁の終端が一番短い壁を，壁を壊す範囲に含めないとその壁が壊されなくなってしまいます．よって，最も終端が短い壁を壊す範囲の端に設定して壊し，残った壁の中で一番終端の短い壁をまた選び……を繰り返します．
　壁の範囲のrでソートする必要がありますが，[l, r]でリストにいれて[r, l]に入れ直してからソートしてまた[l, r]に直して……？と時間が掛かりそうだったのでコードは非常に分かりにくくなっています(ACしたのでヨシ！)．
　sorted(lis, key=lambda x: x[1])とすると[l, r]の形を維持したままrをkeyにソートする事が出来ます．これを使えばもっとシンプルなコードになります．

N, D = map(int, input().split())
D -= 1
wall = []

min_r = 1<<60
for _ in range(N):
    l, r = map(int, input().split())
    wall.append([l, r])
    min_r = min(min_r, r)
wall = sorted(wall)

ans = 0
i = 0
while True:
    ans += 1
    if i >= N:
        break
    while wall[i][0] <= min_r+D:
        i += 1
        if i >= N:
            break

    if i >= N:
        break
    min_r = wall[i][1]
    while i < N:
        if wall[i][0] > min_r:
            break
        min_r = min(min_r, wall[i][1])
        i += 1

print(ans)

よりシンプルなコード(解説見た後に作成)

N, D = map(int, input().split())
D -= 1
wall = []

for _ in range(N):
    wall.append([int(i) for i in input().split()])

wall = sorted(wall, key=lambda x: x[1])
min_r = wall[0][1]
ans = 1

for l, r in wall[1:]:
    if l > min_r + D:
        ans += 1
        min_r = r

print(ans)