結果

問題 No.3740 Troublesome Congestion
コンテスト
ユーザー 👑 kencho
提出日時 2026-09-03 04:41:04
言語 Python3
(3.14.7 + numpy 2.5.2 + scipy 1.18.0 + ACL)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
AC  
実行時間 51 ms / 2,000 ms
+ 884µs
コード長 2,243 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 64 ms
コンパイル使用メモリ 15,232 KB
実行使用メモリ 11,776 KB
最終ジャッジ日時 2026-09-19 13:01:50
合計ジャッジ時間 3,580 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
部分点1 20 % AC * 7
部分点2 30 % AC * 12
満点 50 % AC * 26
合計 4 * 100% = 400 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys

N = 40

def build(m):
    g = [["#"] * N for _ in range(N)]
    for r in range(N):
        for c in range(N):
            if -2 <= r - c <= 3:
                g[r][c] = "."
    switches, exits = [], []
    for r in range(N):
        c = r + 2
        if c + 2 < N:
            switches.append((r, c + 1)); exits.append((r, c + 2))
    for c in range(N):
        r = c + 3
        if r + 2 < N:
            switches.append((r + 1, c)); exits.append((r + 2, c))
    for r in range(N):
        for c in range(N):
            if r + c >= 2 * N - 7 and g[r][c] == ".":
                g[r][c] = "#"
    dp = [[0] * N for _ in range(N)]
    dp[0][0] = 1
    for r in range(N):
        for c in range(N):
            if (r or c) and g[r][c] == ".":
                dp[r][c] = (dp[r - 1][c] if r else 0) + (dp[r][c - 1] if c else 0)
    values = [(dp[r - 1][c] if r else 0) + (dp[r][c - 1] if c else 0) for r, c in switches]
    chosen = []
    for i in sorted(range(len(values)), key=values.__getitem__, reverse=True):
        if values[i] <= m:
            m -= values[i]; chosen.append(i)
    assert m == 0
    upper, lower = [], []
    for i in chosen:
        r, c = switches[i]
        g[r][c] = "P"
        er, ec = exits[i]
        g[er][ec] = "."
        (upper if er < ec else lower).append((er, ec))
    def connect(cells, up):
        if not cells: return
        cells.sort(); r, c = cells[0]
        for nr, nc in cells[1:]:
            if up:
                for x in range(c, nc + 1): g[r][x] = "."
                for y in range(r, nr + 1): g[y][nc] = "."
            else:
                for y in range(r, nr + 1): g[y][c] = "."
                for x in range(c, nc + 1): g[nr][x] = "."
            r, c = nr, nc
        if up:
            for x in range(c, N): g[r][x] = "."
            for y in range(r, N): g[y][-1] = "."
        else:
            for y in range(r, N): g[y][c] = "."
            for x in range(c, N): g[-1][x] = "."
    connect(upper, True); connect(lower, False)
    g[0][0] = g[-1][-1] = "."
    return g

it = iter(map(int, sys.stdin.buffer.read().split()))
out = []
for _ in range(next(it)):
    grid = build(next(it))
    out.append(str(N)); out.extend(map("".join, grid))
print("\n".join(out))
0