enakai00 https://blog.hatena.ne.jp/enakai00/ めもめも https://enakai00.hatenablog.com/ 何の話かと言うと atcoder.jp上記の問題をネタに「ギリギリ間に合う系」、もしくは、「より一般にはもっと多くの種類で考えてもよさそうなのに、なぜか具体的な少数のものに限定されている」系の話をします。 実行時間の見積もり PyPy3 での実行時間を調べてみます。 for _ in range(10**9): pass # 902 ms for _ in range(10**10): pass # 8416 ms これより、制限時間 2s の問題であれば、 回のループまではなんとか間に合うことがわかります。 素朴な解法 例えば、4 文字の部分列を作るのであれば、最初の文字は、・文字列 S の… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fenakai00.hatenablog.com%2Fentry%2F2021%2F07%2F31%2F132905" title="006 - Smallest Subsequence（★5）の解説 - めもめも" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2021-07-31 13:29:05 rich https://enakai00.hatenablog.com/entry/2021/07/31/132905 1.0 100%