Digit DP 入門 - torus711 のアレ
はじめに 動的計画法のパターンの一つで，「Digit DP」とか「桁 DP」と呼ばれているものがあります．問題によって異なってくる部分もありますが，問題によらず共通している部分がかなりあるので，その部分を中心に解説してみたいと思います． Digit DP とは？ 「ある整数 以下の非負整数であって，ある条件を満たすものの個数を求めよ」といったタイプの数え上げ問題を解くときにしばしば使われる手法です．Digit DP は，整数の各桁に入る値を 1 桁ずつ決めていくという全探索を DP 化したものです．「ある条件」の部分はとりあえず置いておいて，「 以下の非負整数を数える」というのを例にしてみようと思います．答えは当然 ですが，これを Digit DP で求めることで Digit DP の本質的なアイデアが見えてくると思います．また，求める整数は 10 進表記であるとします． Digit DP
「998244353 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜 - Qiita
1. なぜ 998244353 で割るのか？ 最初はこのような設問を見るとぎょっとしてしまいますが、実はとても自然な問題設定です。 $998244353$ で割らないと、答えの桁数がとてつもなく大きくなってしまうことがあります。このとき以下のような問題が生じます: 多倍長整数がサポートされている言語とされていない言語とで有利不利が生じる 10000 桁にも及ぶような巨大な整数を扱うとなると計算時間が膨大にかかってしまう 1 番目の事情はプログラミングコンテストに特有のものと思えなくもないですが、2 番目の事情は切実です。整数の足し算や掛け算などを実施するとき、桁数があまりにも大きくなると桁数に応じた計算時間がかかってしまいます。実用的にもそのような巨大な整数を扱うときは、いくつかの素数で割ったあまりを計算しておいて、最後に中国剰余定理を適用して復元することも多いです。 なぜ 9982443
動的計画法超入門！ Educational DP Contest の A ～ E 問題の解説と類題集 - Qiita
0. はじめに: 非常に素敵な DP の入門コンテンツ 待ちに待ったコンテストの到来です！！！！！ DP (動的計画法) はアルゴリズムの登竜門というべき難所ですが、いくつか問題を解いて行くとパターンのようなものが見えて来ます。まさに「習うより慣れろ」の世界で、たくさん問題を解いて行くうちに、DP な問題の解法を一言で言えるようになって来ます。 典型を学ぶ方法論として、その最も典型的なシンプルな形をした問題をそのまま吸収してしまうのは 1 つの有効な方法だと思います。それにふさわしいシンプルな問題たちを集めた DP コンテストが先日開かれました。DP 以外にもこういうのが欲しい気持ちになりますね。 Educational DP Contest / DP まとめコンテスト 全部で A 問題から Z 問題まで 26 問あります。今回はこれらの問題に対し 簡単なコメントや解説、その他の解説へのリ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
