[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)
補足
関係するリンク(参考文献など)
筆者について
- Atcoderアカウント
- 今回も不参加のため，成績なし．
- 解説で示したA問題の提出
- 解説で示したB問題の提出
- 解説で示したC問題の提出
- 解説で示したD問題の提出
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
最後に一言
- Diffが見えない間はとりあえずA~Dにだけなりそうです。