結果

問題 No.1951 消えたAGCT(2)
ユーザー lam6er
提出日時 2025-03-20 21:11:05
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 342 ms / 3,000 ms
コード長 2,793 bytes
コンパイル時間 151 ms
コンパイル使用メモリ 82,492 KB
実行使用メモリ 85,492 KB
最終ジャッジ日時 2025-03-20 21:11:22
合計ジャッジ時間 5,265 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    n = int(input[0])
    s = input[1]
    
    # Convert characters to numerical values (A=0, B=1, ..., Z=25)
    original_chars = [ord(c) - ord('A') for c in s]
    
    # Initialize count array for each character (0-25)
    count = [0] * 26
    for c in original_chars:
        count[c] += 1
    
    # BIT (Fenwick Tree) 1-based indexing
    class FenwickTree:
        def __init__(self, size):
            self.n = size
            self.tree = [0] * (self.n + 2)  # 1-based
            
        def update_point(self, idx, delta):
            while idx <= self.n:
                self.tree[idx] += delta
                idx += idx & -idx
                
        def query_prefix(self, idx):
            res = 0
            while idx > 0:
                res += self.tree[idx]
                idx -= idx & -idx
            return res
        
        def find_kth(self, k):
            # Find the smallest index where prefix sum >= k
            sum_ = 0
            pos = 0
            max_bit = 1
            while (max_bit << 1) <= self.n:
                max_bit <<= 1
            mask = max_bit
            while mask > 0:
                next_pos = pos + mask
                if next_pos > self.n:
                    mask >>= 1
                    continue
                if sum_ + self.tree[next_pos] < k:
                    sum_ += self.tree[next_pos]
                    pos = next_pos
                mask >>= 1
            return pos + 1  # 1-based
    
    ft = FenwickTree(n)
    for i in range(1, n+1):
        ft.update_point(i, 1)
    
    total_shift = 0
    ans = 0
    
    while True:
        current_shift = total_shift % 26
        # Calculate the target original characters that would now contribute to AGCT
        targetA = (0 - current_shift) % 26
        targetG = (6 - current_shift) % 26
        targetC = (2 - current_shift) % 26
        targetT = (19 - current_shift) % 26
        
        # Sum the counts of these targets
        c1 = count[targetA] + count[targetG] + count[targetC] + count[targetT]
        
        if c1 == 0:
            break
        
        ans += 1
        
        # Find the k-th element (k = c1)
        k = c1
        pos = ft.find_kth(k)
        
        # Get the original character at pos (1-based)
        original_char = original_chars[pos - 1]  # since original_chars is 0-based
        
        # Update count
        count[original_char] -= 1
        
        # Update the Fenwick Tree (mark as removed)
        ft.update_point(pos, -1)
        
        # c2 is the new count after deletion
        c2 = count[original_char]
        
        # Update total_shift
        total_shift += c2
    
    print(ans)
    
if __name__ == '__main__':
    main()
0