提出 #72942201

---

ソースコード 拡げる

import sys
import time
import random
import math
from collections import deque

# --- チューニング設定 ---
TIME_LIMIT = 1.95
SA_TIME_LIMIT = 1.45    # 高速化したので時間をたっぷりとる
SA_DEPTH = 8            # ビット演算なら深さ8まで余裕でいける
BFS_LIMIT = 3500

def solve():
    start_time = time.time()
    
    # --- 1. 入力 ---
    try:
        line1 = sys.stdin.readline().split()
        if not line1: return
        N, M, K, T = map(int, line1)
        
        adj = [[] for _ in range(N)]
        degrees = [0] * N
        for _ in range(M):
            u, v = map(int, sys.stdin.readline().split())
            adj[u].append(v)
            adj[v].append(u)
            degrees[u] += 1
            degrees[v] += 1
        
        for _ in range(N):
            sys.stdin.readline()
    except ValueError:
        return

    # --- 2. Safe Core (安全圏) ---
    is_safe = [True] * N
    curr_degrees = list(degrees)
    queue = deque([i for i in range(N) if curr_degrees[i] == 1])
    
    while queue:
        u = queue.popleft()
        is_safe[u] = False
        for v in adj[u]:
            if is_safe[v]:
                curr_degrees[v] -= 1
                if curr_degrees[v] == 1:
                    queue.append(v)
    
    if sum(is_safe) == 0:
        for i in range(N):
            if degrees[i] >= 2: is_safe[i] = True

    # --- 3. 高速化前処理: パスのビットマスク用リスト ---
    # shop_paths[k] = [ (length, [node_indices...]), ... ]
    shop_paths = [[] for _ in range(K)]
    
    for start_node in range(K):
        q = deque([(start_node, -1, [])])
        cnt = 0
        while q:
            u, p, path = q.popleft()
            if path:
                # パス自体を保存
                shop_paths[start_node].append((len(path), path))
            
            if len(path) >= SA_DEPTH:
                continue
            
            for v in adj[u]:
                if v == p: continue
                if v < K: continue
                if not is_safe[v]: continue
                
                # 枝刈り: あまりに多すぎるとSAが遅くなるので制限
                if cnt > 1200: break
                
                q.append((v, u, path + [v]))
                cnt += 1

    # --- 4. 爆速焼きなまし (Bitwise SA) ---
    current_colors = [0] * N 
    # 初期解: 半分くらいRにしておく
    for i in range(K, N):
        if random.random() < 0.3: current_colors[i] = 1
            
    best_colors = list(current_colors)
    
    # スコア計算: 文字列操作を排除し、ビット演算とタプルのみで行う
    # seen = set( (length, bitmask_value) )
    def calc_score_fast(colors):
        total_score = 0
        r_count = 0
        
        # Rの数ペナルティ（工事コスト削減のため）
        # しかしPythonのsumは遅いので、差分更新したいがここでは簡易的に
        # K以降のsumをとる
        # r_count = sum(colors[K:]) * 0.5 # 係数は調整
        
        for i in range(K):
            seen = set()
            local_score = 0
            for length, path in shop_paths[i]:
                # ビットマスク生成
                val = 0
                for idx, node in enumerate(path):
                    if colors[node]:
                        val |= (1 << idx)
                
                # (長さ, 値) がユニークなら加点
                key = (length, val)
                if key not in seen:
                    seen.add(key)
                    # 長さの2乗をスコアに (長い文字列を強力に推奨)
                    local_score += length * length 
            
            total_score += local_score
        
        # Rが多いと少し減点（1個あたり0.1点減点など、コスト意識）
        # total_score -= sum(colors) * 0.1
        return total_score

    current_score = calc_score_fast(current_colors)
    best_score = current_score
    
    T0 = 200.0
    T1 = 1.0
    temp = T0
    
    sa_iter = 0
    while True:
        sa_iter += 1
        if (sa_iter & 255) == 0:
            now = time.time()
            if now - start_time > SA_TIME_LIMIT:
                break
            progress = (now - start_time) / SA_TIME_LIMIT
            temp = T0 + (T1 - T0) * progress
        
        target = random.randint(K, N - 1)
        if not is_safe[target]: continue
            
        current_colors[target] ^= 1 
        new_score = calc_score_fast(current_colors)
        
        delta = new_score - current_score
        
        if delta >= 0:
            current_score = new_score
            if current_score > best_score:
                best_score = current_score
                best_colors = list(current_colors)
        else:
            try:
                prob = math.exp(delta / temp)
            except OverflowError:
                prob = 0
            if random.random() < prob:
                current_score = new_score
            else:
                current_colors[target] ^= 1 # Revert

    # --- 5. 実行パート (Real-Cost Greedy) ---
    real_tree_flavors = [0] * N
    delivered_strings = [set() for _ in range(K)]
    
    current_pos = 0
    prev_pos = -1
    current_ice = ""
    action_queue = deque()
    
    for t_idx in range(T):
        turns_left = T - t_idx
        
        # 計画作成
        if not action_queue:
            # (pos, prev, current_string, path_history, flip_cost)
            q = deque([(current_pos, prev_pos, current_ice, [], 0)])
            visited = { (current_pos, current_ice) }
            
            candidates = []
            bfs_cnt = 0
            
            while q:
                u, p, s, path, flips = q.popleft()
                bfs_cnt += 1
                if bfs_cnt > BFS_LIMIT: break
                
                # 距離 + 工事コスト が残りターンを超えたら無意味
                current_total_cost = len(path) + flips
                if current_total_cost > turns_left: continue
                if len(path) > 16: continue # 遠すぎるのは見ない
                
                # ショップ到達
                if u < K:
                    if s != "" and s not in delivered_strings[u]:
                        # 評価関数
                        # Value: 長さの2.5乗（長いのが正義）
                        # Cost: 移動距離 + (工事回数 * 1.5) 
                        # ※工事には1ターンかかるが、リスクもあるので少し重く見る
                        score = len(s) ** 2.5
                        cost = len(path) + (flips * 1.2) + 0.1
                        efficiency = score / cost
                        
                        candidates.append((path, score, efficiency))
                    continue
                
                # 移動先列挙
                next_nodes = []
                for v in adj[u]:
                    if v == p: continue
                    if is_safe[u] and not is_safe[v]: continue
                    next_nodes.append(v)
                
                for v in next_nodes:
                    new_flips = flips
                    if v >= K:
                        # 理想の色にする必要があるか？
                        # 現在の色を取得
                        actual_color = real_tree_flavors[v]
                        # 理想の色 (best_colors) を使う前提でパスを組む
                        target_color = best_colors[v]
                        
                        # もし「今の現実」と「理想」が違うなら、工事コスト+1
                        # そして、その場所で得られる色は「理想の色」になる
                        if actual_color != target_color:
                            new_flips += 1
                        
                        flavor = 'R' if target_color == 1 else 'W'
                        next_s = s + flavor
                    else:
                        next_s = s
                    
                    if len(next_s) <= 8: # 長さ8まで許容
                        if (v, next_s) not in visited:
                            visited.add((v, next_s))
                            q.append((v, u, next_s, path + [v], new_flips))
            
            # ベストパス選択
            if candidates:
                # 常に「効率（コスパ）」最優先
                candidates.sort(key=lambda x: -x[2]) 
                best_path = candidates[0][0]

                for node in best_path:
                    action_queue.append(node)
                    # 味変予約: 現実と理想が違うなら変える
                    if node >= K and real_tree_flavors[node] != best_colors[node]:
                        action_queue.append(-1)
            else:
                # ランダム移動 (Safe優先)
                cands = [v for v in adj[current_pos] if v != prev_pos]
                safe_cands = [v for v in cands if is_safe[v]]
                if is_safe[current_pos] and safe_cands:
                    action_queue.append(random.choice(safe_cands))
                elif cands:
                    action_queue.append(random.choice(cands))
                else:
                    pass

        # --- 実行 (Safety Guard) ---
        final_action = -999
        while action_queue:
            cand = action_queue.popleft()
            if cand == -1:
                # 味変: 今の場所で、色が違うなら実行
                if current_pos < K: continue
                if real_tree_flavors[current_pos] == best_colors[current_pos]: continue 
                final_action = -1; break
            else:
                if cand == prev_pos or cand not in adj[current_pos]: continue
                final_action = cand; break
        
        if final_action == -999:
            cands = [v for v in adj[current_pos] if v != prev_pos]
            safe_cands = [v for v in cands if is_safe[v]]
            if is_safe[current_pos] and safe_cands: final_action = safe_cands[0]
            elif cands: final_action = cands[0]
            else: break 
            
        print(final_action)
        sys.stdout.flush()
        
        if final_action == -1:
            # 味を反転
            real_tree_flavors[current_pos] ^= 1
        else:
            prev_pos = current_pos
            current_pos = final_action
            if current_pos >= K:
                current_ice += ('R' if real_tree_flavors[current_pos] else 'W')
            else:
                if current_ice: delivered_strings[current_pos].add(current_ice)
                current_ice = ""

if __name__ == "__main__":
    solve()

提出情報

ジャッジ結果