2021-08-08から1日間の記事一覧
atcoder.jp 解法 参考: 桁DPについて nizi-24.hatenablog.com 桁DPをしよう。 dp[i][smaller][k] ← i: 上から何桁目まで確定しているか、smaller: 未満フラグ、k: 今までに何個0以外の数字が登場したか 遷移するときには、0かどうかで場合分けすればよい。 …
atcoder.jp 桁DPの問題。初めて桁DPについて学んだので記事にします。 桁DPとは? ・N以下の自然数で条件を満たすものは何通りか? ・N以下の自然数で条件を満たすものの中で最大のものはいくつか? みたいな問題で活躍するアルゴリズムです。 説明は少し複…