読者です 読者をやめる 読者になる 読者になる

びったんびったん

ユーザビリティ・プログラミングについて。

MM89 考えたこと

マラソン参加3回目、がっつり参加したのは初めてだけれど楽しかったです。
暫定 72.34点 15位 Python

問題文 https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16494&pm=10967


全部Sにしたら100%になるよねーと思って上からSE以外をSにする。
38点


初期解(ランダム解)でなぜ迷路がほとんどできないのか考えてみる。

境界からスタートしてランダムに動いてもその場からあまり動かない。迷路の中心に向かう力がない。大きな迷路ができにくい。

ビジュアライザを無効なパスを表示するように変えてみる。
Uに突っ込んでる。Uを変えればよい。
くるっと回転して自分のパスに突っ込んでる。回転しなければよい。直進すればよい?やっぱりSが強い?

直進すれば迷路の中心に向かって迷路が大きくなり、回転して死ぬこともなくなる?


紙にいろいろ書いて思いつく。

f:id:hakomof:20151027204511p:plain

LとRが交互に並ぶようなライン(間にSやEはあってもよい)はどこから進入しても下から入れば上へ、上から入れば下へ抜ける。蛇行しながら直進する。

このラインを下端から上端まで積めば下端から上端、上端から下端へ抜ける迷路がたくさんできる。

このLとRが交互になるような修正をX座標が小さい順にF個とる。
64点

f:id:hakomof:20151027204509p:plain


ここでかなり迷走したので数多のソースが生まれそして死んでいった。

複数の迷路が密に重なっているのがよくないのではと思った。
複数の迷路で修正を共有しているのはメリットだけれど、マスを共有しているのはデメリットなのでトータル損してそう。もっと高効率な迷路をばらけさせたい。

LとRが交互になるような修正を全体にしたうえで有効な迷路を列挙する。
厳密に列挙すると指数時間になってしまうので、上左右の移動だけ、下左右の移動だけでできる迷路を列挙する。列挙漏れはEがからむときだけなので見なかったことにする。この制限でメモ化ができるようになってるはずなんだけど今自分の実装見るとしてない。あれ?

で、列挙した迷路をFを超えない範囲で近似スコアが最大になるように選択する組み合わせ問題になった。

最初DPしようとしたけどマスが共有されているのでできなんだ。

迷路ごとのマス数/修正数が大きい順にFを超えない範囲で選んでいく(貪欲)。
71点

f:id:hakomof:20151027204505p:plain


選択した迷路をひとつのぞいて別の迷路を選択して近似スコアが上がれば採用(山登り)。
72点

焼きなまそうと思ったけどよくわからず。

おわり


その他

方針さえあってれば Python でも探索時間減るだけやし上位狙わなければへーきへーきと思ったけど全然きつい。終わる前提の処理が終わらない終わらない。配列使いまわしたり、boolの2次元配列を整数の1次元配列に圧縮したり、なくなく迷路集合カットするなどした。

LとRを交互にするというアイデアに固執しすぎた感。マラソン終わるまで現解法の発展が上位の解法だと信じて疑わなかった。反省。

EとEを優先的につなぐように修正してみたけど微増だったのでやめた。テストケースごとのスコアは大きく上下するのがたまにある感じでWHFに特徴がみられなかった。今思うとEの割合とかもっとよく見ればよかった。平均じゃなくてFが多いとか少ないとか個々のテストケース見るの大事。

結局乱数使わなかったんだけどこれでいいのか。


Python 240 行

from copy import deepcopy
from itertools import compress, count, product, starmap
from time import time

class MazeFixing:
    def improve(self, maze, F):
        reverse = len(maze[0]) < len(maze)

        if reverse:
            maze = transpose(maze)
        else:
            maze = list(map(list, maze))

        fixes = createFixes(maze)
        paths = createPaths(maze, F, fixes)
        pair = climb(maze, F, paths, *greed(maze, F, paths))

        pair.fixed.i = -1

        fixes = [(y, x, fixes[y][x])
            for y in range(len(maze))
                for x in range(len(maze[0]))
                    if maze[y][x] is not '.' and pair.fixed.get()]

        if reverse:
            fixes = ((y, x, dest) for x, y, dest in fixes)
        return list(starmap('{} {} {}'.format, fixes))

def transpose(maze):
    return list(map(list, zip(*maze)))

def createFixes(maze):
    fixes = [[''] * len(maze[0]) for _ in range(len(maze))]
    ux = -1

    for y, line in enumerate(maze):
        for x, cell in enumerate(line):
            if cell in '.LRE':
                if ux >= 0:
                    if left is cell is 'L':
                        line[ux] = 'R'
                        fixes[y][ux] = 'R'
                    elif left is cell is 'R':
                        line[ux] = 'L'
                        fixes[y][ux] = 'L'
                    else:
                        line[ux] = 'S'
                        fixes[y][ux] = 'S'

                    ux = -1
                left = cell

            elif cell is 'U':
                if ux >= 0:
                    line[ux] = 'S'
                    fixes[y][ux] = 'S'
                ux = x

    xs = []

    for y, line in enumerate(maze):
        for x, cell in enumerate(line):
            if cell in '.E' or cell in 'LR' and xs and cell is not line[xs[0]]:
                for i in xs[1:-1:2]:
                    line[i] = 'R' if line[i] is 'L' else 'L'
                    fixes[y][i] = line[i]

                if xs and not len(xs) % 2:
                    line[xs[-1]] = 'S'
                    fixes[y][xs[-1]] = 'S'
                xs = []

            if cell in 'LR':
                xs.append(x)
    return fixes

def createPaths(maze, F, fixes):
    width = len(maze[0])
    height = len(maze)

    paths = []
    visited = [[False] * width for _ in range(height)]
    fixed = deepcopy(visited)

    for y, x, d in product(range(height), range(width), (1, 3)):
        if maze[y][x] is not '.' and maze[y + dy[d]][x + dx[d]] is '.':
            search(maze, fixes, visited, fixed, x, y, (d + 2) % 4, d)

            path = BoolsPair((width - 2) * (height - 2))

            for i, j in product(range(height), range(width)):
                if maze[i][j] is not '.':
                    path.append(visited[i][j], fixed[i][j])
                visited[i][j] = False
                fixed[i][j] = False

            if any(path.fixed.a):
                paths.append(path)
    return paths

def search(maze, fixes, visited, fixed, x, y, d, b):
    if maze[y][x] is '.':
        return d is (b + 2) % 4

    for i in range(4) if maze[y][x] is 'E' else [
            (d + 'SRUL'.index(maze[y][x])) % 4]:
        if not (i is b or i is (d + 2) % 4):
            visited[y][x] = search(maze, fixes, visited, fixed,
                x + dx[i], y + dy[i], i, b) or visited[y][x]

    if visited[y][x]:
        fixed[y][x] = bool(fixes[y][x])
    return visited[y][x]

def greed(maze, F, paths):
    src = BoolsPair((len(maze[0]) - 2) * (len(maze) - 2))
    dest = deepcopy(src)
    mx = deepcopy(src)

    compressed = [True] * len(paths)

    while any(compressed):
        mx.visited.count = 0
        mx.fixed.count = 1

        for i, path in compress(enumerate(paths), compressed):
            dest.merge(src, path)

            if src.visited.count == dest.visited.count or dest.fixed.count > F:
                compressed[i] = None

            elif (mx.visited.count / mx.fixed.count <
                    dest.visited.count / dest.fixed.count):
                mxI = i
                mx, dest = dest, mx

        if any(compressed):
            compressed[mxI] = False
            src, mx = mx, src

    return src, [c is False for c in compressed]

def climb(maze, F, paths, mx, mxAdded):
    timer.limit = 8

    while True:
        updated = False
        added = mxAdded[:]

        for i in compress(range(len(added)), added):
            if timer.elapses():
                return mx

            added[i] = False

            src = BoolsPair((len(maze[0]) - 2) * (len(maze) - 2))
            dest = deepcopy(src)

            for path in compress(paths, added):
                src.merge(src, path)

            for j, path in enumerate(paths):
                if not (i == j or added[j]):
                    dest.merge(src, path)

                    if (dest.fixed.count <= F and
                            mx.visited.count < dest.visited.count):
                        updated = True
                        mx, dest = dest, mx
                        mxAdded[i] = False
                        mxAdded[j] = True
            added[i] = True
        if not updated: break
    return mx

class BoolsPair:
    def __init__(self, n):
        self.visited = Bools(n)
        self.fixed = Bools(n)

    def append(self, visited, fixed):
        self.visited.append(visited)
        self.fixed.append(fixed)

    def merge(self, a, b):
        self.visited.merge(a.visited, b.visited)
        self.fixed.merge(a.fixed, b.fixed)

    def copy(self, a):
        self.visited.copy(a.visited)
        self.fixed.copy(a.fixed)

class Bools:
    def __init__(self, n):
        self.a = [0] * ((n + 62) // 63)
        self.i = 0
        self.count = 0

    def append(self, v):
        self.a[self.i // 63] = self.a[self.i // 63] | v << self.i % 63
        self.i += 1

    def merge(self, a, b):
        self.count = 0
        for i, a, b in zip(count(), a.a, b.a):
            self.a[i] = a | b
            self.count += bin(self.a[i]).count('1')

    def copy(self, a):
        self.count = a.count
        for i, a in enumerate(a.a):
            self.a[i] = a

    def get(self):
        self.i += 1
        return self.a[self.i // 63] >> self.i % 63 & 1

class Timer:
    def __init__(self):
        self.start = time()

    def elapses(self):
        return time() - self.start > self.limit

dx = 1, 0, -1, 0
dy = 0, 1, 0, -1

timer = Timer()

# maze = [raw_input() for _ in range(int(raw_input()))]
# F = int(raw_input())

# ret = MazeFixing().improve(maze, F)

# print(len(ret))
# print('\n'.join(ret))