結果
問題 | No.1943 消えたAGCT(1) |
ユーザー |
![]() |
提出日時 | 2022-05-20 22:00:29 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,254 ms / 2,000 ms |
コード長 | 5,156 bytes |
コンパイル時間 | 175 ms |
コンパイル使用メモリ | 82,132 KB |
実行使用メモリ | 150,612 KB |
最終ジャッジ日時 | 2024-09-20 08:08:13 |
合計ジャッジ時間 | 16,709 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 27 |
ソースコード
class BalancingTree: def __init__(self, n): self.N = n self.root = self.node(1<<n, 1<<n) def add(self, v):# v を追加(その時点で v はない前提) v += 1 nd = self.root while True: if v == nd.value: # v がすでに存在する場合に何か処理が必要ならここに書く return 0 else: mi, ma = min(v, nd.value), max(v, nd.value) if mi < nd.pivot: nd.value = ma if nd.left: nd = nd.left v = mi else: p = nd.pivot nd.left = self.node(mi, p - (p&-p)//2) break else: nd.value = mi if nd.right: nd = nd.right v = ma else: p = nd.pivot nd.right = self.node(ma, p + (p&-p)//2) break def leftmost(self, nd): if nd.left: return self.leftmost(nd.left) return nd def rightmost(self, nd): if nd.right: return self.rightmost(nd.right) return nd def find_l(self, v): # vより真に小さいやつの中での最大値(なければ-1) v += 1 nd = self.root prev = 0 if nd.value < v: prev = nd.value while True: if v <= nd.value: if nd.left: nd = nd.left else: return prev - 1 else: prev = nd.value if nd.right: nd = nd.right else: return prev - 1 def find_r(self, v): # vより真に大きいやつの中での最小値(なければRoot) v += 1 nd = self.root prev = 0 if nd.value > v: prev = nd.value while True: if v < nd.value: prev = nd.value if nd.left: nd = nd.left else: return prev - 1 else: if nd.right: nd = nd.right else: return prev - 1 @property def max(self): return self.find_l((1<<self.N)-1) @property def min(self): return self.find_r(-1) def delete(self, v, nd = None, prev = None): # 値がvのノードがあれば削除(なければ何もしない) v += 1 if not nd: nd = self.root if not prev: prev = nd while v != nd.value: prev = nd if v <= nd.value: if nd.left: nd = nd.left else: ##### return else: if nd.right: nd = nd.right else: ##### return if (not nd.left) and (not nd.right): if not prev.left: prev.right = None elif not prev.right: prev.left = None else: if nd.pivot == prev.left.pivot: prev.left = None else: prev.right = None elif nd.right: # print("type A", v) nd.value = self.leftmost(nd.right).value self.delete(nd.value - 1, nd.right, nd) else: # print("type B", v) nd.value = self.rightmost(nd.left).value self.delete(nd.value - 1, nd.left, nd) def __contains__(self, v: int) -> bool: return self.find_r(v - 1) == v class node: def __init__(self, v, p): self.value = v self.pivot = p self.left = None self.right = None def debug(self): def debug_info(nd_): return (nd_.value - 1, nd_.pivot - 1, nd_.left.value - 1 if nd_.left else -1, nd_.right.value - 1 if nd_.right else -1) def debug_node(nd): re = [] if nd.left: re += debug_node(nd.left) if nd.value: re.append(debug_info(nd)) if nd.right: re += debug_node(nd.right) return re print("Debug - root =", self.root.value - 1, debug_node(self.root)[:50]) def debug_list(self): def debug_node(nd): re = [] if nd.left: re += debug_node(nd.left) if nd.value: re.append(nd.value - 1) if nd.right: re += debug_node(nd.right) return re return debug_node(self.root)[:-1] n = int(input()) S = list(input()) board = ['A','T','C','G'] BT = BalancingTree(32) for i in range(1,n+1): BT.add(i) cnt = 0 for s in S: if s in board: cnt += 1 ans = 0 while cnt: index = BT.find_r(cnt-1) BT.delete(index) if S[index-1] in board: cnt -=1 ans += 1 print(ans)