AtCoder Beginner Contest 163の感想

ABC163に参加した。

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

A – Circle Pond

piの出し方を知っていれば簡単。

import math

r = int(input())

ans = 2 * r * math.pi
print(ans)

B – Homework

宿題をするのにかかる日数を合計し、Nから引いた値が答え。

負になる場合は-1を出力する。

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

ans = max(n - sum(a), -1)
print(ans)

C – management

各値がAに何回登場するか数える。

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

ans = [0] * n

for i in a:
    ans[i - 1] += 1

for i in ans:
    print(i)

D – Sum of Large Numbers

10^100は共通項なので無視すと、0, 1, 2, … , N のN+1個の中からK個以上の数を選び、和としてありえる物の個数を数える問題になる。

最小値は下からK個、最大値は上からK個足せば良い。

各値は1刻みなので、最小値から最大値の間の数は全て和としてありえる値になる。

なので、1個選んだ場合、2個選んだ場合、… 、N+1個選んだ場合、と累積和を事前にO(N)で求めておき、Kに関してループを回せば解ける。

n+1個の数があるので、Pythonではn+2の配列が必要になることに注意する。

n, k = map(int, input().split())
mod = 10 ** 9 + 7

cum = [0] * (n + 2)
cum[1] = 1
for i in range(2, n + 2):
    cum[i] = i + cum[i - 1]

ans = 0
for j in range(k, n + 2):
    small = cum[j]
    big = cum[n + 1] - cum[n - j + 1]
    ans += big - small + 1
    ans %= mod

print(ans % mod)

今回のコンテストはUnratedとなったため、レートは更新されなかった。


コメント

タイトルとURLをコピーしました