abc294の備忘録(Python)

- PythonでAtcoderに参加する一般人の備忘録です。
- 解けた問題のソースコードと解き方のメモとなりますので**最適解ではない**ことが多々あります。
- ご指摘ありましたらコメントしていただければ気づいたときに返信します。

# 目次

[A-Filter](#a-filter)
[B-ASCII Art](#b-ascii-art)
[C-Merge Sequences](#c-merge-sequences)
[D-Bank](#d-bank)
[E-2xN Grid](#e-2xn-grid)

# A-Filter
**問題ページ**：[A-Filter](https://atcoder.jp/contests/abc294/tasks/abc294_a)
## 手法
入力が1行リストなので、要素を一つずつ確認し偶数のものを解答用リストに挿入ないし、出力します。
偶数の判定に関しては、$A$%$B$で$A$を$B$で割った余りを計算できます。
## コード
```python
def main():
    N = input()
    A = list(map(int,input().split())
    ans = []
    for i in A:
        if i % 2 == 0:
            ans.append(i)

    print(*ans)

if __name__ == '__main__':
    main()
```
# B-ASCII Art
**問題ページ**：[B-ASCII Art](https://atcoder.jp/contests/abc294/tasks/abc294_b)
## 手法
問題を解く上で必要となってくるポイントは数字をアルファベットに変換する点です。
これは、$chr(x)$関数で数値$x$をコードとする$Unicode$文字を求められるので利用しました。
アルファベット大文字は$65$~$90$、小文字は$97$~$123$ですが自分は忘れるので必要になる度に調べてます。
```python
def main():
    H,W = map(int,input().split()
    A = [list(map(int, input().split())) for l in range(H)]
    for i in range(H):
        temp = ''
        for j in range(W):
            if A[i][j] == 0:
                temp += '.'
            else:
                temp += chr(A[i][j]+64)
        print(temp)

if __name__ == '__main__':
    main()
```
# C-Merge Sequences
**問題ページ**：[C-Merge Sequences](https://atcoder.jp/contests/abc294/tasks/abc294_c)
## 手法
$C$の$i$番目には$A$の要素と$B$の要素のどちらが入るのかを求める問題でした。
制約条件として二つのリストは一つとして同一の要素を持たず、入力時点で二つのリストはソート済みです。
$A[i]$と$B[j]$の要素を比較し、$A[i]$の方が小さければ$A[i]$を$n$に書き換えて$i$に$1$を加えて右に$1$つずらす作業を繰り返します。
※解答2は解答1が読みずらいため、後から$Deque$を使用して書き直したものになります。
## コード
### 解答1
```python
def main():
    N,M = map(int,input().split())
    A = list(map(int,input().split()))
    B = list(map(int,input().split()))
    
    indexA = 0
    indexB = 0
    for i in range(N+M):
        if indexA < N and indexB < M:
            if A[indexA] < B[indexB]:
                A[indexA] = i+1
                indexA += 1
            else:
                B[indexB] = i+1
                indexB += 1
        
        if indexA == N:
            for j in range(N+M-i-1):
                
                B[indexB+j] = i+j+2
            break
        if indexB == M:
            for j in range(N+M-i-1):
                A[indexA+j] = i+j+2
            break
    print(*A)
    print(*B)        
    
if __name__ == '_main__':
    main()
```
### 解答2(Deque使用)
``` python
from collections import deque
def main():
    N,M = map(int,input().split())
    A = deque()
    B = deque()
    AL = list(map(int,input().split()))
    BL = list(map(int,input().split()))
    indexlist_A = deque()
    indexlist_B = deque()
    for a in AL:
        A.append(a)
        
    for b in BL:
        B.append(b)

    for i in range(N+M):
        if len(A) > 0 and len(B) > 0:
            Ai = A.popleft()
            Bi = B.popleft()
            if Ai < Bi:
                indexlist_A.append(i+1)
                B.appendleft(Bi)
            
            if Ai > Bi:
                indexlist_B.append(i+1)
                A.appendleft(Ai)
                
        elif len(A) == 0 and len(B) > 0:
            B.popleft()
            indexlist_B.append(i+1)
            
        else:
            A.popleft()
            indexlist_A.append(i+1)
        
    print(*indexlist_A)
    print(*indexlist_B)

if __name__ == '__main__':
    main()
```

# D-Bank
**問題ページ**：[D-Bank](https://atcoder.jp/contests/abc294/tasks/abc294_d)
## 手法
$Query[i]$によって異なる処理が行われます。
- 1の場合：一度も呼び出していない最も小さい番号を呼び出し$Que$に挿入する。
- 2の場合：$i$を呼び出し番号$Que$から取り除く。
- 3の場合：解答用$Que$に呼び出し番号$Que$で左にあるものを一つ挿入する。
  
コードでは、$Query[i]$が$2$の場合には受付済み番号$Set$に挿入する操作のみ行い、$Query[i]$が$3$の場合に受付済み番号$Set$に含まれる番号を呼び出し番号$Que$から削除する操作を行った上で、最も小さい番号を解答用$Que$に挿入する操作行っています。

※$Deque$と$Set$を使用しています。
## コード
```python
from collections import deque()
def main():
    N,Q = map(int,input().split())
    ans = deque()
    call = deque()
    go = set()
    indicate = 1
    for _ in range(Q):
        print(*call)
        print(*go)
        
        query = inp.l()
        if query[0] == 1:
            call.append(indicate)
            indicate += 1

        if query[0] == 2:
            go.add(query[1])
        if query[0] == 3:
            while len(call) > 0:
                x = call.popleft()
                if x in go:
                    go.remove(x)
                else:
                    ans.append(x)
                    call.appendleft(x)
                    break
    print(*ans)
        
if __name__ == '__main__':
    main()
```
# E-2xN Grid
**問題ページ**：[E-2xN Grid](https://atcoder.jp/contests/abc294/tasks/abc294_e)
## 手法
$L$の範囲が広いため$i$番目が条件を満たしているか1つずつ確認していくのは諦めました。
この問題で必要なのは連長圧縮を適切に処理していくことでした。
問題では$L$列を連長圧縮することで$N_1+N_2$列まで圧縮し、制約より最大でも$2×10^5$の範囲に収まっています。

1行目と2行目の整数列の連長圧縮をそれぞれ$Deque$で管理し、1行目と2行目でどちらか、あるいは両方の整数が変わるポイント間を確認しながらカウントを行っていきます。
$l_1$と$l_2$で長い方を$Deque$に戻す。このとき$l_i$の値は$|l_1-l_2|$の値に変更しています。
また、$v_1$と$v_2$の値が等しい場合、問題の条件を満たしているので、条件を満たしている区間"$min(l_1,l_2)$"をカウントに加算していく。
この操作を$v_1$と$v_2$がなくなるまで繰り返すことで問題の解答を得られました。
## コード
```python
from collections import deque
def main():
    L,N1,N2 = map(int,input().split())
    v1 = deque()
    v2 = deque()
    l1 = deque()
    l2 = deque()
    for _ in range(N1):
        x,y = map(int,input().split())
        v1.append(x)
        l1.append(y)
    for _ in range(N2):
        x,y = map(int,input().split())
        v2.append(x)
        l2.append(y)
    count = 0
    while len(v1) > 0 and len(v2) > 0:
        v1t = v1.popleft()
        v2t = v2.popleft()
        l1t = l1.popleft()
        l2t = l2.popleft()
        if l1t < l2t:
            l2.appendleft(l2t-l1t)
            v2.appendleft(v2t)
            
            if v1t == v2t:
                count += l1t
        elif l1t > l2t:
            l1.appendleft(l1t-l2t)
            v1.appendleft(v1t)
        
            if v1t == v2t:
                count += l2t
        else:
            
            if v1t == v2t:
                count += l1t
    print(count)
            
        
if __name__ == '__main__':
    main()
```