🚀

AtCoder ABC216 個人的メモ

2021/08/30に公開

Python

競技プログラミング

AtCoder

tech

所感

abcde5完

A - Signed Difficulty

X, Y = map(int, input().split("."))

if 0 <= Y <= 2:
    print(X, "-", sep="")
elif 3 <= Y <= 6:
    print(X)
else:
    print(X, "+", sep="")

B - Same Name

N = int(input())

seen = set()
for _ in range(N):
    ST = input()
    if ST in seen:
        print("Yes")
        exit()
    seen.add(ST)

print("No")

C - Many Balls

N = int(input())

ans = []
while N > 0:
    if N % 2:
        N -= 1
        ans.append("A")
    else:
        N //= 2
        ans.append("B")

print("".join(ans[::-1]))

D - Pair of Balls

「各色で塗られたボールはちょうど2個ずつ存在」ということから捨てることができるボールのペアは順番を気にせず捨てて良さそうと分かる。
問題文の操作を素直に実装すると以下のようになる。

各筒の一番上を確認する( $O(M)$ )
同じ色があったらその2つのボールを捨てる( $O(1)$ )
1と2をボールを捨てることができなくなるまで行う( $O(N)$ )

というわけで全体で $O(NM)$ となりtleしそう。
1の各筒を確認する操作は事前にメモしておけばボールを捨てるたびに行う必要はない。
2の操作によってメモを更新する必要があるが、その際に更新されるのは2つの筒のみなので更新は $O(1)$ で済む。
よって、以下のような実装をすればおｋ(1と2は↑と同じ)。

各筒の一番上を確認しメモする( $O(M)$ )
同じ色があったらその2つのボールを捨てる( $O(1)$ )
ボールを捨てた筒で新しく一番上になったボールをメモに書き込む( $O(1)$ )
2と3をボールを捨てることができなくなるまで行う( $O(N)$ )

def color_check(color: int, cylinder_i: int) -> None:
    """
    新しく筒の一番上になったボールの色colorと同じ色が他の筒の一番上にあるかを判定\\
    ある場合 → 削除可能なペアとしてstackに2つの筒のインデックスを追加\\
    ない場合 → colorの色のボールが一番上にあることメモ

    Args:
        color      (int): 新しく一番上になったボールの色
        cylinder_i (int): 今見ている筒のインデックス
    """
    if color in top_colors:
        stack.append((top_colors[color], cylinder_i))
    else:
        top_colors[color] = cylinder_i
    return


N, M = map(int, input().split())
A = []
top_colors = {}  # 各色で最初に一番上に来たボールのインデックス
stack = []       # 捨てることができるインデックスのペア
for i in range(M):
    k = int(input())
    # ボールを捨てることをpop()で実現したいのでaは反転
    a = list(map(int, input().split()))[::-1]
    A.append(a)
    color_check(a[-1], i)

while stack:
    i, j = stack.pop()
    for k in (i, j):
        A[k].pop()    # 筒の一番上を捨てる
        if not A[k]:  # 筒が空になったらメモの更新は不要
            continue
        color_check(A[k][-1], k)

# 筒が全て空になっているかを判定
if any(a for a in A):
    print("No")
else:
    print("Yes")

E - Amusement Park

1番目に楽しいアトラクションが2番目と同じ楽しさになるまで乗りまくる
1番目と2番目が同じ楽しさになったら1番目と2番目を交互に乗る
3番目と同じ楽しさになったら1,2,3番目を順に乗る
以上の操作を以下のいずれかを満たすまで繰り返す
- アトラクションにK回乗った
- 楽しさの最大値が負になった

これだと全体で $O(K)$ となるのでtleする。
1番目に楽しいアトラクションが2番目と同じになるまで乗る回数は両者の楽しさの差。
この回数をまとめて満足度に加算すれば $A_i$ 毎に $O(1)$ となるので全体で $O(N)$ となる。

N, K = map(int, input().split())
A = list(map(int, input().split()))  # 整数を入力

A.sort(reverse=True)
A.append(0)
ans = 0
ride_cnt = 0
for i in range(N):
    diff_next = A[i] - A[i + 1]
    if diff_next * (i + 1) + ride_cnt <= K:
        res = diff_next * (A[i] + A[i + 1] + 1) // 2  # 総和の公式
        res *= i + 1
        ans += res
        ride_cnt += diff_next * (i + 1)
    else:
        # 同じ楽しさを(i+1)回ずつ楽しむ
        diff_next = (K - ride_cnt) // (i + 1)
        ans += (diff_next * (A[i] + A[i] - diff_next + 1) // 2) * (i + 1)
        ride_cnt += diff_next * (i + 1)
        # 残りのK-cnt回同じ楽しさを楽しむ(K-ride_cnt<i+1になっている)
        ans += (A[i] - diff_next) * (K - ride_cnt)
        break

print(ans)

参考

F - Max Sum Counting

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
MOD = 998244353

AB = sorted((a, b) for a, b in zip(A, B))
# Bの総和がAの最大値以上となる場合は条件式が必ず不成立になるので、その場合はまとめて扱う
dp = [0] * (max(A) + 1)
dp[0] = 1
ans = 0
for a, b in AB:
    dec = sum(dp[1:a + 1])  # i番目を含んでいない場合
    for i in range(len(dp)- 1, -1, -1):
        j = i + b
        if j >= len(dp):
            continue
        dp[j] += dp[i]
        dp[j] %= MOD
    ans += sum(dp[1:a + 1]) - dec
    ans %= MOD

print(ans)