AtCoder ABC478振り返り (PythonでABC問題)

ABC478を振り返ります

今回はABCDまで4問解答でした。
2週間ほど休んでいましたが、復帰戦で上々の結果だったので良かったです。
久々に緑色に復帰しました。

A - Grapes

長さN個の配列を用意して、地道に+1ずつ配ります。
配列の長さからが溢れないように、 % N で処理すればokです。

N, M = map(int, input().split())
ans = [0] * N

# 各自に1個ずつ配る
m = M 
for i in range(M):
    ans[i % N] += 1

for i in ans:
    print(i)

B - Topping

トッピングN種類から3種類を選ぶ全パターンについて、価格と嬉しさを求めます。

N, V = map(int, input().split())
W = list(map(int, input().split()))

# N種類の中から3種類を選ぶ
ans = 0
for x in range(N - 2):
    for y in range(x + 1, N - 1):
        for z in range(y + 1, N):
            # 予算オーバーチェック
            price = x + y + z + 3
            if price > V:
                continue

            # max を探す
            w = W[x] + W[y] + W[z]
            ans = max(w, ans)

print(ans)

C - Sort Subarray

操作の後、Aが条件を満たすのはこんなときです。
たとえば、長さ N の A を 位置 i で区切った場合...

条件1

• 左側 A[0]〜A[i-1]: 昇順になっていればok
• 真ん中 A[i]〜A[i+K]: ここは昇順に並べかえるので、なんでも可
• 右側 A[i+K+1]〜A[N-1]: 昇順になっていればok

加えて、左側 - 真ん中 - 右側 がスムーズに繋がらないといけません

条件2

[左側の最大値] <= [真ん中の最小値], [真ん中の最大値] <= [右側の最小値]

条件1, 条件2を同時に満たせるかどうかを調べればokです。

INF = 10 ** 18

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

# Aの先頭から、昇順に並んでいる範囲を調べる
max_array = [0] * N
max_array[0] = A[0]
max_index = 0
max_continue = True
for i in range(1, N):
    max_array[i] = max(max_array[i-1], A[i])
    if max_continue and A[i-1] <= A[i]:
        max_index = i
    else:
        max_continue = False

# Aの最後から、降順に並んでいる範囲を調べる
min_array = [INF] * N
min_array[N-1] = A[N-1]
min_index = N-1
min_continue = True
for i in range(N-2, -1, -1):
    min_array[i] = min(min_array[i+1], A[i])

    if min_continue and A[i] <= A[i+1]:
        min_index = i
    else:
        min_continue = False

# 区切りを移動し、条件を満たすか調べる
for i in range(N-K+1):
    # 左側
    left_max = max_array[i - 1] if i > 0 else 0
    left_continue = i - 1 <= min_index

    # 真ん中
    block_min = min_array[i]
    block_max = max_array[i + K - 1]

    # 右側
    right_min = min_array[i + K] if i + K < N else INF
    right_continue = min_index <= i + K  

    # 左側・右側がそれぞれ昇順に並んでいる。かつ、真ん中の値が 左側の最大値と右側の最小値がの間にある
    if left_continue and right_continue and left_max <= block_min and block_max <= right_min:
        print("Yes")
        exit()

print("No")

D - Range Set Insertion Query

• 整数 X ごとに区間をまとめる
• 区間の重複を取り除く
• 累積和(いもす法？)で答えを求める

という手順で解答しました。

いもす法については、競技プログラミングの鉄則 | マイナビブックス の 2.2章 を参考にしています。

from collections import defaultdict

# 参考 [一次元区間の重なりを結合 #Python - Qiita](https://qiita.com/kkdd/items/6488757de0cc0cbb50cd)
def merger(intervals):
    intervals.sort(key=lambda interval: interval[0])
    merged = [intervals[0]]
    for w in intervals:
        if w[0] > merged[-1][1]:
            merged.append(w)
        elif w[1] > merged[-1][1]:
            merged[-1][1] = w[1]
    return merged

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

# Xごとに区間をまとめる
values = defaultdict(list)
for i in range(Q):
    L, R, X = map(int, input().split())
    values[X].append([L, R])

# 区間の重複を取り除く
for k in values.keys():
    values[k] = merger(values[k])

# 区間の累積和を求める
counts = [0] * (N + 10)
for k in values.keys():
    v_list = values[k]
    for v in v_list:
        left = v[0]
        right = v[1]
        counts[left] += 1
        counts[right + 1] -= 1

answer = []
answer.append(0)
for i in range(1, N + 1):
    newvalue= answer[-1] + counts[i]
    answer.append(newvalue)

print(*answer[1:])