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ユーザ名 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