問題文

https://atcoder.jp/contests/abc354/tasks/abc354_e

• 最初の発想

bitDP を使う発想

残っているカードの集合を $S$ としたときに $\mathrm{dp}[S]$ が true の場合、その手番の人は勝つルートが必ずある。 false の場合、その手番の人は勝てるルートがない。というdpを考える。

一つだけ必ず自明な答えがあってカードの集合が0枚のときはその手番の人は必ず負ける。

なので集合のbitを0からスタートして 1<<n まで見ていくのがよさそう。

実装について考える。

以降 bit をカードの集合として考える。

カード i j を選んで bit から i桁目とj桁目を0にした値を 'bit とすると $\mathrm{dp}('bit)= false$ なら bit の手番だと必ず勝てることになる。

つまり自分に選択権があり、iのカードとjのカードを選べば相手詰ませる選択ができるよ！ということ。

少しだけ実装がややこしいので

カード i j を選んで bit から i桁目とj桁目を0にした値を 'bit

この部分だけ明確に書く。

if(!dp[bit ^ 1<<i ^ 1<<j]) now = true;

XOR を使って楽に実装している。