AtCoder Beginners Contest 303 (ABC303) をPythonで解きました。
見やすいコードを書く練習も兼ねてます。
A - Similar String
問題ページ
difficulty: 22
入力
$N$: 与えられる文字列の長さ
$S$: 長さ$N$の文字列
$T$: 長さ$N$の文字列
考察
2つの文字列どちらも、"l"(エル)を"1"(いち)に変換して、"o"を"0"に変換します。
その変換をしたあとの$S$と$T$が一緒だったら答えはYesになります。
文字列の置き換えは、Pythonだとreplace関数があります。公式解説にはないですが、めちゃくちゃよく使う関数なので覚えておくのがオススメです！
コード
N = int(input())
S = input()
T = input()
S = S.replace('l', '1').replace('o', '0')
T = T.replace('l', '1').replace('o', '0')
if S == T:
print('Yes')
else:
print('No')
B - Discord
問題ページ
difficulty: 112
入力
$N$: 人数
$M$: 集合写真を撮った数
$A_{i,j}$: $i$番目の撮影で左から$j$番目に並んだ人の番号
考察
隣り合って撮影したことのあるペアを入れていくsetを用意します。
それぞれの集合写真で、隣り合ったペアを入れていきます。例えば人1と人2が隣り合っているとき、setには(人1, 人2)のペアと(人2, 人1)のペアどちらも入れておくことにします。
最終的にsetに入っているタプルの数の半分が、隣り合って撮影したペアの数です。
今回は隣り合って撮影したことのないペアの数を聞かれているので、考えられるペア全体$\frac{N(N-1)}{2}$から、先ほどの隣り合って撮影したペアの数を引くことで、答えが出ます。
コード
N, M = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(M)]
seen_pair = set()
for row in A:
for i in range(N - 1):
x, y = row[i], row[i + 1]
seen_pair.add((x, y))
seen_pair.add((y, x))
ans = N * (N - 1) // 2 - len(seen_pair) // 2
print(ans)
C - Dash
問題ページ
difficulty: 417
入力
$N$: 移動の数
$M$: 回復アイテムの数
$H$: 体力の初期値
$K$: 回復アイテムを使うと体力$K$になる
$S_i$: $i$回目の移動の向き
$x_i, y_i$: 回復アイテムのある座標
考察
回復アイテムは、座標をぜんぶsetにつっこんでおきます。回復アイテムをつかったときは、(setの名前).discard(要素)でsetから要素を消せます。Pythonのこの操作はO(1)で超はやいので心配ありません。
あとは言われたとおりに高橋くんを動かします。
下のコードでは、$dic['R']=(1, 0)$ となるような辞書を用意して実装してみました。事前に移動方向のリストや辞書をつくっておくといいケースは多々あって、クセづけておくといいかもです！
コード
N, M, H, K = map(int, input().split())
S = input()
heal = set()
for _ in range(M):
x, y = map(int, input().split())
heal.add((x, y))
st = 'RLUD'
tmp = [(1, 0), (-1, 0), (0, 1), (0, -1)]
dic = dict()
for s, t in zip(st, tmp):
dic[s] = t
nx, ny = 0, 0
for s in S:
vx, vy = dic[s]
nx += vx
ny += vy
H -= 1
if H < 0:
print('No')
exit()
if H < K and (nx, ny) in heal:
H = K
heal.discard((nx, ny))
print('Yes')
D - Shift vs. CapsLock
問題ページ
difficulty: 778
入力
$X$: aキーを押すのにかかる時間
$Y$: Shiftキー+aキーを押すのにかかる時間
$Z$: CapsLockキーを押すのにかかる時間
$S$: aとAだけで構成された、打ちたい文字列
考察
「動的計画法」と呼ばれる問題です。
dp[i][flag]: i文字目(1-indexed)を打ち終わって、Shiftキーの状態がflag(OFFのとき0, ONのとき1)になるための最短時間
となる配列dpをつかって解きます。
① CapsLockボタンを押したときに、dpが変わるかチェックしてから、
② 指定されたaかAのキーを打ち込む
の順番で操作するということにすると、少しだけ実装が楽になります。
コード
INF = 1 << 80
X, Y, Z = map(int, input().split())
S = input()
# dp[i][flag]: i文字目(1-indexed)を打ち終わって、
# Shiftキーの状態がflag(OFFのとき0, ONのとき1)になるための最短時間
dp = [[INF] * 2 for _ in range(len(S) + 1)]
dp[0][0] = 0
for i, s in enumerate(S):
# capslock on/off
dp[i][0] = min(dp[i][0], dp[i][1] + Z)
dp[i][1] = min(dp[i][1], dp[i][0] + Z)
# aかAを打つ。
if s == 'a':
dp[i + 1][0] = dp[i][0] + X
dp[i + 1][1] = dp[i][1] + Y
else:
dp[i + 1][0] = dp[i][0] + Y
dp[i + 1][1] = dp[i][1] + X
ans = min(dp[-1])
print(ans)
E - A Gift From the Stars
問題ページ
difficulty: 1113
入力
$N$: 頂点の数
$u_i, v_i$: 頂点$u_i$ と頂点$v_i$を辺で結ぶ
考察
次数1の頂点の数に注目します。
最初の星の数を$M$とすると、次数が2以上の頂点は$M$個あるので、最初の次数が1の頂点は$N-M$個あります。
2つの星をくっつける操作をするとき、両社の次数1の頂点を結ぶので、次数1の頂点は全体で見ると2つ減ることになります。
この操作は、最初の星が$M$個でこれが1つの連結グラフになるまで行われるので、合計で$M-1$回行われます。
つまり、すべての操作が終わった後の次数1の頂点の数は、$(N-M)-2(M-1)=N-3M+2$個あることになります。
よって、次数1の頂点の数を$cnt1$とすると、$M=\frac{N+2-cnt1}{3}$となります。
すべての操作後の木で、次数を大きい順に$M$個取ってくればそれが答えになります。
コード
N = int(input())
G = [[] for _ in range(N)]
for _ in range(N - 1):
u, v = map(int, input().split())
u, v = u - 1, v - 1
G[u].append(v)
G[v].append(u)
cnt1 = 0 # 木にある次数1の頂点の数
for g in G:
if len(g) == 1:
cnt1 += 1
star_cnt = (N + 2 - cnt1) // 3
cnt_list = [len(g) for g in G]
cnt_list.sort()
ans_list = []
for _ in range(star_cnt):
cnt = cnt_list.pop()
ans_list.append(cnt)
ans_list = ans_list[::-1]
print(*ans_list)