結果

問題 No.910 素数部分列
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:43:23
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,533 bytes
コンパイル時間 208 ms
コンパイル使用メモリ 82,728 KB
実行使用メモリ 89,916 KB
最終ジャッジ日時 2025-03-20 20:44:11
合計ジャッジ時間 5,247 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21 WA * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    n = int(sys.stdin.readline())
    s = sys.stdin.readline().strip()
    
    # Step 1: Count 3,5,7
    count_3 = 0
    count_5 = 0
    count_7 = 0
    ones = []
    nines = []
    for idx, c in enumerate(s):
        if c == '3':
            count_3 +=1
        elif c == '5':
            count_5 +=1
        elif c == '7':
            count_7 +=1
        else:
            if c == '1':
                ones.append(idx)
            else:
                assert c == '9'
                nines.append(idx)
    
    total = count_3 + count_5 + count_7
    
    # Now, process remaining characters (1 and 9)
    # Compute max possible pairs of 19 and 11 via two schemes
    
    # Scheme A: prioritize 19 then 11
    max_19_a = 0
    j = 0
    # Process ones and nines in order of their indices
    # Iterate through all 1's and find earliest possible 9
    for i_idx in ones:
        # Find the first nine in nines >= i_idx, starting from j
        # Using binary search
        pos = bisect.bisect_left(nines, i_idx, j)
        if pos < len(nines):
            max_19_a +=1
            j = pos +1
    
    scheme_a = max_19_a + ( (len(ones) - max_19_a) //2 )
    
    # Scheme B: prioritize 11 then 19
    max_11_b = len(ones) // 2
    remaining_1 = len(ones) %2
    max_19_b = min(remaining_1, len(nines))
    scheme_b = max_11_b + max_19_b
    
    remaining_total = max(scheme_a, scheme_b)
    
    total += remaining_total
    
    print(total)
    
if __name__ == "__main__":
    main()
0