Submission #72942653

---

Source Code Expand

'''
方針: ランダム
  CHANGEが選ばれる確率: 低(0.01)
  店に行きやすくする // 行先が木の場合、50%で再度行先を決め直す
'''
import random
import time
from collections import defaultdict
from enum import Enum

class IceCream:
    '''
    　edges: edges[i]=頂点iから出ている辺とつながってている頂点
    　shops_set: 各頂点が店かの判定用
    　shops: shops[i][ice]=店iのアイスiceをもっているか（各店のアイスの種類を管理）
      trees: trees[i]= "W"or"R"
      Memo:
       店i=頂点i(i=0,1,...,num_shops-1)
    '''
    def __init__(self, num_points,num_edges,num_shops,edges,points=None):
        self.num_points = num_points 
        self.num_edges = num_edges
        self.num_shops = num_shops
        self.num_tree = num_points - num_shops

        self.edges = edges                          
        self.shops_set = set([i for i in range(num_shops)])
        self.shops = [defaultdict(lambda:False) for _ in range(num_shops)]   
        self.trees = defaultdict(lambda:"W")
        self.points = points
    
    def clear_state(self):
        self.trees = defaultdict(lambda:"W")
        self.shops = [defaultdict(lambda:False) for _ in range(self.num_shops)]  


class ActionType(Enum):
    MOVE = 0
    CHANGE = 1

# MOVEが選ばれる確率p
def random_choice(p: float) -> ActionType:
    return ActionType.MOVE if random.random() < p else ActionType.CHANGE


class Optimizer:
    def __init__(self, seed, num_turns=None):
        self.rand = random.Random(seed)
        self.num_turns = num_turns
    
    def random_act(self, ice):
        actions = []
        prev_point = -1    # 前回の位置
        current_point = 0  # 現在の位置
        current_state = "" # 現在のアイス
        action_type = list(ActionType) 
        score = 0
        move_prob = 0.99 # MOVEが選ばれる確率 
        p = 0.5 
        for t in range(self.num_turns):
            action = random_choice(p=move_prob)
            # 現在位置が店 or 現在位置の木がすでにストロベリーの場合、強制的に「MOVE」にする
            cannot_change = (current_point in ice.shops_set)or(ice.trees[current_point] == "R")
            if(cannot_change):
                action = ActionType.MOVE
            # 店または木に訪れる
            if(action == ActionType.MOVE):
                # 1つ前に訪れた場所には戻れない
                while(1):
                    # 行先を乱数で決定
                    next_point = self.rand.choice(ice.edges[current_point])
                    if(next_point != prev_point):
                      break
                    else:
                      # 行先が店ではない場合、一定確率で再度実行
                      if(not (next_point in ice.shops_set)):
                        if self.rand.random() >= p:
                          continue
                        
                # 店 
                if(next_point in ice.shops_set):
                    # 新しい種類の場合
                    if(not ice.shops[next_point][current_state]):
                        ice.shops[next_point][current_state] = True
                        current_state = ""
                        score += 1
                # 木
                else:
                    current_state += ice.trees[next_point]
                # 更新
                prev_point = current_point
                current_point = next_point
                
            # 木の変更
            elif(action == ActionType.CHANGE):
                ice.trees[current_point] = "R"
                
            # 行動履歴
            tmp = next_point if(action == ActionType.MOVE)  else -1
            actions.append(tmp)
        return actions, score


# 入力
def get_input(seed=22):
    num_points,num_edges,num_shops,num_turns = list(map(int, input().split()))
    # 辺
    edges = defaultdict(list) 
    for i in range(num_edges):
        a,b = list(map(int, input().split()))
        edges[a].append(b)
        edges[b].append(a)
    '''
    # 座標: 不要
    points = defaultdict(lambda:tuple)
    for i in range(N):
        x,y = list(map(int, input().split()))
        points[i] = (x,y)
    '''
    ice_cream = IceCream(num_points=num_points,num_edges=num_edges,num_shops=num_shops,edges=edges)
    opt = Optimizer(num_turns=num_turns,seed=seed)
    return ice_cream, opt

def main():
    start_t = time.time()
    ice_cream, opt = get_input()
    elapsed_time = time.time() - start_t
    
    num_opt = 1      # 探索回数 
    time_per_opt = 0 # 1回あたりの探索時間
    limit_t = 1.75   # 制限時間[sec]
    best_actions,best_score = [],0
    scores = []
    # 制限時間まで探索
    while((elapsed_time + time_per_opt) < limit_t):
        actions, score = opt.random_act(ice=ice_cream)
        ice_cream.clear_state() # 木、店の状態の初期化
        scores.append(score)
        if(best_score < score):
            best_actions = actions
            best_score = score
        # 更新
        if(num_opt == 1):
            time_per_opt = elapsed_time
        num_opt += 1
        elapsed_time = elapsed_time = time.time() - start_t
        
    # 出力
    ave_score = sum(scores) / num_opt
    #print(f"best_score: {best_score}")
    #print(f"ave_score: {ave_score}")
    #print(f"num_opt:{num_opt}")
    #scores.sort()
    #print(scores[:10], scores[-10:])
    for i in range(len(best_actions)):
        #print(f"turn: {i+1}")
        print(best_actions[i])
     
if __name__ == "__main__":
    main()

Submission Info

Judge Result