RCO presents 日本橋ハーフマラソン 本戦 (オープン)

Submission #1175194

Source codeソースコード

# encoding: utf-8
import random, sys
import time
inputs = lambda: map(int, raw_input().split())

debug = sys.stderr.write

random.seed()

h, w, k, t = inputs()
X, Y = h, w
Cars = [inputs() for i in xrange(k)]
Coms = []

com_str = "LRUD-"
dd = [(0, -1), (0, 1), (-1, 0), (1, 0), (0, 0)]

order = range(k)
ds = range(4)

def dist(x0, y0, x1, y1):
    return abs(x0 - x1) + abs(y0 - y1)

# 整列
bucket = {}
ref = [0]*k
for i in xrange(k):
    x0, y0, x1, y1 = Cars[i]
    bucket.setdefault(y1, []).append(i)
    ref[i] = len(bucket[y1])
lidx = {} # 左index
ridx = {} # 右index
count = {}
for key in bucket:
    bucket[key].sort(key=lambda i: Cars[i][2])
    lidx[key] = 0
    ridx[key] = -1
    count[key] = 0

# ランダムに散らしてみる
for _ in xrange(0):
    random.shuffle(order)
    exist = {(x0, y0) for x0, y0, x1, y1 in Cars}
    coms = ["-"]*k
    for i in order:
        random.shuffle(ds)
        wild = random.randint(0, 3)
        x0, y0, x1, y1 = Cars[i]

        for d in ds:
            dx, dy = dd[d]
            nx = x0 + dx; ny = y0 + dy
            if not 0 < nx <= X or not 0 < ny <= Y:
                continue
            if not wild and dist(x0, y0, x1, y1) <= dist(nx, ny, x1, y1):
                continue

            if (nx, ny) not in exist:
                exist.add((nx, ny))
                Cars[i] = (nx, ny, x1, y1)
                coms[i] = com_str[d]
                break
    Coms.append("".join(coms))

# 整列
ready = set()
while len(ready) < k and len(Coms) < 2000:
    random.shuffle(order)
    exist = {(x0, y0) for x0, y0, x1, y1 in Cars}
    coms = ["-"]*k

    lmi = min(lidx[key] for key in lidx if count[key] < len(bucket[key]))
    rmi = max(ridx[key] for key in ridx if count[key] < len(bucket[key]))
    for i in order:
        if i in ready:
            continue
        x0, y0, x1, y1 = Cars[i]
        lst = bucket[y1]

        g = None
        if lst[lidx[y1]] == i:
            g = (lidx[y1], y1)
        elif lst[ridx[y1]] == i:
            g = (X+ridx[y1], y1)

        if g is None:
            wild = random.randint(0, 5)
        else:
            wild = random.randint(0, 1)
            if len(ready) > k-10:
                wild = random.randint(0, 2) < 1

        xx = X/2 - len(lst)/2 + ref[i]
        yy = y1
        if g is not None:
            if y0 < y1:
                dds = [1] + ds
            elif y0 > y1:
                dds = [0] + ds
            else:
                dds = [2] + ds
        else:
            if y0 < y1:
                dds = [1] + ds
            elif y0 > y1:
                dds = [0] + ds
            else:
                dds = ds
        random.shuffle(dds)
        for d in dds:
            dx, dy = dd[d]
            nx = x0 + dx; ny = y0 + dy
            if not 0 < nx <= X or not 0 < ny <= Y:
                continue
            if not wild:
                if g is not None:
                    if dist(x0, y0, g[0]+1, g[1]) <= dist(nx, ny, g[0]+1, g[1]):
                        continue
                else:
                    if dist(x0, y0, xx, yy) <= dist(nx, ny, xx, yy):
                        continue
            if g is None:
                if nx-1 < lmi+3 and nx < x0:
                    continue
                if X + rmi-3 < nx-1 and x0 < nx:
                    continue
            else:
                if not g[1] - 1 < ny < g[1] + 1:
                    if nx-1 < lmi+2 and nx < x0:
                        continue
                    if X + rmi-2 < nx-1 and x0 < nx:
                        continue
                else:
                    if nx-1 < lidx[y1] and nx < x0:
                        continue
                    if X + ridx[ny] < nx-1 and x0 < nx:
                        continue

            if (nx, ny) not in exist:
                exist.add((nx, ny))
                Cars[i] = (nx, ny, x1, y1)
                coms[i] = com_str[d]
                if g is not None and nx == g[0]+1 and ny == g[1]:
                    if not lmi+1 < nx-1 < X+rmi-1:
                        ready.add(i)
                        if lst[lidx[y1]] == i:
                            if lidx[y1] < len(lst)/2:
                                lidx[y1] += 1
                            count[y1] += 1
                        else:
                            if len(lst)+ridx[y1] > len(lst)/2+1:
                                ridx[y1] -= 1
                            count[y1] += 1
                break

    Coms.append("".join(coms))

# 最後に進んで配置
update = 1
while update:
    update = 0
    exist = {(x0, y0) for x0, y0, x1, y1 in Cars}
    coms = ["-"]*k
    for i in xrange(k):
        x0, y0, x1, y1 = Cars[i]
        if x0 < x1:
            nx = x0 + 1
            if (nx, y0) not in exist:
                Cars[i] = (nx, y0, x1, y1)
                coms[i] = "D"
                exist.add((nx, y0))
                update = 1
        elif x1 < x0:
            nx = x0 - 1
            if (nx, y0) not in exist:
                Cars[i] = (nx, y0, x1, y1)
                coms[i] = "U"
                exist.add((nx, y0))
                update = 1
    Coms.append("".join(coms))

sys.stdout.write("%d\n" % len(Coms))
sys.stdout.write("\n".join(Coms))

Submission

Task問題 B - 日本橋大渋滞
User nameユーザ名 041_tjake
Created time投稿日時
Language言語 Python2 (2.7.6)
Status状態 AC
Score得点 749062
Source lengthソースコード長 5391 Byte
File nameファイル名
Exec time実行時間 2857 ms
Memory usageメモリ使用量 5864 KB

Test case

Set

Set name Score得点 / Max score Cases
test_01 26151 / 50000 subtask_01_01.txt
test_02 24667 / 50000 subtask_01_02.txt
test_03 25880 / 50000 subtask_01_03.txt
test_04 26206 / 50000 subtask_01_04.txt
test_05 24343 / 50000 subtask_01_05.txt
test_06 26681 / 50000 subtask_01_06.txt
test_07 24379 / 50000 subtask_01_07.txt
test_08 25524 / 50000 subtask_01_08.txt
test_09 24167 / 50000 subtask_01_09.txt
test_10 25291 / 50000 subtask_01_10.txt
test_11 25734 / 50000 subtask_01_11.txt
test_12 25330 / 50000 subtask_01_12.txt
test_13 25189 / 50000 subtask_01_13.txt
test_14 25407 / 50000 subtask_01_14.txt
test_15 25189 / 50000 subtask_01_15.txt
test_16 25694 / 50000 subtask_01_16.txt
test_17 25485 / 50000 subtask_01_17.txt
test_18 23332 / 50000 subtask_01_18.txt
test_19 24320 / 50000 subtask_01_19.txt
test_20 24655 / 50000 subtask_01_20.txt
test_21 22584 / 50000 subtask_01_21.txt
test_22 24583 / 50000 subtask_01_22.txt
test_23 25721 / 50000 subtask_01_23.txt
test_24 23993 / 50000 subtask_01_24.txt
test_25 24864 / 50000 subtask_01_25.txt
test_26 24343 / 50000 subtask_01_26.txt
test_27 25681 / 50000 subtask_01_27.txt
test_28 23202 / 50000 subtask_01_28.txt
test_29 24667 / 50000 subtask_01_29.txt
test_30 25800 / 50000 subtask_01_30.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask_01_01.txt AC 2390 ms 5864 KB
subtask_01_02.txt AC 2306 ms 4724 KB
subtask_01_03.txt AC 2389 ms 4468 KB
subtask_01_04.txt AC 2235 ms 4468 KB
subtask_01_05.txt AC 2417 ms 4724 KB
subtask_01_06.txt AC 2197 ms 4468 KB
subtask_01_07.txt AC 2425 ms 4724 KB
subtask_01_08.txt AC 2293 ms 4596 KB
subtask_01_09.txt AC 2653 ms 4724 KB
subtask_01_10.txt AC 2492 ms 4596 KB
subtask_01_11.txt AC 2376 ms 4468 KB
subtask_01_12.txt AC 2388 ms 4596 KB
subtask_01_13.txt AC 2390 ms 4596 KB
subtask_01_14.txt AC 2344 ms 4596 KB
subtask_01_15.txt AC 2594 ms 4596 KB
subtask_01_16.txt AC 2268 ms 4596 KB
subtask_01_17.txt AC 2454 ms 4596 KB
subtask_01_18.txt AC 2668 ms 4852 KB
subtask_01_19.txt AC 2727 ms 4724 KB
subtask_01_20.txt AC 2586 ms 4596 KB
subtask_01_21.txt AC 2857 ms 4980 KB
subtask_01_22.txt AC 2499 ms 4596 KB
subtask_01_23.txt AC 2406 ms 4596 KB
subtask_01_24.txt AC 2780 ms 4724 KB
subtask_01_25.txt AC 2464 ms 4596 KB
subtask_01_26.txt AC 2601 ms 4724 KB
subtask_01_27.txt AC 2266 ms 4596 KB
subtask_01_28.txt AC 2814 ms 4852 KB
subtask_01_29.txt AC 2542 ms 4596 KB
subtask_01_30.txt AC 2340 ms 4596 KB