ABC386振り返り


前回の振り返り

https://qiita.com/comet725/items/94f09da688c4c40e23e1

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


https://atcoder.jp/contests/abc386

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

# A

Counterを2回ぶち込んで
同じカードが何枚あるかの数を割り出す

2枚あるカードが2種類もしくは、3枚あるカードが1種類のときが要件を満たす

## ソースコード

```python:main.py
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from itertools import product, accumulate, groupby
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():
    A = rLI()
    c0 = Counter(A)
    c1 = Counter(c0.values())
    ans = c1.get(2,0) == 2 or c1.get(3,0) == 1 
    print('Yes' if ans else 'No')
    
if __name__ == '__main__':
    main()

```

# B

頭から数えて、0が連続した数を覚える。
2連続のときや0以外が来たときに押す回数を調整

## ソースコード

```python:main.py
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from itertools import product, accumulate, groupby
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():
    S = rS()
    ans = 0
    t = 0
    for s in S:
        if s == "0":
            t += 1
            if t % 2 ==0:
                ans += 1
        else:
            if t % 2 == 1:
                ans += 1
            t = 0 
            ans += 1
        # err(s, t, ans)
    if t % 2 == 1:
        ans += 1
    print(ans)
    
if __name__ == '__main__':
    main()

```

# C

長さが同じ場合、何文字異なるのか。

長さが違う場合、何文字削除すれば同じ文字列になるか。

長さが大きい方をTに揃えて適当に計算。(最初はSを大きい方にしたらREでたので逆にした)

## ソースコード


```python:main.py
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from itertools import product, accumulate, groupby
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():
    K = rI()
    S = rS()
    T = rS()
    ss = len(S)
    st = len(T)
    if (sg := abs(ss-st)) > K:
        print("No")
        return
    # err(S,T,ss,st,sg)
    if sg > 0:
        if ss > st:
            ss,st=st,ss
            S,T=T,S
        ti=ki=0
        for s in S:
            while ti<st and T[ti]!=s:
                ti+=1
                ki+=1
            if ki > K:
                break
            ti += 1
        ans = ki <= K
    else:
        ans = sum(1 for s,t in zip(S,T) if s!=t) <= K
    print("Yes" if ans else "No")
         
if __name__ == '__main__':
    main()
```

# D

探索じゃないグリッド系はまだまだ苦手です…

# E

XORをサボってできるのかと思いきやTLE＆WA。

二項係数のKが大きいときも小さくなるケースを失念

## ソースコード

<details><summary>TLE&WA</summary>

```python:main.py
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from itertools import product, accumulate, groupby, combinations
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, K = rLI()
    A = rLI()
    Ab = list(map(lambda s:[int(a)for a in s],map(lambda s:s[2:],map(lambda a:f"{a:061b}",A))))
    # err(Ab)
    ans = 0
    # for a,c in zip(combinations(A,K),combinations(Ab,K)):
    for c in combinations(Ab,K):
        ret = 0
        for x in zip(*c):
            # if K<=2:err(x)
            ret <<=1
            ret += sum(x)%2
        # if K<=2:err(a,ret)
        ans = max(ans,ret)
    print(ans)
if __name__ == '__main__':
    main()

```


</details>

# F

Cの高難易度版ですか…
レーベンシュタイン距離とかいう概念を理解する必要があったみたい。

# G

グラフですか…

# まとめ

4完していない回が続いてとてもつらい