MM89 考えたこと
マラソン参加３回目、がっつり参加したのは初めてだけれど楽しかったです。
暫定 72.34点 15位 Python
問題文 https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16494&pm=10967
全部Ｓにしたら１００％になるよねーと思って上からＳＥ以外をＳにする。
３８点
初期解（ランダム解）でなぜ迷路がほとんどできないのか考えてみる。
境界からスタートしてランダムに動いてもその場からあまり動かない。迷路の中心に向かう力がない。大きな迷路ができにくい。
ビジュアライザを無効なパスを表示するように変えてみる。
Ｕに突っ込んでる。Ｕを変えればよい。
くるっと回転して自分のパスに突っ込んでる。回転しなければよい。直進すればよい？やっぱりＳが強い？
直進すれば迷路の中心に向かって迷路が大きくなり、回転して死ぬこともなくなる？
紙にいろいろ書いて思いつく。
ＬとＲが交互に並ぶようなライン（間にＳやＥはあってもよい）はどこから進入しても下から入れば上へ、上から入れば下へ抜ける。蛇行しながら直進する。
このラインを下端から上端まで積めば下端から上端、上端から下端へ抜ける迷路がたくさんできる。
このＬとＲが交互になるような修正をＸ座標が小さい順にＦ個とる。
６４点
ここでかなり迷走したので数多のソースが生まれそして死んでいった。
複数の迷路が密に重なっているのがよくないのではと思った。
複数の迷路で修正を共有しているのはメリットだけれど、マスを共有しているのはデメリットなのでトータル損してそう。もっと高効率な迷路をばらけさせたい。
ＬとＲが交互になるような修正を全体にしたうえで有効な迷路を列挙する。
厳密に列挙すると指数時間になってしまうので、上左右の移動だけ、下左右の移動だけでできる迷路を列挙する。列挙漏れはＥがからむときだけなので見なかったことにする。この制限でメモ化ができるようになってるはずなんだけど今自分の実装見るとしてない。あれ？
で、列挙した迷路をＦを超えない範囲で近似スコアが最大になるように選択する組み合わせ問題になった。
最初ＤＰしようとしたけどマスが共有されているのでできなんだ。
迷路ごとのマス数／修正数が大きい順にＦを超えない範囲で選んでいく（貪欲）。
７１点
選択した迷路をひとつのぞいて別の迷路を選択して近似スコアが上がれば採用（山登り）。
７２点
焼きなまそうと思ったけどよくわからず。
おわり
その他
方針さえあってれば Python でも探索時間減るだけやし上位狙わなければへーきへーきと思ったけど全然きつい。終わる前提の処理が終わらない終わらない。配列使いまわしたり、boolの２次元配列を整数の１次元配列に圧縮したり、なくなく迷路集合カットするなどした。
ＬとＲを交互にするというアイデアに固執しすぎた感。マラソン終わるまで現解法の発展が上位の解法だと信じて疑わなかった。反省。
ＥとＥを優先的につなぐように修正してみたけど微増だったのでやめた。テストケースごとのスコアは大きく上下するのがたまにある感じでＷＨＦに特徴がみられなかった。今思うとＥの割合とかもっとよく見ればよかった。平均じゃなくてＦが多いとか少ないとか個々のテストケース見るの大事。
結局乱数使わなかったんだけどこれでいいのか。
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))
