ABC383振り返り




前回の振り返り

https://qiita.com/comet725/items/2c0a50c9add58a1cdefc

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


https://atcoder.jp/contests/abc383

今週はA,B,Dの3完(1ペナ)…終了直後にCをAC😅

# A

水がマイナスにならないように減らしながら加える。
最後水足したあとは減らないので注意。

## ソースコード

```python:main.py
import sys
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())
def err(*args): print(*args, file=sys.stderr)

def main():
    N = rI()
    T0, V0 = rLI()
    ans = V0
    for _ in range(N-1):
        T, V = rLI()
        ans = max(0,ans-(T-T0))
        ans += V
        T0 = T 
    print(ans)
    
if __name__ == '__main__':
    main()

```

# B

grid問題つらい…
まだB問題だから総当たりで解いても大丈夫
しかし実装に時間かかった😇

## ソースコード

```python:main.py
from itertools import combinations, product
import sys
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())
def err(*args): print(*args, file=sys.stderr)

dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]

def out_of_bounds(y, x, h, w):
    return y < 0 or y >= h or x < 0 or x >= w

def main():
    
    H, W, D = rLI()
    
    grid = [[] for i in range(H)]
    
    floors = []
    
    for i in range(H):
        grid[i] = list(rS())
        # err(grid[i])
        for j,s in enumerate(grid[i], start=0):
            if s==".":
                floors.append((i,j))
    ans = 2
    X = [(i,j) for i, j in product(range(-D,-~D),repeat=2) if abs(i) + abs(j) <= D]
    # for x in X:
    #     err(x,sum(map(abs,x)))
    # err(floors)
    for a0,b0 in combinations(floors,2):
        humided = {a0,b0}
        cnt = 2
        for c0 in [a0,b0]:
            for i,j in X:
                ci0,cj0 = c0
                ci, cj = (ci0+i,cj0+j)
                c = ci,cj
                if out_of_bounds(ci,cj,H,W) or grid[ci][cj] == "#": continue
                if c not in humided:
                    cnt += 1
                    humided.add(c)
        if cnt > ans:
            # err(a0,b0,cnt,humided)
            ans = cnt
    print(ans)
    
if __name__ == '__main__':
    main()

```

# C

またgrid問題…やめてください4んでしまいます

Hが入っている頂点からBFSをする発想はできたんですよ？
しかしTLEが解消できなかったorz
最初にHの頂点全部入れる発想があれば解けたんだけどなあ😢

余談だけど公式解説がいつものフレーズ書いていて草生えそうになったのは内緒
> この問題は多始点BFSの練習問題です。

## ソースコード

<details><summary>競技時間TLEコード</summary>

```python:main.py
from collections import deque, defaultdict
import sys
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())
def err(*args): print(*args, file=sys.stderr)

dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]

dd = defaultdict(lambda: float("inf"))


def out_of_bounds(y, x, h, w):
    return y < 0 or y >= h or x < 0 or x >= w

def main():
    
    H, W, D = rLI()
    
    grid = [[] for i in range(H)]
    
    floors = set()
    humids = []
    humided = set()
    ans = 0
    for i in range(H):
        grid[i] = list(rS())
        # err(grid[i])
        for j,s in enumerate(grid[i], start=0):
            if s==".":
                floors.add((i,j))
            if s=="H":
                humids.append((i,j))
    for h in humids:
        queue = deque([(h,0)])
        while queue:
            cur, d = queue.popleft()
            if cur not in humided:
                humided.add(cur)
                dd[cur]=d
                ans+=1
                if d < D:
                    ci,cj = cur
                    for i,j in zip(dy,dx):
                        nxt = ci+i,cj+j
                        if out_of_bounds(nxt[0],nxt[1],H,W):continue
                        if nxt in floors:
                            queue.append((nxt,d+1))
            elif d<dd[cur]:
                ci,cj = cur
                for i,j in zip(dy,dx):
                    nxt = ci+i,cj+j
                    if out_of_bounds(nxt[0],nxt[1],H,W):continue
                    if nxt in floors:
                        queue.append((nxt,d+1))
    print(ans)
    
if __name__ == '__main__':
    main()

```

</details>



<details><summary>競技終了後ACコード</summary>

```python:main.py
from collections import deque, defaultdict
import sys
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())
def err(*args): print(*args, file=sys.stderr)

dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]

dd = defaultdict(lambda: float("inf"))


def out_of_bounds(y, x, h, w):
    return y < 0 or y >= h or x < 0 or x >= w

def main():
    
    H, W, D = rLI()
    
    grid = [[] for i in range(H)]
    
    floors = set()
    humids = []
    humided = set()
    ans = 0
    for i in range(H):
        grid[i] = list(rS())
        # err(grid[i])
        for j,s in enumerate(grid[i], start=0):
            if s==".":
                floors.add((i,j))
            if s=="H":
                humids.append((i,j))
    
    queue = deque([(h,0) for h in humids])
    while queue:
        cur, d = queue.popleft()
        if cur not in humided:
            humided.add(cur)
            dd[cur]=d
            ans+=1
            if d < D:
                ci,cj = cur
                for i,j in zip(dy,dx):
                    nxt = ci+i,cj+j
                    if out_of_bounds(nxt[0],nxt[1],H,W):continue
                    if nxt in floors:
                        queue.append((nxt,d+1))
    print(ans)
    
if __name__ == '__main__':
    main()

```

</details>


# D

C問題を一回TLEしたあとギリギリまでここに取り掛かっていた。

N^(0.5)以下の素数を列挙した場合をp,q(p<q)とした場合
p^8もしくはp^2*q^2がN以下の場合その値は条件を満たすのでカウントする。
前者は一つずつチェックすればいいが、後者の組み合わせが多いので尺取法で頑張る。

解のカウント方法ミスって1ペナもらってしまった。

## ソースコード

```python:main.py
import sys
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())
def err(*args): print(*args, file=sys.stderr)

def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = i * i
            if j > n:break
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime, table

def main():
    N = rI()
    p,t= sieve(int(N**(1/2)))
    x= sum(p)
    # err(x)
    ans = 0
    for x in t:
        if x**8 <= N:
            ans+=1
    p2 = list(map(lambda p:p*p,t))
    l=0
    r=len(p2)-1
    while l < r:
        m = N//p2[l]
        while p2[r] > m: r-=1
        # if N==200:err(l,r,p2[l],p2[r])
        ans += max(0,r-l)
        l+=1

    print(ans)
    
    
    
if __name__ == '__main__':
    main()

```

# E

グラフはまだまだ慣れません

# F

解説によると動的計画法で行けるらしい
時間あれば解きたい

# G

解説は何かdpとか記号あったけど
分割統治法でやるとかどうとか。

アルゴリズムの授業で聞いたことあるワードだけど
G問題なのでやることは複雑ですねぇ…

# まとめ

BFSの感覚が足りていないのが残念なところ
グリッド問題苦手すぎて逃げてきたツケが回ってきたという話。

当たり前だが好みのジャンルばかりしないで
苦手な分野も解けるようにしないと地力はつかないね