AtCoder ABC227 個人的メモ

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よりは小さいだろうと見積もれる。
なので、その範囲で$a$と$b$を全探索してあり得る建築面積の集合を求める。
そしてそれぞれの$S_i$があり得るかを十分高速に判定すればおｋ。

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

$A$と$B$を全探索し、あり得る$C$の個数を計算で求めればおｋ。

$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}$と分かる。
$A$と$B$が定まれば$C$は$B\leq C\leq \lfloor\frac{N}{AB}\rfloor$となる。
よって、$A$と$B$が求まればあり得る$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)