[ABC399] ABC 399(Atcoder Beginner Contest)のA~D(A,B,C,D)問題をPythonで解説(復習)

A問題

左から順番に比較する。

A.py

"""
<方針>
- 左から順番に比較する。
"""
# 入力
N = int(input())
S = input()
T = input()

# 違う回数
ans = 0
# 左から順番に見る
for i in range(N):
  # 文字が違う時
  if(S[i] != T[i]):
    # 違う回数を増やす。
    ans += 1

# 出力
print(ans)

B問題

順位をまとめた変数 ranks を用意しておき、それを埋めていく。
得点を set して重複を消して、sort し、高い順番に該当する人を見る。
最後に ranks を改行区切りで出力する。

B.py

"""
<方針>
- 順位をまとめた変数 `ranks` を用意しておき、それを埋めていく。
- 得点を `set` して重複を消して、`sort` し、高い順番に該当する人を見る。
- 最後に `ranks` を改行区切りで出力する。
"""
# 入力
N = int(input())
P = list(map(int, input().split()))


# 答え
ranks = [None]*N

# 順位
r = 1

# 重複の無いスコアを高い順番に見ていく。
for p in sorted(set(P), reverse=True):
  # pを取った人数をカウント
  cnt = 0
  # それぞれの得点を見る。
  for i in range(N):
    # pと同じスコアを取った時、
    if(p == P[i]):
      ranks[i] = r # 順位を決める
      cnt += 1 # 人数をカウント
  
  # 次のrを取得
  r += cnt

# 出力
for rank in ranks:
  print(rank)

C問題

方針

グラフがどう繋がっているかは重要ではない。連結しているかどうかが知りたい。だkら、UnionFind で解く。
union されている回数だけ出力すれば良さそう。
計算量は多分 O(M) くらいで、union はアッカーマン関数の逆関数だったか忘れたけど、超ちっちゃいから気にしなくて良い。

前提

C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう．
AとB問題では，基本的に制約条件を見ずにやっても解ける．
しかし，C問題以降では，制約条件を見ないと必ずTLEすると思っても良い．
詳しい話は私の352回の記事のC問題の解説に記したので，是非参照してほしい．

C.py

"""
<方針>
- グラフがどう繋がっているかは重要ではない。連結しているかどうかが知りたい。だkら、`UnionFind` で解く。
- `union` されている回数だけ出力すれば良さそう。
- 計算量は多分 `O(M)` くらいで、`union` はアッカーマン関数の逆関数だったか忘れたけど、超ちっちゃいから気にしなくて良い。
"""
"""クラス"""
class UF:
  """UnionFind"""
  def __init__(self, N):
    self.p = [-1]*N
    
  def f(self, x):
    if self.p[x] < 0:
      return x
    else:
      self.p[x] = self.f(self.p[x])
      return self.p[x]
  
  def u(self, x, y):
    x = self.f(x)
    y = self.f(y)
    
    if(x == y):
      return False
    else:
      if(self.p[x] < self.p[y]):
        x, y = y, x
      
      self.p[x] += self.p[y]
      self.p[y] = x
      return True

"""処理"""
N, M = map(int, input().split())
# UnionFindを初期化
uf = UF(N+1)

# 既に連結だった回数
ans = 0
for _ in range(M):
  u, v = map(int, input().split())
  # unionを行う。
  if not (uf.u(u, v)):
    # 既にunionされていれば、答えをインクリメント
    ans += 1

# 出力
print(ans)

D問題

スワッピングする対象は、自分と同じ数字の前後の位置だけで良い。

D.py

"""
<方針>
- スワッピングする対象は、自分と同じ数字の前後の位置だけで良い。
"""
T = int(input())
for _ in range(T):
  N = int(input())
  A = list(map(int, input().split()))
  A = [a-1 for a in A] # 0-indexed data
  B = [[] for _ in range(N)] # ペアの数字の位置を格納
  C = [None]*(2*N) # ペアの位置を格納
  
  # Bを作成
  for i in range(2*N):
    B[A[i]].append(i)
  
  # ペアの個数
  ans = 0
  # ペアを重複なくカウントするためのset
  se = set()
  # Cを作成
  for u, v in B:
    # 隣り合っていなければ登録する。
    if(abs(u-v) > 1):
      C[u] = v
      C[v] = u
  
  # 左からスワッピングを試みる
  for i in range(2*N):
    # 隣り合っているケースは無視
    if(C[i] is None):
      continue
    
    # スワッピングの位置はペアの左右の位置だけ
    for dx in [-1, 1]:
      swap = C[i] + dx
      # 範囲外条件 or スワッピング先が既に隣り合ってる or スワッピングしたとき隣り合わない条件
      if (not (0<=swap<2*N)) or (C[swap] is None) or (abs(C[swap] - i) > 1):
        continue
      
      a = A[i]
      b = A[C[i]+dx]
      ke = a*(2*N) + b
      
      # a>b or 登録したことあり
      if(a>b) or (ke in se):
        continue
      
      # 重複対策
      se.add(ke)
      
      # 追加
      ans += 1
  
  print(ans)

補足

関係するリンク(参考文献など)

今回のコンテスト

筆者について

その他

間違いを含んでいる可能性があります．
方針と言いつつ，方針ではない感想などを書いている可能性があります．
A問題から解説がだんだん省略されます．
コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．

最後に一言

Diffが見えない間はとりあえずA~Dにだけなりそうです。