AHC50参加記【Atcoder Heuristic Contest】

はじめに

AHC50にでてきました。貪欲のみで黄パフォとれたので書き残しておきます。

問題

問題概要

この問題は、$N \times N$の盤面で、ロボットをつぶさないように岩を置いていくゲームで、プレイヤーの目的は、獲得できる賞金の期待値を最大化することです。

ゲームのルール

1. 岩を置く順番の決定
   最初に、岩が置かれていない全てのマスについて、岩を置いていく順番のリスト P を決める
2. ロボットの初期配置
   岩のないマスの中からランダムに1つが選ばれ、そこにロボットが置かれる
3. ターンの進行
   以下の流れが繰り返される
   • ロボットの移動
     ロボットは「上下左右」の4方向からランダムに1つ選び、壁または既存の岩にぶつかるまで直進する
   • 岩の設置
     決めたリスト P の順番に従い、指定されたマスに新たに岩を置く
4. 得点と終了条件:
   • 岩を置いたマスにロボットがいなければ、賞金を1円獲得し、ゲーム続行となる
   • 岩を置いたマスにロボットがいた場合、ロボットはつぶされゲーム終了となる

目的

最終的に獲得できる賞金の期待値が最も高くなるような、岩を置く順番 P を求めること

解法の方針

下記を貪欲で書きました。

1. まばらな盤面を防ぐ
2. ロボットがいる確率の低いところに岩を置く

まばらな盤面を防ぐ

岩を置いていくと、経過するにつれてまばらな盤面がどうしても出来てしまいます。これを防げば期待値は上がるので、各マスのスコアを計算し、ループごとに再計算させました。
下記にまばら防止部分のパーツを置きます。

まばら防止.py

for r_cand, c_cand in P:
    L_h = 1
    c = c_cand - 1

    # 上下左右の可動範囲を計算
    while c >= 0 and grid[r_cand][c] == ".":
        L_h += 1
        c -= 1
    c = c_cand + 1
    while c < N and grid[r_cand][c] == ".":
        L_h += 1
        c += 1
    L_v = 1
    r = r_cand - 1
    while r >= 0 and grid[r][c_cand] == ".":
        L_v += 1
        r -= 1
    r = r_cand + 1
    while r < N and grid[r][c_cand] == ".":
        L_v += 1
        r += 1
    
    # 可動範囲からスコア算出
    score = L_h + L_v
    
    # 最小スコアの要素を探す
    if scoree < min_score:
        min_score = score
        best_square = (r_cand, c_cand)

ロボットがいる確率の低いところに岩を置く

空きマス$(r, c)$にロボットがいる確率$Prob(r, c)$ から 上下左右に移動するため、それぞれの方向の岩にぶつかるマス対して $Prob(r, c) / 4$ が加算されます。これを全空きマスに行い、最小確率のマスに岩を置いていく戦略です。
こちらも下記にパーツを置いておきます。

最小確率戦略.py

for r_start, c_start in P:
    if probs[r_start][c_start] > 0:
        prob_mass = probs[r_start][c_start] / 4.0
        r = r_start
        while r > 0 and grid[r - 1][c_start] == ".":
            r -= 1
        next_probs[r][c_start] += prob_mass
        r = r_start
        while r < N - 1 and grid[r + 1][c_start] == ".":
            r += 1
        next_probs[r][c_start] += prob_mass
        c = c_start
        while c > 0 and grid[r_start][c - 1] == ".":
            c -= 1
        next_probs[r_start][c] += prob_mass
        c = c_start
        while c < N - 1 and grid[r_start][c + 1] == ".":
            c += 1
        next_probs[r_start][c] += prob_mass

min_prob = float("inf")
for r, c in P:
    min_prob = min(min_prob, next_probs[r][c])

おわり

読んでいただきありがとうございました!