ABC347 with Python (A～E)

ABC347のA~E問題をpythonで解説していきます。個人的にはC問題が難しかったです。

# A - Divisible
## 問題
<p>正整数 $N,K$ 及び長さ $N$ の数列 $A=(A_1,A_2,\ldots,A_N)$ が与えられます。</p>
<p>$A$ に含まれる要素のうち、$K$ の倍数であるもののみを全て取り出し、それらを $K$ で割って出力してください。</p>

https://atcoder.jp/contests/abc347/tasks/abc347_a
## 考察
問題文の通り実装するだけ。

## コード
```python:A.py
N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = []
for a in A:
    if a % K == 0:
        ans.append(a // K)
print(*ans)
```
# B - Substring 
## 問題
<p>英小文字からなる文字列 $S$ が与えられます。$S$ の空でない部分文字列は何種類ありますか？</p>
<p>ただし、部分文字列とは連続する部分列のことを指します。例えば、<code>xxx</code> は <code>yxxxy</code> の部分文字列ですが、<code>xxyxx</code> の部分文字列ではありません。</p>

https://atcoder.jp/contests/abc347/tasks/abc347_b
## 考察
制約が緩いため、部分文字列を全列挙してset(重複を含まない性質あり)へ代入、その長さを表示すればよい。

## コード
```python:B.py
S = input()
candi = set()
LS = len(S)
for L in range(1, LS + 1): # 部分文字列の長さ
    for i in range(LS - L + 1): # 部分文字列の開始位置
        candi.add(S[i : i + L])
print(len(candi))
```
# C - Ideal Holidays
## 問題
<p>AtCoder 王国の $1$ 週間は $A+B$ 日からなり、$1$ 日目から $A$ 日目が休日で、$A+1$ 日目から $A+B$ 日目が平日です。</p>
<p>高橋くんは $N$ 個の予定があり、$i$ 番目の予定は今日から $D_i$ 日後です。</p>
<p>高橋くんは今日が $1$ 週間の何日目かを忘れてしまいました。高橋くんの $N$ 個の予定が全て休日である可能性があるかを判定してください。</p>

https://atcoder.jp/contests/abc347/tasks/abc347_c
## 考察
まず、1週間単位で見ればよいので、$D_i$すべてについて$A+B$で割ったあまりに変換する。その後、条件を満たすような場合は、下図の2パターンしか考えられない。よって、これを実装する。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3426433/f0aa112c-c191-3387-6413-fea7ebef42be.png)


## コード
```python:C.py
N, A, B = map(int, input().split())
D = list(map(int, input().split()))
D = [d % (A + B) for d in D]
D.sort()
for i in range(N - 1):
    if D[i + 1] - D[i] + 1 - 2 >= B:
        print("Yes")
        exit()
if D[-1] - D[0] + 1 <= A:
    print("Yes")
else:
    print("No")
```
# D - Popcount and XOR
## 問題
<p>非負整数 $a,b,C$ が与えられます。
次の $5$ つの条件をすべて満たす非負整数の組 $(X,Y)$ が存在するか判定し、存在するならひとつ出力してください。</p>
<ul>
<li>$0 \leq X < 2^{60}$</li>
<li>$0 \leq Y < 2^{60}$</li>
<li>$\operatorname{popcount}(X)=a$</li>
<li>$\operatorname{popcount}(Y)=b$</li>
<li>$X\oplus Y=C$</li>
</ul>
<p>ただし、$\oplus$ はビットごとの排他的論理和を表します。</p>
<p>条件を満たす $(X,Y)$ が複数存在する場合、どれを出力しても構いません。</p>
<details><summary>popcount とは？</summary>
<p>非負整数 $x$ について $x$ の popcount とは、$x$ を $2$ 進法で表記したときの $1$ の個数です。
より厳密には、非負整数 $x$ について $x=\sum_{i=0}^\infty b_i2^i\ (b_i\in\lbrace0,1\rbrace)$ が成り立っているとき $\operatorname{popcount}(x)=\sum_{i=0}^\infty b_i$ です。</p>
例えば、$13$ を $2$ 進法で表記すると $1101$ なので、 $\operatorname{popcount}(13)=3$ となります。

</details>

https://atcoder.jp/contests/abc347/tasks/abc347_d
## 考察
$\operatorname{popcount}(C)=c$とする。
まず、排他的論理和の性質から、$C$でビットが1となっているときは、$X$,$Y$のどちらかのビットが1、もう一方が0となっていなければならない。また、ビットが0となっているときは、$X$,$Y$のどちらのビットも1か0になっていなければならない。したがって、```a+b<c```となっていたり、```(a+b-c)%2!=0```であったりする場合は、条件を満たす$X$,$Y$が存在しない。また、$X$と$Y$がどちらのビットも1となるようなペアの個数をdとすると、```c+d>60```となる場合も条件を満たすものは存在しないことがわかる。
よって、$C$のビットを一つずつ見ていき、1だったならaとbどちらか大きい方のビットを1にする、0だったなら```a+b>c```かつaもbも0でない場合に両方のビットを1とする、という風に実装すればよい。最後に、```a>0```だったり```b>0```のように、使い切れなかった場合は条件を満たせないことに注意。

## コード
```python:D.py
a, b, C = map(int, input().split())
c = 0
for i in range(60):
    if (C >> i) & 1:
        c += 1
d = (a + b - c) // 2
if a + b - c < 0 or (a + b - c) % 2 != 0 or c + d > 60:
    print(-1)
    exit()
X = 0
Y = 0
for i in range(60):
    if (C >> i) & 1:
        if a > b:
            a -= 1
            X += 1 << i
        else:
            b -= 1
            Y += 1 << i
        c -= 1
    else:
        if a + b > c and a * b != 0:
            a -= 1
            b -= 1
            X += 1 << i
            Y += 1 << i
if a > 0 or b > 0:
    print(-1)
    exit()
print(X, Y)
```
# E - Set Add Query
## 問題
<p>全ての要素が $0$ で初期化された長さ $N$ の整数列 $A=(A_1,A_2,\ldots,A_N)$ があります。また、集合 $S$ があります。はじめ $S$ は空です。</p>
<p>以下の $Q$ 個のクエリを順に行います。$Q$ 個のクエリを全て処理した後の数列 $A$ の各要素の値を求めてください。 $i$ 番目のクエリは以下の形式です。</p>
<ul>
<li>整数 $x_i$ が与えられる。整数 $x_i$ が $S$ に含まれる場合、$S$ から $x_i$ を削除する。そうでない場合、$S$ に $x_i$ を追加する。次に、$j=1,2,\ldots,N$ について、$j\in S$ ならば $A_j$ に $|S|$ を加算する。</li>
</ul>
<p>なお、$|S|$ は集合 $S$ の要素数を意味します。例えば $S=\lbrace 3,4,7\rbrace$ のとき、$|S|=3$ です。</p>

https://atcoder.jp/contests/abc347/tasks/abc347_e
## 考察
$|S|$の各ターンの値がわかっていれば、例えば3~10ターンの間$x$が$S$に含まれていた場合、累積和を用いて$O(1)$でこの間に$x$に加算された数が計算できる(今回の実装だとacc[11]-acc[3]で計算できる)。

よって、各ターンの$|S|$の長さをset等で求めることと、ある数$x$がどのターンで$S$に追加され、どのターンで$S$から削除されるかを記録することをすればよい。

## コード
```python:E.py
N, Q = map(int, input().split())
X = list(map(int, input().split()))
LS = []
L = [[] for _ in range(N + 1)]
R = [[] for _ in range(N + 1)]
S = set()
for turn in range(Q):
    x = X[turn]
    if x in S:
        S.remove(x)
        R[x].append(turn)
    else:
        S.add(x)
        L[x].append(turn)
    LS.append(len(S))

acc = [0]
for ls in LS:
    acc.append(acc[-1] + ls)

ans = [0] * (N + 1)
for x in range(1, N + 1):
    for i in range(len(R[x])):
        l, r = L[x][i], R[x][i]
        ans[x] += acc[r] - acc[l]
    if len(R[x]) < len(L[x]):
        l = L[x][-1]
        ans[x] += acc[-1] - acc[l]
print(*ans[1:])
```