JunKobayashi https://blog.hatena.ne.jp/JunKobayashi/ JunKobayashi's Diary https://junkobayashi.hatenablog.com/ ABC本番で敗北した問題 動的計画法 部分文字列 惨敗した回。C問題の方針を見出すのに時間がかかりすぎて（\(j\)を固定した時、\(N\)個それぞれの条件を満たすことができる文字列が存在するかを定数時間で答えられるようにするのが本質）全く方針が見えず撃沈。おそらくは 公式解説 と同じ内容となるが、自分にとって理解のしやすいようにまとめ直す。 ※以下、全て0-indexedを前提とし、文字列\(S\)の部分文字列である\[S[i]S[i+1] \dots S[j - 2]S[j - 1]\]を\(S[i:j)\)という形式で表記するものとする。 ＜問題概要＞ ABC452 D - No-Subsequence Substring 英小文字から… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fjunkobayashi.hatenablog.com%2Fentry%2F2026%2F04%2F05%2F221757" title="ABC452 D - No-Subsequence Substring - JunKobayashi&#39;s Diary" 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 2026-04-05 22:17:57 rich https://junkobayashi.hatenablog.com/entry/2026/04/05/221757 1.0 100%