結果

問題 No.3740 Troublesome Congestion
コンテスト
ユーザー 👑 rin204
提出日時 2026-09-19 21:53:59
言語 PyPy3
(7.3.23 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 1,334 ms / 2,000 ms
+ 535µs
コード長 4,792 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 770 ms
コンパイル使用メモリ 83,380 KB
実行使用メモリ 163,684 KB
最終ジャッジ日時 2026-09-19 21:54:51
合計ジャッジ時間 29,007 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
部分点1 20 % AC * 7
部分点2 30 % AC * 12
満点 50 % AC * 26
合計 4 * 100% = 400 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import random

random.seed(0)


def f(n, thr):
    A = [[0] * n for _ in range(n)]
    dp = [[0] * n for _ in range(n)]
    dp[0][0] = 1
    for i in range(n):
        for j in range(n):
            if random.random() < thr and not (i == 0 or j == 0 or (i == j == n - 1) or i == n - 1):
                A[i][j] = 1
                continue
            if i > 0:
                dp[i][j] += dp[i - 1][j]
            if j > 0:
                dp[i][j] += dp[i][j - 1]

    return A, dp[-1][-1]


def create(n):
    dic = {}
    while len(dic) < 1000:
        A, cnt = f(n, random.random())
        dic[cnt] = A

    A = [[1] * n for _ in range(n)]
    dic[0] = A

    pairs = {}
    for c1 in dic.keys():
        for c2 in dic.keys():
            pairs[c1 * c2] = (c1, c2)

    cs = sorted(pairs.keys())
    return dic, sorted(dic.keys()), cs, pairs


dic, _, cs2, pairs = create(10)

dic2, cs1, _, _ = create(8)


def check(A):
    n = len(A)
    assert n == len(A[0])
    dp1 = [[0] * n for _ in range(n)]
    dp2 = [[0] * n for _ in range(n)]
    dp1[0][0] = 1

    for i in range(n):
        for j in range(n):
            if A[i][j] == "#":
                continue
            if A[i][j] == "P":
                if i > 0:
                    dp2[i][j] += dp1[i - 1][j]
                if j > 0:
                    dp2[i][j] += dp1[i][j - 1]
            else:
                if i > 0:
                    dp1[i][j] += dp1[i - 1][j]
                    dp2[i][j] += dp2[i - 1][j]
                if j > 0:
                    dp1[i][j] += dp1[i][j - 1]
                    dp2[i][j] += dp2[i][j - 1]
    return dp2[-1][-1]


def max_(k, cs1, cs2):
    idx = len(cs2) - 1
    ma = -1
    res = None

    for c in cs1:
        while c * cs2[idx] > k:
            idx -= 1
        if c * cs2[idx] > ma:
            ma = c * cs2[idx]
            res = (c, cs2[idx])
    return res


def solve(m, out=True):
    M = m
    N = 40
    ans = [["."] * N for _ in range(N)]
    ans[-2][-1] = "P"
    ans[-1][-2] = "P"

    c1, c2 = max_(m, cs2, cs2)

    start = [(0, 0), (9, 9), (18, 18), (27, 27)]
    boards = []
    boards.append(dic[pairs[c1][0]])
    boards.append(dic[pairs[c1][1]])
    boards.append(dic[pairs[c2][0]])
    boards.append(dic[pairs[c2][1]])

    for (si, sj), b in zip(start, boards):
        for i in range(10):
            for j in range(10):
                if b[i][j] == 1:
                    ans[i + si][j + sj] = "#"

        ti = si + 9
        tj = sj + 9
        for k in range(9):
            ans[ti + 1][tj - k - 1] = "#"
            ans[ti - k - 1][tj + 1] = "#"
            if si != 0 and k != 8:
                ans[si - 1][tj - k - 1] = "#"
                ans[ti - k - 1][sj - 1] = "#"

    m -= c1 * c2
    ans[10][0] = "."
    ans[11][1] = "#"
    c1, c2 = max_(m, cs1, cs2)
    start = [(13, 0), (20, 7), (29, 16)]
    ns = [8, 10, 10]
    boards = []
    boards.append(dic2[c1])
    boards.append(dic[pairs[c2][0]])
    boards.append(dic[pairs[c2][1]])

    for (si, sj), b, sn in zip(start, boards, ns):
        for i in range(sn):
            for j in range(sn):
                if b[i][j] == 1:
                    ans[i + si][j + sj] = "#"

        ti = si + sn - 1
        tj = sj + sn - 1
        for k in range(sn - 1):
            ans[ti + 1][tj - k - 1] = "#"
            ans[ti - k - 1][tj + 1] = "#"
            if si != 0 and k != sn - 2:
                ans[si - 1][tj - k - 1] = "#"
                ans[ti - k - 1][sj - 1] = "#"

    m -= c1 * c2
    ans[0][10] = "."
    ans[1][11] = "#"
    c1, c2 = max_(m, cs1, cs2)
    start = [(0, 13), (7, 20), (16, 29)]
    ns = [8, 10, 10]
    boards = []
    boards.append(dic2[c1])
    boards.append(dic[pairs[c2][0]])
    boards.append(dic[pairs[c2][1]])

    for (si, sj), b, sn in zip(start, boards, ns):
        for i in range(sn):
            for j in range(sn):
                if b[i][j] == 1:
                    ans[i + si][j + sj] = "#"

        ti = si + sn - 1
        tj = sj + sn - 1
        for k in range(sn - 1):
            ans[ti + 1][tj - k - 1] = "#"
            ans[ti - k - 1][tj + 1] = "#"
            if sj != 0 and k != sn - 2:
                ans[si - 1][tj - k - 1] = "#"
                ans[ti - k - 1][sj - 1] = "#"
    m -= c1 * c2

    ans[-3][-4] = "#"
    ans[-3][-3] = "#"
    ans[-3][-2] = "#"
    ans[38][26] = "#"
    ans[26][38] = "#"
    if m > 0:
        ans[21][0] = "."
        for i in range(22, 37):
            ans[i][1] = "#"
        ans[37][m] = "#"

    if out:
        print(N)
        for row in ans:
            print(*row, sep="")

    assert M == check(ans), (M, check(ans))


for _ in range(int(input())):
    m = int(input())
    solve(m)

# for i in range(10000):
#     n = random.randrange(10**18)
#     print(i, n)
#     solve(n, False)
0