結果

問題 No.608 God's Maze
コンテスト
ユーザー qwewe
提出日時 2025-05-14 13:27:13
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,938 bytes
コンパイル時間 218 ms
コンパイル使用メモリ 82,328 KB
実行使用メモリ 84,332 KB
最終ジャッジ日時 2025-05-14 13:27:45
合計ジャッジ時間 5,089 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6 WA * 59
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def solve():
    N_str = sys.stdin.readline()
    S_str = sys.stdin.readline().strip()

    N = int(N_str)
    S_target = S_str

    start_pos_1_indexed = N
    start_pos_0_indexed = start_pos_1_indexed - 1
    num_tiles = len(S_target)

    target_state = []
    for char_s in S_target:
        target_state.append(1 if char_s == '#' else 0)

    first_sharp = -1
    last_sharp = -1
    for i in range(num_tiles):
        if target_state[i] == 1:
            if first_sharp == -1:
                first_sharp = i
            last_sharp = i
    
    if first_sharp == -1: # Should not happen based on problem statement (at least one '#')
        print(0)
        return

    min_moves = float('inf')

    # Max number of full sweeps of the [L_s, R_s] segment.
    # A "traversal" is one pass Ls->Rs or Rs->Ls.
    # Max_traversals can be small. Let's try up to 4.
    # k=0 means no full traversals of [Ls,Rs], just P->Ls or P->Rs.
    for num_main_traversals in range(5): # 0, 1, 2, 3, 4 traversals of [Ls,Rs]
        # Option 1: Initial move towards first_sharp (Ls)
        # Path: P -> Ls -> (Ls <-> Rs sweeps)
        if True: # Always possible to attempt this strategy
            landings = [0] * num_tiles
            current_pos = start_pos_0_indexed
            current_moves = 0

            # Travel P -> Ls
            temp_p = current_pos
            while temp_p != first_sharp:
                if temp_p < first_sharp:
                    temp_p += 1
                else:
                    temp_p -= 1
                landings[temp_p] += 1
                current_moves += 1
            current_pos = first_sharp
            
            # Perform main traversals
            temp_current_pos_sweeps = first_sharp
            for i in range(num_main_traversals):
                # Odd traversals (1st, 3rd...): Ls -> Rs (or current -> other_end)
                # Even traversals (2nd, 4th...): Rs -> Ls (or current -> other_end)
                target_node_sweep = last_sharp if (temp_current_pos_sweeps == first_sharp) else first_sharp
                
                # If Ls == Rs, a traversal means 0 moves and no change in pos.
                if temp_current_pos_sweeps == target_node_sweep and first_sharp == last_sharp: # handles Ls=Rs case
                    pass # 0 moves for this traversal
                else:
                    path_start_sweep = temp_current_pos_sweeps
                    while path_start_sweep != target_node_sweep:
                        if path_start_sweep < target_node_sweep:
                            path_start_sweep +=1
                        else:
                            path_start_sweep -=1
                        landings[path_start_sweep] +=1
                        current_moves +=1
                temp_current_pos_sweeps = target_node_sweep
            
            # Check configuration
            match = True
            for i in range(num_tiles):
                if (landings[i] % 2) != target_state[i]:
                    match = False
                    break
            if match:
                min_moves = min(min_moves, current_moves)

        # Option 2: Initial move towards last_sharp (Rs)
        # Path: P -> Rs -> (Rs <-> Ls sweeps)
        if True: # Always possible
            landings = [0] * num_tiles
            current_pos = start_pos_0_indexed
            current_moves = 0

            # Travel P -> Rs
            temp_p = current_pos
            while temp_p != last_sharp:
                if temp_p < last_sharp:
                    temp_p += 1
                else:
                    temp_p -= 1
                landings[temp_p] += 1
                current_moves += 1
            current_pos = last_sharp

            # Perform main traversals
            temp_current_pos_sweeps = last_sharp
            for i in range(num_main_traversals):
                target_node_sweep = first_sharp if (temp_current_pos_sweeps == last_sharp) else last_sharp
                
                if temp_current_pos_sweeps == target_node_sweep and first_sharp == last_sharp:
                    pass
                else:
                    path_start_sweep = temp_current_pos_sweeps
                    while path_start_sweep != target_node_sweep:
                        if path_start_sweep < target_node_sweep:
                            path_start_sweep +=1
                        else:
                            path_start_sweep -=1
                        landings[path_start_sweep] +=1
                        current_moves +=1
                temp_current_pos_sweeps = target_node_sweep
            
            match = True
            for i in range(num_tiles):
                if (landings[i] % 2) != target_state[i]:
                    match = False
                    break
            if match:
                min_moves = min(min_moves, current_moves)
                
    print(min_moves)

solve()
0