ABC330(A~E)をPythonで解く

# A: Counting Passes 

https://atcoder.jp/contests/abc330/tasks/abc330_a

順番にL点以上を取っているか確認します。


<details><summary>コード</summary>

```python
N, L = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
for i in range(N):
    if A[i] >= L:
        ans += 1

print(ans)
```

</details>

# B: Minimize Abs 1 

https://atcoder.jp/contests/abc330/tasks/abc330_b

与えられたリストのそれぞれの要素について2つの条件を満たす整数$X_{i}$を求めよとのことなので、条件をそれぞれ見ていきます。

$L \leq X_{i} \leq R$


$L以上R以下であるようなどの整数Yについても |X_{i}-A_{i}| \leq |Y-A_{i}| を満たす。$


一つ目の条件から、求める答えは$L$以上$R$以下であることがわかります。

二つ目の条件ですが、不等式の左辺はリストの要素 $A_{i}$ と$X_{i}$の差の絶対値です。とりあえずこれを小さくすればいいとわかります。

不等式の右辺は$L$以上$R$以下の任意の整数$Y$とリストの要素 $A_{i}$ の差の絶対値なので、$A_{i}$になるべく近い数を選んで小さくすることができます。

なので、求める$X_{i}$は$L$以上$R$以下の数で最も$A_{i}$に近い数です。

1. $A_{i}$が$L$より小さいとき、$L$以上$R$以下の数で最も$A_{i}$に近い数は$L$です。
2. $A_{i}$が$R$より大きいとき、$L$以上$R$以下の数で最も$A_{i}$に近い数は$R$です。
3. $L \leq A_{i} \leq R$のとき、$L$以上$R$以下の数で最も$A_{i}$に近い数は$A_{i}$自身です。

これを実装すると以下のようになります。

<details><summary>コード</summary>

```python
N, L, R = map(int, input().split())
A = list(map(int, input().split()))
ans = []
for i in range(N):
    if A[i] < L:
        ans.append(L)
    elif A[i] > R:
        ans.append(R)
    else:
        ans.append(A[i])

print(*ans)
```

</details>

# C: Minimize Abs 2

https://atcoder.jp/contests/abc330/tasks/abc330_c

$|x^2+y^2-D| = |y^2-(D-x^2)| = |(D-x^2)-y^2|$

したがって$x$を決めると$y$もそのまま決めることができます。
$x$の範囲ですが、$D$より大きいものは考えなくていいので$\sqrt{D}$までで良いです。

$D-x^2$と$y$の差を最小にしたいので、$y$は$\sqrt{D-x^2}$になるべく近づけます。
`int()`は小数点以下を切り捨てするので、$y = int (\sqrt{D-x^2}), int (\sqrt{D-x^2})+1$の両方をありうる$x$の全てにおいて確認すると答えを求めることができます。

<details><summary>コード</summary>

```python
D = int(input())

ans = []

for x in range(1, int(D**0.5)+1):
    d = D - x**2
    y = int(d**0.5)

    ans.append(abs(x**2+y**2-D))
    ans.append(abs(x**2+(y+1)**2-D))

print(min(ans))

```

</details>


# D: Counting Ls 

https://atcoder.jp/contests/abc330/tasks/abc330_d

問題文から文意が少しつかみづらいですが、解答例を見てみると「`o`があるマスに存在しているとき、同じ列から一つ`o`を、同じ行から一つ`o`を選ぶ」ことで条件を全て満たすような3マスを取ることができます。具体的には、例えばあるマスが`o`であり、同じ行にそのマスを含めて4個、同じ列にそのマスを含めて5個の`o`があるとき、自分以外の二つの`o`の選び方は $(4-1)\times(5-1)=15$通りです。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2611731/0f912eb7-2226-0a66-9dcf-d986eb24a323.png)


よって、各行、各列に`o`が何個あるのかまずは計算します。

<details><summary>コード</summary>

```python
N = int(input())
S = [input() for _ in range(N)]

row_cnt = [S[i].count("o") for i in range(N)]
col_cnt = [(0) for _ in range(N)]

for c in range(N):
    for r in range(N):
        col_cnt[c] += 1 if S[r][c] == "o" else 0
```

</details>

各行の`o`の個数は`count()`で、各列の`o`の個数は累積和で求めることができます。

以上の計算を前以てしておくことで、あとはマスをひとつづつ確認し、あり得る組の数を足していくだけで答えが出ます。

<details><summary>コード</summary>

```python

N = int(input())
S = [input() for _ in range(N)]
row_cnt = [S[i].count("o") for i in range(N)]
col_cnt = [(0) for _ in range(N)]

for c in range(N):
    for r in range(N):
        col_cnt[c] += 1 if S[r][c] == "o" else 0

ans = 0


for row in range(N):
    for col in range(N):
        ans += (row_cnt[row]-1) * (col_cnt[col]-1) if S[row][col] == "o" else 0

print(ans)
```

</details>


# E: Mex and Update 

https://atcoder.jp/contests/abc330/tasks/abc330_e

数列$A$内の各要素の個数と$A$内に含まれていない数字をそれぞれ管理します。性質上、長さ$N$の数列におけるmexは必ず$N$以下となります（長さ$N$の順列におけるmexが$N$であるため）。

まずは数列$A$、各要素の個数を格納した辞書`cnt`、含まれていない数字の集合`mex`を用意します。


各クエリに対して、以下の操作をします。

1. 入力を受け取る
2. 置き換えられる要素の個数を`cnt`で1減らす
3. 置き換える要素の個数を`cnt`で1増やす
4. もし置き換えられた要素の個数が0なら`mex`に追加する
5. 数列$A$内で要素を実際に置き換える
6. 置き換えた要素が`mex`に存在している場合、それを削除する
7. `mex`内の最小の要素を出力する

これを可能にするためには、`mex`は
1. 要素の追加
2. 要素の削除
3. 最小要素の出力

が高速で可能なデータ型を用意することが求められます。

例えば、`sortedcontainers`の`SortedSet`でこれが可能です。


<details><summary>コード</summary>

```python
from collections import defaultdict
from sortedcontainers import SortedSet

N, Q = map(int, input().split())
A = list(map(int, input().split()))
cnt = defaultdict(int)
mex = SortedSet([])

for i in A:
    cnt[i] += 1

for j in range(N+1):
    if cnt[j] == 0:
        mex.add(j)

for _ in range(Q):
    i, x = map(int, input().split())
    cnt[A[i-1]] -= 1
    cnt[x] += 1
    
    if cnt[A[i-1]] == 0:
        mex.add(A[i-1])

    A[i-1] = x

    if cnt[x] == 1:
        mex.discard(x)

    print(mex[0])
```

</details>