Well, for now the only option can only be to sign the puzzle input with SINGLE, since using ANYONE_CAN_PAY will not make the TX valid if other inputs get added (as all the TX inputs are already signed by the sponsor).

This makes the 56-bit challenge tractable, only one SHA256 round overhead, instead of two.

Though it remains a big curiosity what the deal would be with output #0 in this case. It seems to be able to contain basically anything we want, right? For example, someone can lower the fee and use #0 as a transfer, and it would be 100% valid, but probably the nodes will reject it.