AtCoder Beginner Contest 330の振り返り

結果はこちらです。

A - Counting Passes

この問題はA[i]がL以上かどうかを判定すればいいです。

N,L=map(int,input().split())
A=list(map(int,input().split()))
print(sum(1 for i in range(N) if A[i]>=L))

B - Minimize Abs 1

この問題は読解に苦労しました。要はmax(L,min(R,A[i]))をやれ、ということです。c++ではstd::clampというのがあるみたいです。pythonにはそれがないのでコンテスト終わった後実装した関数を貼っておくのでよかったら使ってください。

def clamp(val, low, high): return max(low, min(val, high))
N,L,R=map(int,input().split())
A=list(map(int,input().split()))
for i in range(N):A[i]=clamp(A[i],L,R)
print(*A)

C - Minimize Abs 2

この問題で苦労しました、、サンプルは3つともあっているのに何かが違う、、となって先にD問題を解いてから解きました。おそらく最初はyだけを求めて計算していたのですが、y+1も判定してあげることでACしました。また
Dの制約が2*10^12なのでxは10^6程度まで見てあげれば大丈夫です。
なぜ10^6まででいいかというとx*x+y*y-Dが絶対値なので
(10^6)*(10^6)=10^12なので制約を満たすからです。

from math import isqrt
D=int(input())
ans=float('inf')
x=0
while(x*x<=D):
  y=isqrt(D-x*x)
  ans=min(ans,abs(x*x+y*y-D),abs(x*x+(y+1)*(y+1)-D))
  x+=1
print(ans)

D - Counting Ls

この問題は、行、列でそれぞれ何個oがあるかをカウントし、最後に自分自身を引いた数を積の法則で求めれば大丈夫です。

N=int(input())
S=[list(input().rstrip()) for _ in range(N)]
r,c=[0 for _ in range(N)],[0 for _ in range(N)]
for i in range(N):
  for j in range(N):
    if(S[i][j]=='o'):
      r[i]+=1
      c[j]+=1
ans=0
for i in range(N):
  for j in range(N):
    if(S[i][j]=='o'):
      ans+=(r[i]-1)*(c[j]-1)
print(ans)

E - Mex and Update

この問題はpythonのSortedSet(c++のstd::setに相当)とリストの中にその数字が何個あるかをカウントするためにdefaultdictを使いました。

SortedSetについての簡単な説明

追加、検索、削除がそれぞれO(logN)でできるというc++でいうstd::set相当の機能を持っているデータ構造です。
s=SortedSet([3,4,5,1,3,1]) 計算量はO(N*logN)です。
s.add(3) 計算量はO(logN)です。
s.discard(3) 計算量はO(logN)です。またもしsの中にその数字がない場合は何も起こりません。
このほかにも二分探索などの機能もあり覚えておいて損はないと思います。

まずMEXになりうる数字を管理するためにmexというSortedSetをつくり0からN+1までの値を追加しました。また同時にAに何が何個あるのかをカウントするためにcntというdefaultdictを作成しインクリメントをしています。
各クエリに対してまずA[i-1]をデクリメントします。もしcnt[A[i-1]]が0になったということはその数字はMEXになりうるのでmexに追加します。
そしてA[i-1]をxに変更します。ここでcnt[A[i-1]]をインクリメントします。そのときcnt[A[i-1]]が1以上あるのであればそれはMEXにはならないためmexから削除します。
そしてmexの最初の値を出力することで各クエリに対してMEXを求めることができます。

from sortedcontainers import SortedSet
from collections import defaultdict

N,Q=map(int,input().split())
A=list(map(int,input().split()))
mex=SortedSet(range(N+1))
cnt=defaultdict(int)
for a in A:
  mex.discard(a)
  cnt[a]+=1
for _ in range(Q):
  i,x=map(int,input().split())
  cnt[A[i-1]]-=1
  if(cnt[A[i-1]]==0):mex.add(A[i-1])
  A[i-1]=x
  cnt[A[i-1]]+=1
  if(cnt[A[i-1]]>0):mex.discard(A[i-1])
  print(mex[0])

感想

今回はC問題で思った以上に苦戦しペナを量産してしまったので注意深く問題を解いていきたいと思います。