ABC 401-500/ABC446E - Multiple-Free Sequences - 競技プログラミング用 知識集積所

---

問題

ABC446E

必要知識

B以下レベルの内容は省略

• メモ化再帰※

考え方

Mが最大1000なので、modM上で初項と第2項の組を全て考えても最大100万通り。
そして、初項がMの倍数でない限り、「初項、第2項」の判定は「第2項、第3項」の判定をコピーすればよい。
よって、動的計画法かメモ化再帰※のようなアルゴリズムが有用。
しかし問題は参照先がループする可能性があることで、それへの対処が必要。

これは、「OK」「NG」「未調査」「調査中」の4つのステータスをもってメモ化再帰※をすることで対応できる。
すなわち、参照先をどんどん掘っていって、

• 「OK」に当たったら、通ってきたとこ全部OK
• 「NG」に当たったら、通ってきたとこ全部NG
• 「調査中」に当たったら、問題ないところだけでループするということなので、通ってきたとこ全部OK

という判定にすればよい。

解答例

解答例

注意点

別解