M-SOLUTIONS プロコンオープン 2020の感想

AtCoder

2020.07.26

M-SOLUTIONS プロコンオープン 2020に参加した。

M-SOLUTIONS Programming Contest 2020 - AtCoder

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

A – Kyu in AtCoder

やるだけ。

x = int(input())

if 400 <= x < 600:
    print(8)
elif 600 <= x < 800:
    print(7)
elif 800 <= x < 1000:
    print(6)
elif 1000 <= x < 1200:
    print(5)
elif 1200 <= x < 1400:
    print(4)
elif 1400 <= x < 1600:
    print(3)
elif 1600 <= x < 1800:
    print(2)
elif 1800 <= x < 2000:
    print(1)

B – Magic 2

制約が緩いので全探索。

a, b, c = map(int, input().split())
k = int(input())

ans = False
for x in range(k + 1):
    for y in range(k - x + 1):
        for z in range(k - x - y + 1):
            if a * (2 ** x) < b * (2 ** y) < c * (2 ** z):
                ans = True
                break

print('Yes') if ans else print('No')

C – Marks

最初は愚直に掛け算してTLE。

O(N)なのに何で…と思っていたが、掛け算の桁数が大きくなると計算時間が爆発的に増えるということを知らなかった。

差分だけ持てばいいことに時間ギリギリで気づいて滑り込みAC。

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

for i in range(k, n):
    if a[i - k] / a[i] < 1:
        print('Yes')
    else:
        print('No')

D – Road to Millionaire

解説放送を見てAC。

１．貪欲法

翌日の株価が高ければ今日株を買い、低ければ何もしない。

差分を更新していく。

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

ans = 1000
for i in range(n - 1):
    x = a[i]
    y = a[i + 1]
    if x < y:
        k = ans // x
        ans %= x
        ans += k * y

print(ans)

２．DP

i日目に株を売った場合の所持金の最大値を求める。

i-1日目から何もしないか、i日目より前のj日目で買った株をi日目で売る、のどちらかの計算を行いながらDPテーブルを更新していく。

Aは0日目に対応させるためにダミーデータとして[0]を追加している。

n = int(input())
a = [0] + list(map(int, input().split()))

dp = [0] * (n + 10)
dp[1] = 1000
for i in range(2, n + 1):
    dp[i] = dp[i - 1]
    for j in range(1, i):
        x = dp[j] // a[j]
        y = dp[j] + (a[i] - a[j]) * x
        dp[i] = max(dp[i], y)

ans = dp[n]
print(ans)

D問題が解けなかった上にC問題を解くのが遅すぎて爆死。