AtCoder Beginner Contest 178の感想

AtCoder

2020.09.142020.09.17

ABC178に参加した。

AtCoder Beginner Contest 178 - AtCoder

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

A – Not

0を1、1を0にする。

1-xを計算するか、1と排他的論理和 1^x を取ればOK。

x = int(input())

ans = 1 - x
print(ans)

B – Product Max

愚直に考えると二重ループになって間に合わない。

最大値だけを求めればいいので、区間の最大・最小の組合せだけ考えればいい。

負の値も含まれているので、区間の最大値同士だけを掛け算しても正しい答えにならない可能性があることに注意。

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

ans = max(a * c, a * d, b * c, b * d)
print(ans)

C – Ubiquity

ベン図を書くとわかりやすい。

全事象は0~9の10個の数字を使った場合で10^N

ここから1~9しか使わなかった場合と0~8しか使わなかった場合を引く。

そして1~8しか使わなかった場合を足せば答えになる。

n = int(input())
mod = 10 ** 9 + 7

ans = pow(10, n, mod) - 2 * pow(9, n, mod) + pow(8, n, mod)
print(ans % mod)

D – Redistribution

本番中はメモ化再起で解いた。

最低でも3が必要なので、値が0~2なら0、3~5なら1を返す。

6以上なら最低でも3が1個はあるので初期値を1とし、3以上の値を引いて総当り。

メモ化しないと間に合わないのでlru_cacheでデコレート。

from functools import lru_cache
import sys

sys.setrecursionlimit(2000)

s = int(input())
mod = 10 ** 9 + 7


@lru_cache(maxsize=None)
def dfs(n):
    if n <= 2:
        return 0
    elif 3 <= n <= 5:
        return 1
    else:
        count = 1
        for i in range(3, n + 1):
            count += dfs(n - i)
            count %= mod

        return count % mod


ans = dfs(s)
print(ans)

解説ではDPで解いていた。

こちらの方が実装も楽で考え方もわかりやすい。

s = int(input())
mod = 10 ** 9 + 7

dp = [0] * (s + 1)
dp[0] = 1

x = 0
for i in range(3, s + 1):
    x += dp[i - 3]
    dp[i] = x % mod

ans = dp[s] % mod
print(ans)

E – Dist Max

マンハッタン距離という言葉を初めて聞いた。

絶対値の扱い方がよくわからず本番中に解けなかった。

45度回転させて解くのが定石らしい。

愚直にやると二重ループでO(N^2)だが、解説のような式変形を行うことでO(N)で解けた。

|x| = max(x, -x) は当たり前といえば当たり前だが新しい発見。

n = int(input())
a, b = [], []

for _ in range(n):
    x, y = map(int, input().split())
    a.append(x - y)
    b.append(x + y)

ans = max(max(a) - min(a), max(b) - min(b))
print(ans)

Highest更新して初のレート700台。

緑までもうひと踏ん張り。