Pythonでヒューリスティック型競プロに入門してみました

AHC002 参加しました

結果

問題

詳細(公式リンク)

A - Walking on Tiles

概要

「ドミノ」のように2つの数字が書かれたタイルが敷き詰められており(1マスのタイルもいくつかあります)、一度踏んだタイルは二度と踏めないという条件で、なるべく大きい数字をたくさん踏んで進む経路を探索する問題です。
上の画像は実行結果を可視化したもので、太枠で囲まれた数字がタイル、オレンジの実線が移動経路、青タイルは一度踏んだのでもう踏めなくなったタイルです。
右上の赤丸からスタートし、右下の緑色の丸のところで行き止まりにぶつかっています。

雑に言えば、白く残ったタイルが少なければ少ないほど望ましいです。
私の結果では結構残ってしまっていますね…

入力の受け取り

import sys
sys.setrecursionlimit(10**7)

def input():
    return sys.stdin.readline().strip()

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

def main():
    sy, sx = get_nums_l()
    t = []
    for y in range(50):
        t.append(get_nums_l())
    p = []
    for y in range(50):
        p.append(get_nums_l())

main()

input と get_nums_l は私が競プロ問題を解く時に使っているテンプレで定義している関数で、inputは標準入力読み取りの高速化(するらしい)、get_nums_lは入力を1行読み取って整数リストに変換する関数です。

sy , sx はそれぞれスタート地点のy座標,x座標を表します。問題文中では si , sj とされていますがわかりにくい気がしたので改名しています。

t[][] はタイルを識別するための値を表します。 マス (x1, y1) と マス (x2, y2) があるとき、 t[y1][x1] == t[y2][x2] であれば、マス (x1, y1) と マス (x2, y2) は繋がったタイルです。

p[][] はマスに書かれている数字を表します。 マス (x, y) の数字は p[y][x] に格納されています。

最初の戦略 (バックトラック)

深さ優先探索を使ってとにかく進める方向に進んでいき、行き止まりにあたったら1歩戻って別の方向を探す バックトラック法 を使って探索してみます。

def main():
    
    # (入力受け取り処理は省略します)

    def solve(y, x, now_score, moved_tiles, move_history, last_move):
        """与えられた状態から最良の移動をした場合に得られるスコアと、そのときの移動経路を返します。"""

        if t[y][x] in moved_tiles:
            # 移動済みタイルにあたった場合はこの経路の結果を確定し、スコアと経路をreturnする
            return now_score, move_history

        # 現在のスコアと移動経路を更新する
        now_score += p[y][x]
        moved_tiles.add(t[y][x])
        move_history.append(last_move)

        ret = []

        # 動けそうな方向に1歩進む
        # 4方向の結果を比較して、最も良かった値をこの経路のスコアとする
        if y-1>0:
            ret.append(solve(y-1, x, now_score, set(moved_tiles), list(move_history), "U"))
        if y+1<50:
            ret.append(solve(y+1, x, now_score, set(moved_tiles), list(move_history), "D"))
        if x-1>0:
            ret.append(solve(y, x-1, now_score, set(moved_tiles), list(move_history), "L"))
        if x+1<50:
            ret.append(solve(y, x+1, now_score, set(moved_tiles), list(move_history), "R"))

        score, ans = max(ret)

        return score, ans

    # 初期状態から探索して最も良い移動経路を探す
    max_score, ans = solve(sy, sx, 0, set(), [], "")

    # ["", "U", "R", "D", "L"] のような1文字ずつの配列になっているので、文字列を結合して出力用の文字列 "URDL"形式に変換する
    print("".join(ans))


main()

solve 関数を再帰的に呼び出すことにより、深さ優先探索で全経路を探索し、最善の経路を探すことができます。
これだけで、必ず有限時間で最善経路を発見できます。

制限時間つき探索

実際に上のソースを動かしてみると、全く結果が返ってきません。
盤面は $50 * 50 = 2500$ マスの広さがあり、一度踏んだタイルは二度と踏めないことを考えても最大1250回の再帰呼び出しがされる可能性があるため、膨大な計算量になってしまいます。
(来た道を戻る経路はありえないためある地点からは最大3方向進めるので、計算量のオーダーは盤面のタイル数 $N$ に対して $O(3^N)$ でしょうか？厳密にはもう少し小さいかもしれません)

そこで、下のように時間で打ち切って 暫定の最適解 を出力するようにします。

まず、「制限時間による打ち切り」を表現する例外クラスを作ります。
わざわざ定義せず、 ValueError などの組み込み例外を使ってもいいのですが、なんとなく気持ち悪いのでちゃんと作っておきます。

class TLEError(Exception):
    def __init__(self):
        pass

処理の冒頭で現在時刻を取得しておき、都度経過時間を確認してギリギリのところで打ち切ります。

from time import time

# 暫定の最適解
z_max_score = 0
z_ans = None

def main():
    # 処理を始めた時刻を保存
    stime = time()

    # (入力受け取り処理は省略します)

    def solve(y, x, now_score, moved_tiles, move_history, last_move):
        """与えられた状態から最良の移動をした場合に得られるスコアと、そのときの移動経路を返します。"""
        global z_max_score, z_ans

        if t[y][x] in moved_tiles:
            # 移動済みタイルにあたった場合はこの経路の結果を確定し、スコアと経路をreturnする
            return now_score, move_history

        # 現在のスコアと移動経路を更新する
        now_score += p[y][x]
        moved_tiles.add(t[y][x])
        move_history.append(last_move)

        # 暫定ハイスコアを越えていた場合、この経路を暫定の最適解として保存する
        if now_score > z_max_score:
            z_max_score = now_score
            z_ans = list(move_history)

        # 時間切れなら例外を投げて打ち切りにする
        if time()-stime > 1.85:
            raise TLEError()

        ret = []

        # 動けそうな方向に1歩進む
        # (以下省略)

if time()-stime > 1.85: のところで経過時間を確認しており、制限時間2秒なので少し余裕を持たせて1.85秒のところで打ち切りにします。
最初は1.9秒で打ち切っていたのですが、時々トータルの処理時間が2秒をわずかに越えてしまい制限時間オーバーになってしまうようでした。

solve関数を呼び出す部分は以下のようにtry文でTLEErrorをキャッチできるようにします。

    try:
        max_score, ans, _ = solve(sy, sx, 0, set(), [], "")

        # 結果が返ってきた場合はこれを出力する
        print("".join(ans))
    except TLEError:
        # 途中で打ち切りになった場合は、その時点の暫定の最適解を出力する
        print("".join(z_ans))

これで、 時間ギリギリまでいろんな経路を探索して、暫定で最も良い経路を出力する ことができるようになりました。
スコアは約243万点、その瞬間では21位のスコアを出すことができました。

その後

ちょっとした高速化と、見込みのなさそうな領域は探索をせずに次を探す(枝刈り)などを実装してみて、結局最初の画像の通り343万点まで向上しました。
(進む方向をランダムで決定するなどもやってみたのですが逆にスコアが下がったのでやめました)
最もスコアの良かった時のソースをおまけとして貼り付けておきます。

ソース全体(クリックで展開)

from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
from time import time

def input():
    return sys.stdin.readline().strip()

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

class TLEError(Exception):
    def __init__(self):
        pass

z_max_score = 0
z_ans = None

back_his = defaultdict(lambda:defaultdict(lambda:defaultdict(int)))

def main():

    stime = time()

    sy, sx = get_nums_l()
    t = []
    for y in range(50):
        t.append(get_nums_l())
    p = []
    for y in range(50):
        p.append(get_nums_l())
    

    def back(ret):
        score, ans, back = max(ret)
        # 枝刈りカウントを1減らして返す
        return (score, ans, back-1)

    def solve(y, x, now_score, moved_tiles, move_history, last_move, depth):
        global z_max_score, z_ans

        if t[y][x] in moved_tiles:
            # 移動済みタイル
            # 同じマスで何度も行き止まっている場合は枝刈りする
            back_his[y][x][depth] += 1
            return now_score, move_history, back_his[y][x][depth]//6

        now_score += p[y][x]
        moved_tiles.add(t[y][x])
        move_history.append(last_move)
        depth+=1
        
        if now_score > z_max_score:
            z_max_score = now_score
            z_ans = list(move_history)

        if time()-stime > 1.85:
            raise TLEError()

        ret = []

        if y-1>0:
            ret.append(solve(y-1, x, now_score, moved_tiles, move_history, "U", depth))
            if(ret[-1][2] > 1):
                move_history.pop(-1)
                moved_tiles.remove(t[y][x])
                return back(ret)
        if y+1<50:
            ret.append(solve(y+1, x, now_score, moved_tiles, move_history, "D", depth))
            if(ret[-1][2] > 1):
                move_history.pop(-1)
                moved_tiles.remove(t[y][x])
                return back(ret)
        if x-1>0:
            ret.append(solve(y, x-1, now_score, moved_tiles, move_history, "L", depth))
            if(ret[-1][2] > 1):
                move_history.pop(-1)
                moved_tiles.remove(t[y][x])
                return back(ret)
        if x+1<50:
            ret.append(solve(y, x+1, now_score, moved_tiles, move_history, "R", depth))
            if(ret[-1][2] > 1):
                move_history.pop(-1)
                moved_tiles.remove(t[y][x])
                return back(ret)

        score, ans, _ = max(ret)
        ans = list(ans)

        move_history.pop(-1)
        moved_tiles.remove(t[y][x])

        return score, ans, 0

    try:
        max_score, ans, _ = solve(sy, sx, 0, set(), [], "", 0)
        # print(max_score)
        log(max_score)
        print("".join(ans))
    except TLEError:
        # print(z_max_score)
        log(z_max_score)
        print("".join(z_ans))

main()