ABC388振り返り


前回の振り返り

https://qiita.com/comet725/items/00291978c5a5e8c809fc

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

https://atcoder.jp/contests/abc388

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


# A

f-stringは便利

## ソースコード

```python:main.py
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():
    S = rS()
    ans = f"{S[0]}UPC"
    print(ans)
    
if __name__ == '__main__':
    main()

```

# B

for文で全計算

## ソースコード

```python:main.py
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, D = rLI()
    
    s = []
    
    for i in range(N):
        s.append(rLI())
    
    for i in range(D):
        ans = 0
        for T,L in s:
            w = (L+-~i)*T
            # err(w)
            ans = max(ans,w)
        print(ans)
    
if __name__ == '__main__':
    main()

```

# C

最低限大きければそれ以降は全部乗せられる

尺取法で乗せられる大きさまで見つけたら
それ以上の大きさの個数を足す

## ソースコード

```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():
    N = rI()
    A = rLI()
    
    ans = r = 0
    
    for i in range(N):
        a = A[i]
        while r<N and 2*a>A[r]:r+=1
        if r==N:break
        # err(i,a,r,A[r])
        # err(ans, N-r)
        ans += N-r
    print(ans)
    
if __name__ == '__main__':
    main()

```

# D

各々で何個リリースするかを考える

渡すべき石の数は自分より後ろの人の人数
それより持ってる石の数が少なければ後ろの人はもらえない

順番に渡すと時間かかりそうなので遅延セグ木でゴリ押し

なぜかimos法の存在忘れてた😅

## ソースコード

セグ木の実装は以下を使用した
- [shakayami/ACL-for-python](https://github.com/shakayami/ACL-for-python)

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

#lazy_segtreeの実装略

# 操作の定義
def op(a, b):
    return a + b

def mapping(f, x):
    return f + x

def composition(f, g):
    return f + g

ID = 0
E = 0

def main():
    N = rI()
    A = rLI()
    B = lazy_segtree(A, op, E, mapping, composition, ID)

    for i in range(N):
        b = B.get(i)
        r = min(b,N--~i)
        # err(b,r)
        if r > 0:
            B.apply_point(i,-r)
            B.apply(i+1,i+1+r,1)
        
    ans = [B.get(i) for i in range(N)]
    print(*ans)
    
if __name__ == '__main__':
    main()

```

# E

Cのプログラムいじって貪欲法でやったがWA
反対側でやった場合をやってみたがWA

乗せられる餅の組み合わせをグラフの辺に見立てて一般最大マッチング？とか思ったけど無茶だった

## ソースコード

<details><summary>WAコード</summary>

```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():
    N = rI()
    A = rLI()
    
    ansl = 0
    r = 1
    
    usedl = defaultdict(lambda: False)
    for i in range(N):
        if usedl[i]:continue
        a = A[i]
        while r<N and (2*a>A[r] or usedl[r]):r+=1
        if r==N:break
        usedl[i] = True
        usedl[r] = True
        ansl += 1
        # err(ansl,i,a,r,A[r])
        # err(*[k for k,v in usedl.items() if v])
    ansr = 0
    usedr = defaultdict(lambda: False)
    # err("-------------------------")
    l = N-2
    for i in range(N-1,1,-1):
        if usedr[i]:continue
        a = A[i]
        while l>=0 and (2*A[l]>a or usedr[l]):l-=1
        if l==-1:break
        usedr[i] = True
        usedr[l] = True
        ansr += 1
        # err(ansr,i,a,l,A[l])
        # err(*[k for k,v in usedr.items() if v])
        
    print(max(ansl,ansr))
    
if __name__ == '__main__':
    main()

```
</details>


# F

動的計画法したくなるけど
N成約が巨大過ぎてきつい…

# G

Eの強化版ですね。

# まとめ

久々の4完だけどEの壁は厚い…