Fool Game (PKU 2542)

http://poj.org/problem?id=2542

問題

トランプの6〜Aを使ってカードゲームを行う。まず先手がカードを1枚場に出す。以降次の操作を繰り返す。
後手はそのカードに勝つカードを1枚場に出す。その次に先手は場に出ているカードと同じランクのカードを出す。
上記の操作を繰り返してカードを出せなくなったほうが負けになる。先手が勝つためには最初にどのカードを出せば良いか？複数通りある場合は辞書順最小を答えよ。

解法

どちらの手番か、二人の持っているカード、直前に出されたカードをキーとしてメモ化DPを行う。setでやったら間に合わなかったが、状態をlong longで保持したら間に合った。