#1170619 (Python3) No.3740 Troublesome Congestion

• 問題: No.3740 Troublesome Congestion
• ユーザー: 👑 kencho
• 提出日時: 2026-07-09 12:03:10
• 言語: Python3 (3.14.7 + numpy 2.5.2 + scipy 1.18.0 + ACL)
• 結果: WA
• 実行時間: -
• コード長: 6,244 bytes
• コンパイル時間: 62 ms
• コンパイル使用メモリ: 15,744 KB
• 実行使用メモリ: 11,648 KB
• 最終ジャッジ日時: 2026-09-19 12:32:10
• 合計ジャッジ時間: 2,332 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

サブタスク	配点	結果
部分点1	20 %	WA * 7
部分点2	30 %	WA * 12
満点	50 %	WA * 26
合計	4 * 0% = 0 点

ソースコード

import sys

N = 50


def connect_stair(G, entries):
    """
    entries = [(r, c), ...] を上から順につなぐ。
    各 entry から右、次に下、右、下...という一本の collector に合流させる。
    collector 上では分岐しないので、P を踏んだ後の suffix は 1 通りになる。
    """
    if not entries:
        return

    entries.sort()

    cur_r, cur_c = entries[0]

    for nxt_r, nxt_c in entries[1:]:
        # 右へ
        for c in range(cur_c, nxt_c + 1):
            if G[cur_r][c] != 'P':
                G[cur_r][c] = '.'

        # 下へ
        for r in range(cur_r, nxt_r + 1):
            if G[r][nxt_c] != 'P':
                G[r][nxt_c] = '.'

        cur_r, cur_c = nxt_r, nxt_c

    # 最後は右端へ行き、右端を下ってゴールへ
    for c in range(cur_c, N):
        if G[cur_r][c] != 'P':
            G[cur_r][c] = '.'

    for r in range(cur_r, N):
        if G[r][N - 1] != 'P':
            G[r][N - 1] = '.'


def build_binary(M):
    """
    二進 partial。

    k 段目の prefix 経路数を 2^k にする。
    bit k が 1 なら、その段から P へ 1 本だけ出口を出す。

    47 段まで入るので、0 <= M < 2^47 は必ず構築できる。
    """
    K = 47
    if not (0 <= M < (1 << K)):
        return None

    G = [['#'] * N for _ in range(N)]

    # prefix chain
    # stage k: (k,k) -> (k+1,k+1) に 2 通り
    for k in range(K):
        r = k
        c = k
        G[r][c] = '.'
        G[r][c + 1] = '.'
        G[r + 1][c] = '.'
        G[r + 1][c + 1] = '.'

    G[K][K] = '.'

    entries = []

    for k in range(K):
        if (M >> k) & 1:
            # (k,k) への prefix は 2^k。
            # (k,k+1) までは prefix 2^k のまま。
            # その右に P を置く。
            pr = k
            pc = k + 2
            er = k
            ec = k + 3

            if ec >= N:
                return None

            G[pr][pc] = 'P'
            G[er][ec] = '.'
            entries.append((er, ec))

    connect_stair(G, entries)

    G[0][0] = '.'
    G[N - 1][N - 1] = '.'

    return G


def build_ternary(M):
    """
    三進 partial。

    32 段の 3-way gadget を使う。
    各段は縦長 3x2 または横長 2x3 の矩形。

    縦長 gadget:
        入力から右上側の外へ出る P は prefix 1*x
        入力から中央右側の外へ出る P は prefix 2*x

    横長 gadget:
        digit 0/1 の段にだけ使う。
        digit 2 は扱いづらいので、その段は必ず縦長にする。

    50x50 に収めるため、縦長 gadget はちょうど 17 個にする。
    したがって、三進表現中の digit 2 の個数が 18 個以上だと失敗する。
    """
    K = 32
    LIM = pow(3, K)

    if not (0 <= M < LIM):
        return None

    digits = []
    x = M
    for _ in range(K):
        digits.append(x % 3)
        x //= 3

    if x != 0:
        return None

    # digit 2 の段は縦長必須。
    forced_vertical = [i for i, d in enumerate(digits) if d == 2]
    if len(forced_vertical) > 17:
        return None

    vertical = [False] * K
    for i in forced_vertical:
        vertical[i] = True

    # 縦長を合計 17 個にする。
    need = 17 - len(forced_vertical)
    for i in range(K):
        if need == 0:
            break
        if not vertical[i]:
            vertical[i] = True
            need -= 1

    if sum(vertical) != 17:
        return None

    G = [['#'] * N for _ in range(N)]
    entries = []

    r = 0
    c = 0
    G[r][c] = '.'

    for k in range(K):
        d = digits[k]

        if vertical[k]:
            # 縦長 3x2 gadget
            #
            # 入力: (r,c)
            # 出力: (r+2,c+1)
            #
            # 経路数は 3 倍。
            #
            # prefix が x の場所:
            #   (r,c+1)
            # prefix が 2x の場所:
            #   (r+1,c+1)
            for rr in range(r, r + 3):
                for cc in range(c, c + 2):
                    G[rr][cc] = '.'

            if d == 1:
                pr, pc = r, c + 2
                er, ec = r, c + 3
            elif d == 2:
                pr, pc = r + 1, c + 2
                er, ec = r + 1, c + 3
            else:
                pr = pc = er = ec = None

            nr, nc = r + 2, c + 1

        else:
            # 横長 2x3 gadget
            #
            # digit 0/1 のときだけ使う。
            #
            # 入力: (r,c)
            # 出力: (r+1,c+2)
            #
            # prefix が x の場所:
            #   (r,c+2)
            assert d in (0, 1)

            for rr in range(r, r + 2):
                for cc in range(c, c + 3):
                    G[rr][cc] = '.'

            if d == 1:
                pr, pc = r, c + 3
                er, ec = r, c + 4
            else:
                pr = pc = er = ec = None

            nr, nc = r + 1, c + 2

        if d != 0:
            if not (0 <= pr < N and 0 <= pc < N and 0 <= er < N and 0 <= ec < N):
                return None

            G[pr][pc] = 'P'
            G[er][ec] = '.'
            entries.append((er, ec))

        r, c = nr, nc
        if not (0 <= r < N and 0 <= c < N):
            return None
        G[r][c] = '.'

    connect_stair(G, entries)

    G[0][0] = '.'
    G[N - 1][N - 1] = '.'

    return G


def fallback_wrong_grid():
    """
    unsupported な M に対しても RE しないための出力。
    当然ほとんどの M では WA になる。
    partial 提出らしくするためのもの。
    """
    G = [['#'] * N for _ in range(N)]
    for i in range(N):
        G[0][i] = '.'
        G[i][N - 1] = '.'
    # P がないので、P をちょうど 1 回押す経路数は 0。
    return G


def solve():
    M = int(sys.stdin.readline())

    # 三進を優先。通れば二進よりかなり広い。
    G = build_ternary(M)

    # fallback として二進。
    if G is None:
        G = build_binary(M)

    # それでも無理なら、形式だけ正しい不正解グリッド。
    if G is None:
        G = fallback_wrong_grid()
    print(N)
    print('\n'.join(''.join(row) for row in G))


if __name__ == "__main__":
    solve()