続きです。取り合えず、3を数えるプログラムは出来ましたが、ABC154-Eはもう少し応用が必要そうでまだ解けてません。取り合えず、3を数える方だけ載せておきます。100までは参考サイト様と出力が一致することを確認済みです。
その２とか言ってますが次が最終回（＝ABC154-EのAC）にしたい。
#include <iostream> #include <string> #include <string.h> using namespace std; int foo(std::string n) { // 該当する数字の数を格納する配列 // 桁数×未満フラグ（該当桁がn未満なら0、nなら1）×3が付くかのフラグ const int digit = n.size(); int dp[digit][2][2]; memset(dp, 0, sizeof(int)*digit*2*2); int x0 = n[0] - '0'; if(x0 < 3){ dp[0][0][0] = x0; // 0～(x0-1)までのx0個 dp[0][0][1] = 0; // x0が3未満なので0個 dp[0][1][0] = 1; // x0が3未満なので1個 dp[0][1][1] = 0; // x0が3未満なので0個 }else if(x0 == 3){ dp[0][0][0] = x0; // 0～(x0-1)までのx0個 dp[0][0][1] = 0; // x0が3だが、3未満でないので0個 dp[0][1][0] = 0; // x0が3なので0個 dp[0][1][1] = 1; // x0が3なので1個 }else if(x0 > 3){ dp[0][0][0] = x0-1; // 0～(x0-1)までのx0個から3を引いた(x0-1)個 dp[0][0][1] = 1; // x0が3より大きいので3の1個 dp[0][1][0] = 1; // x0が3より大きいのでx0の1個 dp[0][1][1] = 0; // x0が3ではないので0個 } //printf("%d %d %d %d\n", dp[0][0][0], dp[0][0][1], dp[0][1][0], dp[0][1][1]); for(int i=1; i<digit; i++){ const int x = n[i] - '0'; if(x < 3){ dp[i][0][0] = dp[i-1][0][0]*(10-1) + dp[i-1][0][1]*0 + dp[i-1][1][0]*x; dp[i][0][1] = dp[i-1][0][0]*1 + dp[i-1][0][1]*10 + dp[i-1][1][1]*x; dp[i][1][0] = dp[i-1][1][0]*1 + dp[i-1][1][1]*0; dp[i][1][1] = dp[i-1][1][0]*0 + dp[i-1][1][1]*1; }else if(x == 3){ dp[i][0][0] = dp[i-1][0][0]*(10-1) + dp[i-1][0][1]*0 + dp[i-1][1][0]*x; dp[i][0][1] = dp[i-1][0][0]*1 + dp[i-1][0][1]*10 + dp[i-1][1][1]*x; dp[i][1][0] = 0; dp[i][1][1] = 1; }else if(x > 3){ dp[i][0][0] = dp[i-1][0][0]*(10-1) + dp[i-1][0][1]*0 + dp[i-1][1][0]*(x-1); dp[i][0][1] = dp[i-1][0][0]*1 + dp[i-1][0][1]*10 + dp[i-1][1][0]*1 + dp[i-1][1][1]*x; dp[i][1][0] = dp[i-1][1][0]*1 + dp[i-1][1][1]*0; dp[i][1][1] = dp[i-1][1][0]*0 + dp[i-1][1][1]*1; } //printf("%d %d %d %d\n", dp[i][0][0], dp[i][0][1], dp[i][1][0], dp[i][1][1]); } //cout << dp[digit-1][0][1] + dp[digit-1][1][1] << endl; return dp[digit-1][0][1] + dp[digit-1][1][1]; } int main() { std::string n; cin >> n; cout << foo(n) << endl; return 0; }
