ABC330(A~E)をPythonで解く

A: Counting Passes

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

コード

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)

B: Minimize Abs 1

与えられたリストのそれぞれの要素について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}$自身です。

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

コード

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)

C: Minimize Abs 2

$|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$の全てにおいて確認すると答えを求めることができます。

コード

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))

D: Counting Ls

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

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

コード

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

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

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

コード

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)

E: Mex and Update

数列$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でこれが可能です。

コード

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])