ARC102-E Stop. Otherwise...

問題リンク

解法

出てくる目を分類してみると、

• 2つ以上選んではいけない目
• ともに選んではいけないペア
• 制約のない目

の つに分かれる。 これらの出る数を決めて組み合わせを計算しようとすると、一回の計算で かかり、全体で となって間に合わない。

ここで、「ともに選んではいけないペア」のうち、どちらか片方を出すものの数を決めてしまえば、これは片方から先に 個差し引いておくことで、制約のない目と同一視できる。

これで、一回 の計算量が になるので、前計算を含めて全体の計算量は になる。

感想

最初、立式が悪くて悩んでいたが、同一視できるところを同一視したら解けた。