ABC389振り返り



前回の振り返り

https://qiita.com/comet725/items/51d247f4fd0293f6774d

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


https://atcoder.jp/contests/abc389

今週はA,B,C,Dの完(1ペナ)


# A

デリミタを`x`にしてsplit

あとはただの掛け算

## ソースコード

```python: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():
    a,b = list(map(int,sys.stdin.readline().rstrip().split("x")))
    
    ans = a*b
    print(ans)
    
if __name__ == '__main__':
    main()

```

# B

順番に比較

なんとなくメモ化再帰にした

## ソースコード

```python: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)

d = defaultdict(lambda: -1)

d[0] = 1
def fact(n):
    if d[n] != -1:
        ret = d[n]
    else:
        ret = fact(n-1)*n
    return ret

def main():
    N = rI()
    X = 2
    while fact(X) != N:
        X += 1
    print(X)
if __name__ == '__main__':
    main()

```

# C

後ろにヘビを追加するときに頭の座標を累積和して計算

先頭が抜けるたびに先頭のヘビの番号を変える

出力は先頭のヘビの番号を気にしながら出力

err関数のコメントアウト忘れてTLE

## ソースコード

```python: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():
    Q = rI()
    
    q = [0]
    top = 0
    for _ in range(Q):
        query = rLI()
        q0 = query[0]
        if q0 == 1:
            q.append(q[-1]+query[1])
            # err(q[top:])
        if q0 == 2:
            top+=1
            # err(list(map(lambda x:x-q[top],q[top:])))
        if q0 == 3:
            # err(query[1]-1,list(map(lambda x:x-q[top],q[top:])))
            print(q[query[1]+top-1]-q[top])
    
if __name__ == '__main__':
    main()

```

# D

右上の頂点のことだけをまず考える
x座標を順番に増やして取れる最大のy座標を計算する

右上しか見ていなかったを思い出して数を4倍する
4倍した分重複して数えてある正方形があるのでそれを調整して、最終的な内包する正方形の数を求める

## ソースコード

```python: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():
    R = rI()
    ans = 0
    r2 = R**2
    for x in range(R):
        y = int((r2-(x+0.5)**2)**0.5+0.5)
        # err(x+0.5,y, ans)
        ans+= y
    ans = 4*ans - 4*R + 1
    print(ans)
    
if __name__ == '__main__':
    main()

```

# E

F問題よりACしている人が明らかに少なかったのでパス

# F

先週D問題の解説引きづってimos法で悩んでたけどだめでした

その時に過剰だった遅延セグ木が
ここでは公式解法だったみたい…
しかもまさかの遅延セグ木でinlineDPとかいうスゴ技

# G

このレベルのグラフは無理だって

# まとめ

順位表みてE飛ばしたけどFもきつかった…