🔖

AtCoder ABC227 個人的メモ

2021/11/14に公開

A - Last Card

愚直にシミュレーション

N, K, A = map(int, input().split())

ans = A - 1
for _ in range(K):
    ans += 1
    ans %= N + 1
    ans = max(1, ans)

print(ans)

B - KEYENCE building

S_i\leq 1000かつa,bが正の整数なので、a,bはそれぞれ1000よりは小さいだろうと見積もれる。
なので、その範囲でabを全探索してあり得る建築面積の集合を求める。
そしてそれぞれのS_iがあり得るかを十分高速に判定すればおk。

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

lst = set()
for a in range(1, 1000):
    for b in range(1, 1000):
        res = 4 * a * b + 3 * a + 3 * b
        lst.add(res)

ans = 0
for s in S:
    if s not in lst:
        ans += 1

print(ans)

参考

set in の計算量
https://wiki.python.org/moin/TimeComplexity

C - ABC conjecture

ABを全探索し、あり得るCの個数を計算で求めればおk。

A\leq B\leq CかつABC\leq Nより、A^3\leq Nとなる必要があるので、A\leq N^{1/3}と分かる。
同様にABB\leq Nなので、B\leq (\frac{N}{A})^{1/2}と分かる。
ABが定まればCB\leq C\leq \lfloor\frac{N}{AB}\rfloorとなる。
よって、ABが求まればあり得るCの個数は計算で求めることができる。

計算量はまぁ大体いいでしょと思ったら大丈夫だった。

N = int(input())

ans = 0
for a in range(1, N + 1):
    if a ** 3 > N:
        break
    for b in range(a, N + 1):
        if a * b * b > N:
            break
        c = N // (a * b)
        ans += max(0, c - b + 1)

print(ans)

参考

調和級数の話
https://manabitimes.jp/math/627

D - Project Planning

https://atcoder.jp/contests/abc227/editorial/2911

解は最大で10^{12}\times 2\times 10^5 \simeq 10^{17}となるので、二分探索の探索範囲に注意

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

ok = 0
ng = 10 ** 18
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    res = sum(min(mid, a) for a in A)
    if mid * K <= res:
        ok = mid
    else:
        ng = mid

print(ok)

Discussion