Cまで三完でした。レートはやや下がったけど、ABで詰まって動揺してしまってもCを通せた、というのは良かった。
D - Unique Subsequence
解説AC。
制約からDPを使いそうなこと、一意な部分列を得たいので、部分列DPみたいな考え方をしそうなことも分かる。
だがそこから考察を進められなかった。
そこから、公式解説に書いてある必要十分条件に至る部分は、どうにかして考察してたどりつかねばいけないように思う。難しいけれど、時間かければ思いつけた気もするし、どうだろう……。
その後の実装はDPなのだけど、各数字について「その数字がでてきたindexたち」をメモしながら進めていくことがポイントか。
そうやって実装したものを、Binary Indexed Tree で高速化すれば良い。
0 件のコメント:
コメントを投稿