ABC395振り返り


前回の振り返り

https://qiita.com/comet725/items/d2f53af25345f6504a0c


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


https://atcoder.jp/contests/abc395

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

# A

順番にみて、条件から外れたらNo出して終了
生き残ったら該当するのでYes

## ソースコード

```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()
    for i in range(1,N):
        if A[i-1]>=A[i]:
            print("No")
            break
    else:
        print("Yes")
    
if __name__ == '__main__':
    main()

```

# B

高速な実装もあるけど
Nの成約的にそのままやっても制限時間収まるので素直に実装

## ソースコード

```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()
    s = [["?"]*N for _ in range(N)]
    for i in range(N):
        j = N-i
        c = "#."[i%2]
        for y in range(i,j):
            for x in range(i,j):
                s[y][x]=c
    for i in range(N):
        print("".join(s[i]))
if __name__ == '__main__':
    main()

```

# C

値が重複していなかったら-1
重複していたらその値の位置を順番を保存。
同じ数の感覚が一番短いのを探す

defaultdict君活躍の巻

## ソースコード

```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()
    dc = defaultdict(lambda: 0)
    di = defaultdict(list)
    s = set()
    for i,a in enumerate(A, start=1):
        di[a].append(i)
        dc[a]+=1
        if dc[a] == 2:
           s.add(a)
    if len(s) == 0:
        print(-1)
        return
    ans = float('inf')
    for a in s:
        # err(a,dc[a],di[a],ans)
        for i in range(1,dc[a]):
            ans = min(ans,di[a][i]-di[a][i-1]+1)
    print(ans)
    
if __name__ == '__main__':
    main()

```

# D

2番めの操作を軽くしようとして失敗

## ソースコード

<details><summary>TLEコード</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, Q = rLI()
    A = defaultdict(set)
    T=set()
    ops = []
    for _ in range(Q):
        op = rLI()
        ops.append(op)
        if op[0]==3:
            T.add(op[1])
    P = {t:t for t in T}        
    for t in T:
        A[t].add(t)
    # if IS_LOCAL:err(dict(A))
    for op in ops:
        q = op[0]
        if q == 1:
            a,b= op[1:]
            if a not in T:continue
            p = P[a]
            # err(p,A[p])
            A[p].remove(a)
            A[b].add(a)
            P[a]=b
        if q == 2:
            a,b= op[1:]
            for k in A[a]:
                P[k] = b
            for k in A[b]:
                P[k] = a
            A[a],A[b]=A[b],A[a]
        if q == 3:
            a = op[1]
            print(P[a])
            
    
if __name__ == '__main__':
    main()

```

このfor文を消す方法がわからなかった。
```python
for k in A[a]:
    P[k] = b
for k in A[b]:
    P[k] = a
```

</details>


# E

ダイクストラ使うんだろうなと思ったくらい。

# 感想

3問しかACできなかったけどunratedにしたのでセーフ(?)

Dが安定して解けるまでしばらくunratedかね...