結果

問題 No.1924 3 color painting on a line
ユーザー qwewe
提出日時 2025-05-14 13:10:53
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,487 bytes
コンパイル時間 191 ms
コンパイル使用メモリ 82,316 KB
実行使用メモリ 70,772 KB
最終ジャッジ日時 2025-05-14 13:12:13
合計ジャッジ時間 3,463 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2 WA * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

# Use fast IO
input = sys.stdin.readline

def solve():
    # Read input N and string S
    n = int(input())
    s = input().strip()

    # The problem constraints state N >= 1, so we don't need to handle N=0 explicitly.
    # If N=0 were possible, the answer would be 0 operations.

    # Initialize counts for blocks of each color
    nr = 0 # Number of Red blocks
    ng = 0 # Number of Green blocks
    nb = 0 # Number of Blue blocks

    # We need to count the number of maximal contiguous blocks of each color.
    # We can iterate through the string and increment the count whenever a new block starts.
    if n > 0:
        # Handle the first character to initialize the count for the first block
        first_char = s[0]
        if first_char == 'R':
            nr = 1
        elif first_char == 'G':
            ng = 1
        else: # 'B'
            nb = 1
        
        # Iterate from the second character (index 1) up to N-1
        for i in range(1, n):
            # A new block starts if the current character is different from the previous one
            if s[i] != s[i-1]: 
                 # Identify the color of the new block and increment its count
                 current_char = s[i]
                 if current_char == 'R':
                     nr += 1
                 elif current_char == 'G':
                     ng += 1
                 else: # 'B'
                     nb += 1

    # Now we apply the strategy: Choose a base color, paint everything with it (1 op),
    # then paint over the blocks that have a different target color.
    # The total operations for a base color C is 1 + (sum of block counts for colors != C).

    # Calculate the cost if Red is chosen as the base color.
    # Need 1 op for base coat + ops for Green blocks + ops for Blue blocks.
    costR = 1 + ng + nb
    
    # Calculate the cost if Green is chosen as the base color.
    # Need 1 op for base coat + ops for Red blocks + ops for Blue blocks.
    costG = 1 + nr + nb
    
    # Calculate the cost if Blue is chosen as the base color.
    # Need 1 op for base coat + ops for Red blocks + ops for Green blocks.
    costB = 1 + nr + ng
    
    # The minimum number of operations required is the minimum cost among the three possible base color strategies.
    # The `min` function handles cases where one or two colors might not be present (their counts would be 0).
    print(min(costR, costG, costB))

# Call the solve function to run the logic
solve()
0