先週から時間を見つけてEの復習してるんですが、未だに理解できてません。Eと言えど茶色の人も解けてる問題なので、ここまで手こずる事は予想してませんでした。同一レート内でも自頭が劣るのは自覚してるのだけど、それにしてもここまで難しいとは…それとも理解する方向が徹底的に間違ってるとか。
理解のために桁DPの解説を色々調べてたんですが、結論から言うと自分レベルに分かる説明をしてくれてるサイトは見つかりませんでした。これだけ解説サイトがあるので、1つくらい灰色レベルが対象のサイトさんがあればいいなと思ってたけど、需要ないのかな…
その中でも一番わかりやすかったが、以下のサイトさんでした。単にNまでの数を数えるだけを桁DPの構造で計算する、というので理解が進んだ気がします。ただ、例題２の「3が付く数字」が複雑で、途中の実装がどうしてそうなるのかの説明があればもっと助かった…dp[i][0][1]の計算が考えること多すぎて難しくないですか？ともかく有難うございます。＞サイト主の方
世界一わかりやすい？桁DPの実装 - Qiita
単純にNを数えるだけの実装。（N=234）
#include <iostream> #include <string> #include <string.h> using namespace std; int main() { // n = 234 までの整数を数え上げるプログラム std::string n = "234"; const int digit = n.size(); // 該当する数字の数を格納する配列 // 桁数×未満フラグ（該当桁がn未満なら0、nなら1） int dp[digit][2]; memset(dp, 0, sizeof(int)*digit*2); // 1桁づつ計算 int x0 = n[0] - '0'; dp[0][0] = x0; // 1桁目でn未満なのは0～1の2個（=x0） dp[0][1] = 1; // 1桁目でnなのは2の1個 dp[1][0] = 23; // 2桁目でn未満なのは0～19＋20～22の23個 // 計算方法は(dp[0][0]×10)+(nの2桁目) dp[1][1] = 1; // 2桁目でnなのは23の1個 dp[2][0] =234; // 3桁目でn未満なのは0～229＋230～233の234個 // 計算方法は(dp[1][0]×10)+(nの3桁目) dp[2][1] = 1; // 3桁目でnなのは234の1個 #if 0 // 上の計算を一般化した場合 for(int i=1; i<digit; i++){ int x = n[i] - '0'; dp[i][0] = dp[i-1][0]*10 + x; dp[i][1] = 1; } #endif // dp[2][0]+dp[2][1]が答え cout << dp[digit-1][0]+dp[digit-1][1] << endl; return 0; }
これで計算はできますが、上のサイトのサンプルとは違うんですよね。dp[i-1][1]も使って計算しないといけないようですが、理由が完全に分からぬ。この辺の説明が書いてあるところが全然見つからない罠。なんでだ…
あと「未満フラグ」の呼び方とか真偽は解説サイトによって違うのですが、上のサイトの例に準拠してます。
ちなみに次に分かりやすかったのは次の２サイトさんかな。どちらも実装を掲載してくれてるのだけど、実装の説明が少ないので、どっちかというと桁DPの考え方が理解できた人が理解を深めるため向け？のような気がします。
桁DPの痒いところに手が届く解説 - Qiita
桁 DP の思想 〜 K 以下の整数を走査するとはどういうことか 〜 - けんちょんの競プロ精進記録
もうちょい理解進んだらまた続きの日記書きます。
