AtCoder Beginners Contest 309 (ABC309) をPythonで解きました。
見やすいコードを書く練習も兼ねてます。
A - Nine
問題ページ
考察
「左右」に隣接する組み合わせなのに注意しましょう。
Yesを出力する $(A,B)$ の組み合わせは $6$ つです。エレガントな書き方もありそうですが、これくらいなら全部書いちゃうのが楽だと思います。
コード
A, B = map(int, input().split())
P = [
(1, 2),
(2, 3),
(4, 5),
(5, 6),
(7, 8),
(8, 9)
]
if (A, B) in P:
print("Yes")
else:
print("No")
B - Rotate
問題ページ
考察
問題文の通りに、外側のマスを時計回りに動かします。
入力で受け取った $A$ とは別に、答えとして出力する用のリスト $B$ を用意してあげると楽です。
実装については、下のコードを参考にしてください。
コード
N = int(input())
A = [input() for _ in range(N)]
B = [list(a) for a in A]
for i in range(N - 1):
B[0][i + 1] = A[0][i] # 上の辺
B[N - 1][i] = A[N - 1][i + 1] # 下の辺
B[i + 1][N - 1] = A[i][N - 1] # 右の辺
B[i][0] = A[i + 1][0] # 左の辺
for b in B:
print(*b, sep="")
C - Medicine
問題ページ
考察
「 $a$ 日目まで薬を $b$ 錠だけ飲む」を、「 $a+1$ 日目以降は飲む薬が $b$ 錠だけ減る」と言い換えてみます。
入力で与えられる $(a,b)$ を $a$ の昇順にソートしてあげます。また、 $1$日目に飲む薬の数を事前に計算しておきます。
$a$ の小さいものから順に見ていって、飲む薬の数を実際にシミュレートしていき、その数が $K$ 以下になった時点でその日にちを出力してあげればACです。
実装の工夫として、 「$1$ 日目以降は飲む薬が $0$ だけ減る」を表す $(1,0)$ も追加してあげると、初日から飲む薬の数が $K$ 以下の場合にも正しくACできます。
コード
N, K = map(int, input().split())
A = [(1, 0)]
cnt = 0
for _ in range(N):
a, b = map(int, input().split())
A.append((a + 1, b))
cnt += b
A.sort()
for a, b in A:
cnt -= b
if cnt <= K:
print(a)
exit()
D - Add One Edge
問題ページ
考察
「頂点 $1$ から最も遠い点」と、「頂点 $N_1+N_2$ から最も遠い点」の $2$ 点を結んであげればokです。
問題で聞かれているのは距離だけです。
「頂点 $1$ から最も遠い点までの距離」と、「頂点 $N_1+N_2$ から最も遠い点までの距離」を求めて、そこに $2$点を結んだ分の距離 $1$ を足してあげて答えになります。
コード
from collections import deque
N1, N2, M = map(int, input().split())
G = [[] for _ in range(N1 + N2)]
for _ in range(M):
a, b = map(int, input().split())
a, b = a - 1, b - 1
G[a].append(b)
G[b].append(a)
def bfs(s):
que = deque()
que.append(s)
dist = [-1] * len(G)
dist[s] = 0
while que:
v = que.popleft()
for nv in G[v]:
if dist[nv] == -1:
dist[nv] = dist[v] + 1
que.append(nv)
return max(dist)
print(bfs(0) + bfs(N1 + N2 - 1) + 1)
E - Family and Insurance
問題ページ
考察
「 $y_i$ 代先までの子たちが対象」を「 $y_i + 1$ のパワーを持っている」と言い換えます。
パワーは、 $1$ つ下の代に行くごとに $1$ だけ減っていくものとします。そして、下の代へと受け継いでいる過程で、より大きなパワーを持っている人が現れた場合、そのパワーを採用することにします。
答えは、パワーが $1$ 以上の人の数になります。
人 $1$ から順に下の代へと見ていくのは BFSでもDFSでもいいです。個人的にBFSの方が書きやすいので、下のコードではBFSで人 $1$ から人 $N$ まで見ています。
コード
from collections import deque
N, M = map(int, input().split())
p = [-1] + list(map(int, input().split()))
# chs[i]: 人iの子リスト
chs = [[] for _ in range(N)]
for i, pa in enumerate(p):
if i == 0:
continue
chs[pa - 1].append(i)
power = [0] * N
for _ in range(M):
x, y = map(int, input().split())
x -= 1
y += 1
power[x] = max(power[x], y)
que = deque()
que.append(0)
seen = set()
while que:
v = que.popleft()
cost = power[v]
for ch in chs[v]:
que.append(ch)
power[ch] = max(power[ch], cost - 1)
ans = 0
for el in power:
if el > 0:
ans += 1
print(ans)
F - Box in Box
問題ページ
考察
幅・高さ・奥行きの $3$ つは入れ替えが自由ですが、幅 $\leq$ 高さ $\leq$ 奥行き と固定することにします。こうしなくてもすっぽりとハマる箱のペアがあったとき、その箱のペアは 幅 $\leq$ 高さ $\leq$ 奥行き としてもすっぽりはめられるからです。
幅が昇順になるように、箱たちをソートします。こうすると、箱リストを左から順に見ていったときに、箱の幅は気にする必要がなくなります。
こうして左から順に見ていくと、「今までで見終わった箱たちの中で、今見ている箱の高さ・奥行き $\geq$ ある箱の高さ・奥行き、 になるような箱が存在するか」が分かるようにしたくなります。
愚直にするなら、 Height[depth]: 奥行きdepthのときの最小の高さ、となるリストを用意してあげることになりますが、これだとしんどそうです。
具体的にしんどいのは次の2つです。
- しんどいポイント1: 奥行きの最大値が $10^9$ なせいで、長さ $10^9$ のリストが必要になる。
- しんどいポイント2: 奥行きが $d$ 未満のものについて調べたいとき、 [1,d) の区間を1つ1つ調べないといけない。
実は、この2つはどちらも解決してあげられます。
奥行きの最大値が $10^9$ なのについては、今回は奥行きの実際の値は全く気になってなくて、気になっているのは奥行き同士の大小関係だけです。これは座圧することで解決できて、Heightリストは 長さ$N$ だけ用意すればよくなりました。
[1,d) の区間を1つ1つ調べないといけないのについては、セグメントツリーをつかえば解決できます。さっきHeightリストの長さが $N$ で大丈夫なのが分かったので、[1,d)の区間の最小値を調べるの1回あたりで $O(logN)$ の計算量で済むので、全体でも $O(NlogN)$ の計算量で済みます。
これでほぼ解けました。
あと実は、同じ幅や高さのものも存在していて、判定に気をつける必要があります。
これは、幅の小さい順にソートしたときに、同時に2つ目のキーとして高さの大きい順にソートしてあげることで解決できます。
また別のやり方として、同じ幅のものはまとめて管理して、まとめたものそれぞれでYesになるかどうかを判定した後に、まとめたものをすべてセグメントツリーにつっこんであげてもokです。
コード
'''
syakayamiさん作、PythonバージョンのACLよりコピペしたものです。
使わせていただきありがとうございます！
https://github.com/shakayami/ACL-for-python/blob/master/segtree.py
・使い方(個人的なまとめ)
sg=segtree((初期値リストA), (演算func), (単位元ide_ele))
A: 初期値リスト。問題で与えられてるのをそのまま入れることが多い。
func, ide_ele: 演算とそれに対応する単位元。
例）add,0 (足し算、単位元0)
詳しいことは下のURLに書いてます。
https://github.com/shakayami/ACL-for-python/wiki/segtree
'''
# (コードが長くなるから省略。上のURLからコピペしてね。)
N = int(input())
Box = []
Vs = [[] for _ in range(3)]
for _ in range(N):
bi = list(map(int, input().split()))
bi.sort()
for i in range(3):
Vs[i].append(bi[i])
Box.append(bi)
# 座圧する
for i in range(3):
Vs[i].sort()
dic = [dict() for _ in range(3)]
for i in range(3):
for el in Vs[i]:
if el not in dic[i]:
v = len(dic[i])
dic[i][el] = v
for i in range(N):
for j in range(3):
Box[i][j] = dic[j][Box[i][j]]
# print(Box)
# box[0]の小さい順に箱を見てく
Box.sort(key=lambda x: (x[0], -x[1]))
st = segtree([1 << 60] * (N + 1), min, 1 << 60)
for a, b, c in Box:
if st.prod(0, b) < c:
print("Yes")
exit()
if st.prod(b, b + 1) > c:
st.set(b, c)
print("No")