結果
問題 |
No.1943 消えたAGCT(1)
|
ユーザー |
![]() |
提出日時 | 2025-03-20 20:29:19 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,078 ms / 2,000 ms |
コード長 | 1,910 bytes |
コンパイル時間 | 168 ms |
コンパイル使用メモリ | 82,396 KB |
実行使用メモリ | 89,932 KB |
最終ジャッジ日時 | 2025-03-20 20:30:16 |
合計ジャッジ時間 | 13,315 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 27 |
ソースコード
class FenwickTree: def __init__(self, size): self.n = size self.tree = [0] * (self.n + 2) # Using n+2 to avoid issues with 1-based indexing def update_point(self, idx, delta): # Converts to 1-based index internally idx += 1 # since input is 0-based while idx <= self.n: self.tree[idx] += delta idx += idx & -idx def query_prefix(self, idx): # Sum from 0-based index 0 to idx (inclusive) res = 0 idx += 1 # convert to 1-based index while idx > 0: res += self.tree[idx] idx -= idx & -idx return res def range_query(self, l, r): if l > r: return 0 return self.query_prefix(r) - self.query_prefix(l - 1) def main(): import sys input = sys.stdin.read().split() n = int(input[0]) s = input[1].strip() agct = [1 if c in {'A', 'G', 'C', 'T'} else 0 for c in s] valid_ft = FenwickTree(n) valid_agct_ft = FenwickTree(n) for i in range(n): valid_ft.update_point(i, 1) if agct[i]: valid_agct_ft.update_point(i, 1) count = 0 def find_kth(k): low = 0 high = n - 1 res = -1 while low <= high: mid = (low + high) // 2 s = valid_ft.query_prefix(mid) if s >= k: res = mid high = mid - 1 else: low = mid + 1 return res while True: sum_agct = valid_agct_ft.query_prefix(n - 1) if sum_agct == 0: break k = sum_agct pos = find_kth(k) if pos == -1: break valid_ft.update_point(pos, -1) if agct[pos]: valid_agct_ft.update_point(pos, -1) count += 1 print(count) if __name__ == "__main__": main()