ABC435振り返り

前回の振り返り(間隔空きすぎだけど許して)

今日はABC開催日だったので参加結果を振り返る

今週はA,B,Cの3完(0ペナ)

A

シグマ計算の数式

$$
\sum_{k=1}^Nk=\frac{N(N+1)}{2}
$$

を使う

ソースコード

main.py

from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)

def main():
    N = rI()
    ans = N*(N+1) // 2
    print(ans)
    
if __name__ == '__main__':
    main()

B

l,rから地道に剰余で判定する。それをl,r全探索

Sの計算を累積和でしてるけどfor文の計算でもよかった

ソースコード

main.py

from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)

def main():
    N = rI()
    A = rLI()
    S = [0] + list(accumulate(A))
    ans = 0
    for l in range(N):
        for r in range(l+1,N):
            s = S[r+1]-S[l]
            err(s)
            for i in range(l,r+1):
                err(i,A[i])
                if s % A[i] == 0:
                    break
            else:
                ans+=1    
    print(ans)
    
if __name__ == '__main__':
    main()

C

順番にドミノみてどこまで伸ばせるか随時計算

ソースコード

main.py

from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)

def main():
    N = rI()
    A = rLI()
    
    i = 0
    cur = A[i] - 1
    
    while i < N and cur >= i:
        # err(i+1,cur)
        cur = max(cur,i+A[i]-1)
        i += 1
    print(i)
if __name__ == '__main__':
    main()

D

BFSで時間足りなさそうと思って検索したら
SCC 分解 → DAG → 追加オンリーの伝播 DPとかいう単語で絶望したけど
BFSの実行方法を工夫すればよかったというオチ。

E

$N\leq10^9$とかいう絶望的なオーダーに逃亡

F

ねこはいます

G

CとE問題が合体した!?

感想

D問題の使うアルゴリズム間違えてなかったのに、
オーダーを抑える工夫が足りなかったのは改善したい。