【AtCoder】PythonでABC325を解く
はじめに
abc325のA,B,C,D問題をPython3で解きます。
A問題: Takahashi san
問題の概要
与えられた名字と名前に対して、名字の方に敬称(san)を付けよ。
問題の考察
Pythonで文字列のフォーマットをいじるのに便利なf-stringを使って敬称を付けます。
コード
def main(): S, T = input().split() ans = f"{S} san" print(ans) if __name__ == "__main__": main()
B問題: World Meeting
問題の概要
ある国の拠点の時刻は世界標準時で0時のときに
時で、その拠点には
人の社員が所属している。各拠点の社員は、現地時間で09:00-18:00の時間帯のときのみ会議に参加できる。適切な開始時刻を選んで1時間の会議を設定するとき、会議の参加人数は最大で何人になるか。
コード
def solve(N, W, X): ans = 0 for t in range(24): total = sum(w for w, x in zip(W, X) if 9 <= (t + x) % 24 < 18) ans = max(ans, total) return ans def main(): N = int(input()) W = [] X = [] for _ in range(N): w, x = map(int, input().split()) W.append(w) X.append(x) ans = solve(N, W, X) print(ans) if __name__ == "__main__": main()
C問題: Sensors
問題の概要
のマス目にセンサが配置されている。上下左右斜めで隣接しているセンサ同士は、連動して動作する一纏まりのセンサ群として見なせる。センサ群は何個あるか。
問題の考察
幅優先探索やUnionFindで解くことができますが、ここではUnionFindで解きます。上下左右斜めで隣接しているセンサをUnionFindで同じ集合として結合し、最後に各集合の親がセンサか否かでセンサ群を数えます。
UnionFindのソースコードは、こちらから引用しました(https://note.nkmk.me/python-union-find/)。いつもお世話になっております。
コード
from collections import defaultdict class UnionFind: def __init__(self, n): self.n = n self.parents = [-1] * n def find(self, x): if self.parents[x] < 0: return x else: self.parents[x] = self.find(self.parents[x]) return self.parents[x] def union(self, x, y): x = self.find(x) y = self.find(y) if x == y: return if self.parents[x] > self.parents[y]: x, y = y, x self.parents[x] += self.parents[y] self.parents[y] = x def size(self, x): return -self.parents[self.find(x)] def same(self, x, y): return self.find(x) == self.find(y) def members(self, x): root = self.find(x) return [i for i in range(self.n) if self.find(i) == root] def roots(self): return [i for i, x in enumerate(self.parents) if x < 0] def group_count(self): return len(self.roots()) def all_group_members(self): group_members = defaultdict(list) for member in range(self.n): group_members[self.find(member)].append(member) return group_members def __str__(self): return "\n".join(f"{r}: {m}" for r, m in self.all_group_members().items()) def solve(H, W, S): uf = UnionFind((H + 2) * (W + 2)) for h in range(1, H + 1): for w in range(1, W + 1): if S[h][w] == "#": u = h * (W + 2) + w for dh in range(-1, 2): for dw in range(-1, 2): hh = h + dh ww = w + dw if S[hh][ww] == "#": v = hh * (W + 2) + ww uf.union(u, v) ans = 0 for r in uf.roots(): h = r // (W + 2) w = r % (W + 2) ans += int(S[h][w] == "#") return ans def main(): H, W = map(int, input().split()) S = [] S.append("." * (W + 2)) for _ in range(H): line = "." + input() + "." S.append(line) S.append("." * (W + 2)) ans = solve(H, W, S) print(ans) if __name__ == "__main__": main()
D問題: Printing Machine
問題の概要
商品は、今から
秒後に印字機に入り、その
秒後に印字機から出る。印字機は、中にある商品に対して一瞬で印字することができるが、印字の度に1秒間のチャージ時間を必要とする。印字する対象の商品と印字のタイミングを適切に選んだとき、最大で何個の商品に印字できるか。
問題の考察
印字機に入っている商品の中で最も出が早いものから印字する貪欲法でよさそうですが、が大きいため、印字機への入りと出を毎秒シミュレーションする方法だと計算量的に間に合いません。
時間でのシミュレーションではなく、商品でのシミュレーションによる貪欲法を考えます。まず、印字機に入る時刻で管理された商品用のヒープ(in_heap)と、印字機を出る時刻で管理された商品用のヒープ(out_heap)を持ちます。①in_heap先頭の商品と同じ入り時刻の商品全てをout_heapに入れ、現時刻を
に更新します。②out_heapの先頭の商品の出時刻が
以上であるときは印字してチャージし(
)、そうでないときは印字しない(できない)、というのをin_heap先頭の商品の入り時刻が
より大きいうちは繰り返します。①と②をin_heapが空になるまで繰り返しせば、
の計算量で解けました。
コードでは、入りと出の時刻が十分大きい商品を番兵としてin_heapに入れており、これによってin_heapが空になることはないために条件分岐がシンプルになります。
コード
from heapq import heappop, heappush def solve(N, T, D): in_heap = [] for t, d in zip(T, D): heappush(in_heap, (t, d)) heappush(in_heap, (10000000000000000000, 10000000000000000000)) out_heap = [] ans = 0 while len(in_heap) > 1: tau = in_heap[0][0] while in_heap[0][0] <= tau: t, d = heappop(in_heap) heappush(out_heap, t + d) while out_heap and tau < in_heap[0][0]: if tau <= out_heap[0]: heappop(out_heap) ans += 1 tau += 1 else: heappop(out_heap) return ans def main(): N = int(input()) T = [] D = [] for _ in range(N): t, d = map(int, input().split()) T.append(t) D.append(d) ans = solve(N, T, D) print(ans) if __name__ == "__main__": main()
