ABC377振り返り



[前回の振り返り](https://qiita.com/comet725/items/cb4c0af8271d2777e291)

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


https://atcoder.jp/contests/abc377

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


# A

A,B,Cが1個ずつならYES

## ソースコード

```python:main.py
import sys
from collections import Counter
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():
    S = rS()
    c = Counter(S)
    
    ans = all(c.get(s,0)==1 for s in "ABC")
    print('Yes' if ans else 'No')
    
if __name__ == '__main__':
    main()

```

# B

それぞれの行、列にルークがいないかをチェック

## ソースコード

```python:main.py
from itertools import 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)

def main():
    N = 8
    
    in_i = [0 for _ in range(N)]
    in_j = [0 for _ in range(N)]
    
    for i in range(N):
        S = rS()
        for j,s in enumerate(S):
            if s=="#":
                # err(i,j,"#")
                in_i[i] = 1
                in_j[j] = 1
    ans = 0
    # err(in_i)
    # err(in_j)
    for i,j in product(range(N),repeat=2):
        if in_i[i]==0 and in_j[j] == 0:
            # err(i,j,"put")
            ans += 1 
    
    print(ans)
    
if __name__ == '__main__':
    main()

```

# C
N×Nマスから置けないマスを除外していく

置けないマスとは、ナイトが置かれた位置
そしてナイトの動きが届くマスであり、

ナイトの置くマスと動きをリストで準備して、
置けないマスをsetで管理する

答えを最初Nの2乗で仮置きして
置けないマスが追加で発生するなら
そのたびに答えの数を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 main():
    N, M = rLI()
    k_move = [
        (0,0),
        (2,1),
        (1,2),
        (-2,1),
        (-1,2),
        (-2,-1),
        (-1,-2),
        (2,-1),
        (1,-2),
    ]
    
    ans = N**2
    
    cant_put = set()

    for i in range(M):
        a, b = rLI1()
        for i,j in k_move:
            ai = a+i
            bj = b+j
            
            if 0<=ai<N and 0<=bj<N and (ai,bj) not in cant_put:
                ans -= 1
                cant_put.add((ai,bj))
         
    print(ans)
    
if __name__ == '__main__':
    main()

```

# D

区間の右の値でソートして
尺取法する


## ソースコード

```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, M = rLI()
    
    segs = []
    k = set()
    for i in range(N):
        L, R = rLI1()
        segs.append((L,R))
        k.add((L,R))
    segs.sort(key=lambda m: m[1])
    i = 0
    ans = 0
    r = 0
    # err(segs)
    for l in range(M):
        if (l,l) in k:continue
        r = max(l,r)
        while segs[i][0] < l and i < N-1:i+=1
        # err(l,segs[i])
        while r+1<segs[i][1]:
            r+=1
        if i==N-1 and segs[i][0]<l:
            r = M-1
        # err(l,r, r-l+1)
        ans += r-l+1
    print(ans)
    
if __name__ == '__main__':
    main()

```

# E

この前の問題と形式似てんじゃん→ダブリングしてみる→サンプルケースのWAが取れない

解説によるとグラフとかサイクル的な概念を使うらしい…えー

# F

ルーク、ナイトに続いてクイーンだけど
斜めの管理がむずそうって感じ

# G
最後の3分くらいで問題眺めただけ

動的計画法つかうのね

# まとめ

久々の4完、入緑までもうすぐ

そろそろE問題を解ける地力をつけていきたい