私は足踏みが得意です
これは厳しい(確信)。
こんばんはあじゃじゃです。それではABC399の復習をしていきます。
A.Hamming Distance
左から見るだけでいいです。
n=int(input())
s=input()
t=input()
ans=0
for i in range(n):
if s[i]!=t[i]:
ans+=1
print(ans)実家A問題よりこういうシンプルに書けるやつのほうが好き。
B.Ranking with Ties
難しい。得点を降順で見ることで順位をつけることができます。
n=int(input())
p=list(map(int,input().split()))
ans=[0]*n
cnt=0
d={}
for i in range(100,0,-1):
flg=0
for j in range(n):
if p[j]==i:
cnt+=1
if i not in d:
d[i]=cnt
if p[j]==i:
ans[j]=d[i]
print(*ans,sep="\n")こんな感じでしょうか。Chatgptに実装させたほうが分かりやすいコードが出力されそうですね。
C.Make it Forest
ループになる辺を除けばグラフが森になるのですでに連結な点同士を結ぶ辺のみを除いていけばよいです。すでに連結かどうか判定するのはDisjoint Set Union(UnionFind)で大体定数倍でできるのでO(N+M)時間くらいで通せます。
from atcoder.dsu import DSU
n,m=map(int,input().split())
uf=DSU(n+1)
ans=0
for _ in range(m):
u,v=map(int,input().split())
if uf.same(u,v):
ans+=1
uf.merge(u,v)
print(ans)実装が楽でうれしいね。1分30秒で書けた。
D.Switch Seats
考察が重いかな？という感じでごちゃごちゃやっていた。
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
pos=[[] for _ in range(n+1)]
for i in range(2*n):
ai=a[i]
pos[ai].append(i+1)
d={}
for i in range(1,n+1):
p=sorted(pos[i])
if p[1]==p[0]+1:
continue
d[(p[0],p[1])]=i
cnt=0
for (l,r) in d.keys():
if (l+1,r+1) in d:
cnt+=1
if (l+1,r-1) in d and r>=l+3:
cnt+=1
print(cnt)比較的実装がきれいだと思います。変なコーナーがあるのでそれに注意。
E.Replace
不可能。ループにしっぽがついたやつは損する手がないことに気づけなかった。
F.Range Power Sum
一瞬面を食らいますが、いったん落ち着いてみると二項展開をすることできれいに式変形ができるので後はそれを落ち着いて計算するだけ。
n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=998244353
class Comb:
def __init__(self,sup,mod=998244353):
self.sup=sup
self.mod=mod
self.inv=[1]
self.fact=[1]
for i in range(1,self.sup+1):
self.fact.append((self.fact[-1]*i)%self.mod)
self.inv.append((self.inv[-1]*pow(i,-1,mod))%self.mod)
def C(self,n,r):
assert(self.sup>n)
if r>n :return 0
return (self.fact[n]*self.inv[r]*self.inv[n-r])%self.mod
from itertools import accumulate
C=Comb(k+1)
p=list(accumulate(a,initial=0))
for i in range(n+1):
p[i]%=mod
dp=[[0]*(n+1) for _ in range(k+1)]
for i in range(k+1):
for j in range(n+1):
dp[i][j]=pow(p[j],i,mod) if i else 1
suf=[[0]*(n+1) for _ in range(k+1)]
for i in range(k+1):
for j in range(n-1,-1,-1):
suf[i][j]=(suf[i][j+1]+dp[i][j+1])%mod
ans=0
for i in range(k+1):
tmp=C.C(k,i)*pow(-1,i,mod)%mod
tp=0
for j in range(n):
tp+=(dp[i][j]*suf[k-i][j]%mod)
tp%=mod
ans+=tmp*tp%mod
ans%=mod
print(ans)添え字にi,jを使いすぎてバグらせたりしていたのでその辺も工夫していかないといけないなと思った。
まとめ
問題を上手に選んだので二回連続黄色perfを得ることができました！！！！！しかしなぜかまだ水色なので来週も頑張りたいです。年度内に青になりたかった…、それじゃあまた！！！！！
コメント