結果

問題 No.1284 Flip Game
コンテスト
ユーザー lam6er
提出日時 2025-03-26 15:51:18
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,532 bytes
コンパイル時間 256 ms
コンパイル使用メモリ 82,732 KB
実行使用メモリ 172,844 KB
最終ジャッジ日時 2025-03-26 15:52:32
合計ジャッジ時間 16,322 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26 TLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def main():
    N = int(input())
    c = []
    for _ in range(N):
        row = list(map(int, input().split()))
        c.append(row)
    
    full_mask = (1 << N) - 1
    
    heap = []
    # Initialize with all possible starting positions (each first choice of A)
    for k in range(N):
        mw = 1 << k
        mfb = 0
        p = k
        flag = 0  # Initially, B has not acted after the first move
        heapq.heappush(heap, (0, mw, mfb, p, flag))
    
    # Using a dictionary to keep track of minimum costs for each state
    dp = {}
    INF = float('inf')
    
    # Initialize the starting states
    for k in range(N):
        mw = 1 << k
        mfb = 0
        p = k
        flag = 0
        key = (mw, mfb, p, flag)
        dp[key] = 0
    
    while heap:
        cost, mw, mfb, p, flag = heapq.heappop(heap)
        
        # Check if this state is the answer
        if mw == full_mask and flag == 1:
            print(cost)
            return
        
        # If current cost is higher than the known minimum, skip
        current_key = (mw, mfb, p, flag)
        if dp.get(current_key, INF) < cost:
            continue
        
        # Generate all possible next moves
        for q in range(N):
            # Check if q is currently red (bit not set in mw)
            if not (mw & (1 << q)):
                new_cost = cost + c[p][q]
                new_mw = mw | (1 << q)  # A flips q to white
                
                # B's action: flip p (previous p) if not in mfb
                p_old = p  # B will act on the previous p
                if (mfb & (1 << p_old)) == 0:
                    # B flips p_old back to red
                    new_mw_after_b = new_mw ^ (1 << p_old)
                    new_mfb = mfb | (1 << p_old)
                    new_flag = 0  # B took action
                else:
                    # B does nothing
                    new_mw_after_b = new_mw
                    new_mfb = mfb
                    new_flag = 1  # B did not act
                
                new_p = q
                new_state = (new_mw_after_b, new_mfb, new_p, new_flag)
                
                # Check if this new state has a lower cost
                if new_cost < dp.get(new_state, INF):
                    dp[new_state] = new_cost
                    heapq.heappush(heap, (new_cost, new_mw_after_b, new_mfb, new_p, new_flag))
    
    # If no solution found (shouldn't happen as per problem statement)
    print(-1)

if __name__ == "__main__":
    main()
0