drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AtCoder AtCoder500点 ABC-E DP状態:smaller(桁DP) 数え上げ問題 leading zero 再帰的構造に着目する 二項係数 水色diff DP 制約条件:総和<=K 制約条件:ちょうどK個 どの場所で初めてsmallerになるかを考える DP状態:どの桁まで見たか(広義の桁DP) NoviSteps1Q DP しなくても間に合うけど、桁 DP 的な考え方が役に立つ！ 問題へのリンク 問題概要 100 桁以下の整数 が与えられる。 以上 以下の整数であって、十進法表記で 0 以外の数値がちょうど 個であるようなものが何個あるのかを求めよ。 制約 の桁数 考えたこと 一般に大きな整数 が与えられて、それ以下の整数で条件を満たすもの全体について調べたいとき、こんな感じの考え方が使える！！！ drken1215.hatenablog.com たとえば、S = 314159 のときは、まずは 000000 〜 099999 100000 〜 299999 300000 〜 314159 とに場合分けして… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2020%2F02%2F09%2F225300" title="AtCoder ABC 154 E - Almost Everywhere Zero (1Q, 水色, 500 点) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/80936665/1687765056723440 Hatena Blog https://hatena.blog 2020-02-09 22:53:00 rich https://drken1215.hatenablog.com/entry/2020/02/09/225300 1.0 100%