AtCoder Beginner Contest 154の感想

ABC154に参加した。

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

A – Remaining Balls

U=SかU=Tで場合分け。

s, t = input().split()
a, b = map(int, input().split())
u = input()

if u == s:
    print(a - 1, b)
elif u == t:
    print(a, b - 1)

B – I miss you…

文字数の数だけxを出力。

s = input()

print('x' * len(s))

C – Distinct or Not

ソートして隣り合う数字が等しいかどうか見ていく。

n = int(input())
a = list(map(int, input().split()))

a.sort()
isDistinct = True
for i in range(1, len(a)):
    if a[i - 1] == a[i]:
        isDistinct = False
        break

print('YES') if isDistinct else print('NO')

D – Dice in Line

和の期待値＝期待値の和なので、K個の区間和を総当たりで求める。

そのまま実装すると時間計算量がO(NK)になり間に合わないので累積和を利用する。

n-kを計算する場面があるので、n=kかどうかで場合分けをした。

n, k = map(int, input().split())
p = list(map(int, input().split()))

if n != k:
    p_sum = [0] * (n + 1)

    for i in range(n):
        p_sum[i] = p_sum[i - 1] + p[i]

    ans = 0
    for i in range(k, n):
        ans = max(ans, p_sum[i] - p_sum[i - k])

    ans = (ans + k) / 2
    print(ans)
else:
    ans = (sum(p) + k) / 2
    print(ans)

しかし、焦って場合分けを見落とすことも予想されるので、場合分けしなくて済む方法をコンテスト後に考えた。

n, k = map(int, input().split())
p = list(map(int, input().split()))

p_sum = [0] * (n + 1)

for i in range(n):
    p_sum[i + 1] = p_sum[i] + p[i]

ans = 0
for i in range(n - k + 1):
    ans = max(ans, p_sum[i + k] - p_sum[i])

ans = (ans + k) / 2
print(ans)

E – Almost Everywhere Zero

場合分けが複雑になり、実装出来なかった。

桁DPという方法で解けるらしいので要勉強。

レートが400を超え、茶色になった。

次はレート800の緑を目標に頑張っていく。