Day 178-Q2 — 2026-10-14 | 4 行の Chomp（(b,c,d) ごとに後手勝ちの a は高々 1 つ。P(b,c,d) を 3 種の「縮める手」の集合の mex で O(N^3) 個の表に）

📋 コピーimport sys


def build(n):
    """P[b][c][d]: (a,b,c,d) が後手勝ちになる唯一の a（無ければ -1）。n >= b >= c >= d >= 0"""
    NONE = -1
    P = [[[NONE] * (c + 1) for c in range(b + 1)] for b in range(n + 1)]
    # rowmask[c][d]: b'<b の P(b', min(c,b'), min(d,b'))（2 行目を縮める手の行き先）
    rowmask = [[0] * (n + 1) for _ in range(n + 1)]
    # dead[c][d]: 1 行目を x (1<=x<b) に縮めた (x,x,min(c,x),min(d,x)) が後手勝ちになる x があるか
    dead = [[False] * (n + 1) for _ in range(n + 1)]
    for b in range(n + 1):
        lo = b if b >= 1 else 1
        Pb = P[b]
        colmask = [0] * (n + 1)           # z<c の P(b, z, min(d,z))（3 行目を縮める手）
        for c in range(b + 1):
            Pbc = Pb[c]
            rm = rowmask[c]
            dd = dead[c]
            cm = colmask
            wmask = 0                     # w<d の P(b, c, w)（4 行目を縮める手）
            for d in range(c + 1):
                if dd[d]:
                    v = NONE
                else:
                    x = (rm[d] | cm[d] | wmask) >> lo
                    v = lo + (~x & (x + 1)).bit_length() - 1
                    wmask |= 1 << v
                Pbc[d] = v
            for d in range(n + 1):        # 後の c' > c から見た「3 行目を c に縮める手」
                v = Pbc[d if d < c else c]
                if v >= 0:
                    colmask[d] |= 1 << v
        for c in range(n + 1):            # 後の b' > b から見た「2 行目を b に縮める手」
            cc = c if c < b else b
            Pbc = Pb[cc]
            rm = rowmask[c]
            dd = dead[c]
            for d in range(c + 1):
                v = Pbc[d if d < cc else cc]
                if v >= 0:
                    rm[d] |= 1 << v
                    if b >= 1 and v == b:  # (b,b,..) が後手勝ち → 以後この (c,d) は 1 行目を b に縮めて勝てる
                        dd[d] = True
    return P


def main():
    data = sys.stdin.buffer.read().split()
    q = int(data[0])
    qs = [tuple(int(v) for v in data[1 + 4 * i:5 + 4 * i]) for i in range(q)]
    n = max(b for _, b, _, _ in qs)
    P = build(n)
    print("\n".join("Second" if P[b][c][d] == a else "First" for a, b, c, d in qs))


if __name__ == "__main__":
    main()