Day 177-Q1 — 2026-10-13 | 3 行の Chomp（(b,c) ごとに後手勝ちの a がただ 1 つ、という性質で O(N^3) 状態を O(N^2) 個の値に縮める）

📋 コピーimport sys


def main():
    data = sys.stdin.buffer.read().split()
    q = int(data[0])
    qs = [(int(data[1 + 3 * i]), int(data[2 + 3 * i]), int(data[3 + 3 * i])) for i in range(q)]
    n = max(b for _, b, _ in qs)
    NONE = -1
    # P[b][c]: (a,b,c) が後手勝ち（P 局面）になる唯一の a。無ければ NONE
    P = [[NONE] * (b + 1) for b in range(n + 1)]
    # rowmask[c]: y<b についての P(y, min(c,y)) をビットで持つ（2 行目を y に縮める手の行き先）
    rowmask = [0] * (n + 1)
    # dead[c]: 1 行目を x (1<=x<b) に縮めた (x,x,min(c,x)) が P になる x があるか
    dead = [False] * (n + 1)
    for b in range(n + 1):
        colmask = 0                       # z<c についての P(b,z)（3 行目を z に縮める手の行き先）
        Pb = P[b]
        lo = b if b >= 1 else 1
        for c in range(b + 1):
            if dead[c]:
                v = NONE
            else:
                x = (rowmask[c] | colmask) >> lo
                v = lo + (~x & (x + 1)).bit_length() - 1   # lo 以上で、どちらの集合にも無い最小の a
                colmask |= 1 << v
            Pb[c] = v
        for c in range(n + 1):
            v = Pb[c if c < b else b]
            if v >= 0:
                rowmask[c] |= 1 << v
                if b >= 1 and v == b:     # (b,b,min(c,b)) が P → 以後この c では 1 行目を b に縮めて勝てる
                    dead[c] = True
    out = []
    for a, b, c in qs:
        out.append("Second" if P[b][c] == a else "First")
    print("\n".join(out))


main()