AtCoderをPythonで取り組んだ振り返り(ABC399 A,B、C問題追加)

どうもこんにちは！

今週もAtCoderのコンテストに参加できたので、記録がてら振り返ります。
今回はBまで完答。Cはグラフに関する問題で、手が出せず。森という概念を初めて聞いた気がしました。

問題

問題は以下のリンクから。取り組めたA,Bを振り返ります。

A - Hamming Distance -

同じ長さの文字列が2つ与えられるので、n文字目が異なる個数を回答する問題。シンプルに1文字ずつ比較して数えました。

n = int(input())
s = input()
t = input()
ans = 0
for i in range(n):
  if s[i] != t[i]:
    ans += 1

print(ans)

B - Ranking with Ties -

n人分の試験の点数が与えられるので、その順位付けをするという問題。同じ点数の場合は同順位として、次はその人数を飛ばした順位になります。例えば1位が2人いたら、その次の点数の人は3位となる感じです。

n = int(input())
s = [int(x) for x in input().split()]
ans = [0] * n
r = 1
#print(ans)

while r < n+1:
  k,m = 0,0
  for i in range(n):
      if ans[i] == 0:
          m = max(m,s[i])
#  print(m)
  k = s.count(m)
  for i in range(n):
    if s[i] == m:
      ans[i] = r
  r += k

for i in ans:
    print(i)

--- 2025/9/25追記 ---
緑コーダー目指してC問題取り組みました。

C

与えられたグラフから閉路がない状態にするとき、最小で何本の辺を削除するかを出力する問題。
よくわからず[Python] ABC399 C Make it Forestを参考にさせていただきました。
Union-Findを使って与えられた辺を１本ずつ追加してグラフを作っていくとして、辺を結ぶ2点がすでに1つのグラフを構成している場合は追加する辺が不要と判断できるので、その本数を出力する形で解けるとのこと。

class UnionFind:
    def __init__(self,n):
        self.par = list(range(n))
        
    def root(self,x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]
    
    def same(self,x,y):
        return self.root(x) == self.root(y)
    
    def merge(self,x,y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        self.par[x] = y


n,m = map(int,input().split())
g = [list(map(int,input().split())) for _ in range(m)]

ans = 0
union = UnionFind(n)
for i in range(m):
    u = g[i][0]-1
    v = g[i][1]-1
    
    if union.same(u,v):
        ans += 1
    else:
        union.merge(u,v)

print(ans)

--- 追記ここまで ---

おわりに

今回はグラフの勉強不足につきます。4月になるので目標は未達、問題を解けるように、落ち着いて1つずつ勉強を進めたいと思います。

ではでは。