C++の練習を兼ねて, AtCoder Beginner Contest 154 の 問題E (E – Almost Everywhere Zero) を解いてみた(二回目).
■感想.
1. 前回いまいちな解き方していたので, 解説で, 桁DPを使うことを指摘されていたので, 解き直してみた.
2. 色々苦労したものの, 苦手な DP の訓練のため, 良い経験になったと思う.
※ dp0, dp1 で, どのような値が保存されるかのイメージが, 見えるまでに, 時間かかってしまった(汗).
3. 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトABC 154解説をご覧下さい.
■C++版プログラム(問題E/AC版).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 |
// ロジック, コメントを, 一部修正して, 再提出. // 桁DP使った実装. // 解き直し. // https://img.atcoder.jp/abc154/editorial.pdf #include <bits/stdc++.h> using namespace std; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) int dp0[111][4]; // 上からi桁目まで決めて, 0でない桁がj個あり, Nより小さいことが確定. int dp1[111][4]; // 上からi桁目まで決めて, 0でない桁がj個あり, Nより小さいことが未確定. int main(){ // 1. 入力情報. int K; char N[111]; scanf("%s %d", N, &K); int d = strlen(N); // 2. 解説通り. // 2-1. dp1更新. // ex. // 3500125 // 3 // => 以下のように設定したい. // dp1[0][1] = 1 // 1桁目が, '3'. // dp1[1][2] = 1 // 2桁目が, '5'. // dp1[2][2] = 1 // 3桁目が, '0'. // dp1[3][2] = 1 // 4桁目が, '0'. // dp1[4][3] = 1 // 5桁目が, '1'. // dp1[5][3] = 0 // 6桁目が, '2'. (※但し, dp1[5][4] = 1 を イメージしている) // dp1[6][3] = 0 // 7桁目が, '5'. (※但し, dp1[6][5] = 1 を イメージしている) int c = 1; dp1[0][c] = 1; // 1桁目を更新. repx(i, 1, d){ if(N[i] > '0') c++; if(c > K) break; // この条件が無いと, 上手く動作しないように見える. dp1[i][c] = 1; } // rep(i, d){ // rep(j, 4) printf("%d ", dp1[i][j]); // puts(""); // } // 2-2. dp0更新. // ex. // [入力例] // 3500125 // 3 // => 以下のように更新していく. // [1桁目] // dp0[0][0] = 1 // 1桁目が, '0'. (0XXXXXX のみ) // dp0[0][1] = 2 // 1桁目が, '1' ~ '2'. (1XXXXXX, 2XXXXXX のみ) // dp0[0][2] = 0 // 1桁目までで, '0' でない数字が, 2個出ることはありえない. // dp0[0][3] = 0 // 1桁目までで, '0' でない数字が, 3個出ることはありえない. // // [2桁目] // dp0[1][0] = 1 // 2桁目も, '0'. (00XXXXX のみ) // dp0[1][1] // = dp0[0][0] * 9 // 2桁目が, '0' 以外. (01XXXXX, 05XXXXX など) // + dp0[0][1] * 1 // 2桁目が, '0'. (10XXXXX, 20XXXXX のみ) // + dp1[0][0] * (N[1] > '1') * (N[1] - '1') // 2桁目が, '0' 以外. (今回は無し) // + dp1[0][1] * (N[1] > '0') // 2桁目が, '0'. (30XXXXX の形) // = 1 * 9 + 2 * 1 + 0 * 1 * 4 + 1 * 1 = 12通り. // dp0[1][2] // = dp0[0][1] * 9 // 2桁目が, '0' 以外. (21XXXXX, 15XXXXX など) // + dp0[0][2] * 1 // 2桁目が, '0'. (今回は無し) // + dp1[0][1] * (N[1] > '1') * (N[1] - '1') // 2桁目が, '1' ~ '4'. (31XXXXX, 34XXXXX など) // + dp1[0][2] * (N[1] > '0') // 2桁目が, '0'. (今回は無し) // = 2 * 9 + 0 * 1 + 1 * 1 * 4 + 0 * 1 = 22通り. // dp0[1][3] = 0 // 2桁目までで, '0' でない数字が, 3個出ることはありえない. // ※ 上記の結果から, 例えば, 以下の入力例は, dp0[1][2] + dp1[1][2] = 22 + 1 = 23通り と 計算できたりする. // [入力例] // 35 // 2 // // [3桁目] // dp0[2][0] = 1 // 3桁目も, '0'. (000XXXX のみ) // dp0[2][1] // = dp0[1][0] * 9 // 3桁目が, '0' 以外. (002XXXX, 005XXXX など) // + dp0[1][1] * 1 // 3桁目が, '0'. (100XXXX, 020XXXX など) // + dp1[1][0] * (N[2] > '1') * (N[2] - '1') // 3桁目が, '0' 以外. (今回は無し) // + dp1[1][1] * (N[2] > '0') // 3桁目が, '0'. (今回は無し) // = 1 * 9 + 12 * 1 + 0 * 0 * (-1) + 0 * 0 = 21通り. // dp0[2][2] // = dp0[1][1] * 9 // 3桁目が, '0' 以外. (209XXXX, 057XXXX など) // + dp0[1][2] * 1 // 3桁目が, '0'. (120XXXX, 280XXXX など) // + dp1[1][1] * (N[2] > '1') * (N[2] - '1') // 3桁目が, '0' 以外. (今回は無し) // + dp1[1][2] * (N[2] > '0') // 3桁目が, '0'. (今回は無し) // = 12 * 9 + 22 * 1 + 0 * 0 * (-1) + 1 * 0 = 130通り. // dp0[2][3] // = dp0[1][2] * 9 // 3桁目が, '0' 以外. (219XXXX, 176XXXX など) // + dp0[1][3] * 1 // 3桁目が, '0'. (今回は無し) // + dp1[1][2] * (N[2] > '1') * (N[2] - '1') // 3桁目が, '0' 以外. (今回は無し) // + dp1[1][3] * (N[2] > '0') // 3桁目が, '0'. (今回は無し) // = 22 * 9 + 0 * 1 + 1 * 0 * (-1) + 0 * 0 = 198通り. // ※ 上記の結果から, 例えば, 以下の入力例は, dp0[2][3] + dp1[2][3] = 198 + 0 = 198通り と 計算できたりする. // [入力例] // 350 // 3 // // ~(略)~ // // [7桁目] // dp0[6][0] = 1 // 7桁目も, '0'. (0000000 のみ) // dp0[6][1] // = dp0[5][0] * 9 // 7桁目が, '0' 以外. (0000001, 0000009 など) // + dp0[5][1] * 1 // 7桁目が, '0'. (1000000, 0000700 など) // + dp1[5][0] * (N[6] > '1') * (N[6] - '1') // 7桁目が, '0' 以外. (今回は無し) // + dp1[5][1] * (N[6] > '0') // 7桁目が, '0'. (今回は無し) // = 1 * 9 + 48 * 1 + 0 * 1 * 4 + 0 * 1 = 57通り. // dp0[6][2] // = dp0[5][1] * 9 // 7桁目が, '0' 以外. (0090001, 2000009 など) // + dp0[5][2] * 1 // 7桁目が, '0'. (1050000, 0007700 など) // + dp1[5][1] * (N[6] > '1') * (N[6] - '1') // 7桁目が, '0' 以外. (今回は無し) // + dp1[5][2] * (N[6] > '0') // 7桁目が, '0'. (今回は無し) // = 48 * 9 + 941 * 1 + 0 * 1 * 4 + 0 * 1 = 1373通り. // dp0[6][3] = 0 // = dp0[5][2] * 9 // 7桁目が, '0' 以外. (1007001, 2080009 など) // + dp0[5][3] * 1 // 7桁目が, '0'. (1060010, 2050900 など) // + dp1[5][2] * (N[6] > '1') * (N[6] - '1') // 7桁目が, '0' 以外. (今回は無し) // + dp1[5][3] * (N[6] > '0') // 7桁目が, '0'. (今回は無し) // = 941 * 9 + 9550 * 1 + 0 * 1 * 4 + 0 * 1 = 18019通り. // => 以上から, dp0[6][3] + dp1[6][3] = 18019 + 0 = 18019通り と 計算できた. // // 1桁目を更新. dp0[0][0] = 1; dp0[0][1] = N[0] - '1'; // 2桁目以降を更新. repx(i, 1, d) dp0[i][0] = 1; repx(i, 1, d){ repx(j, 1, 4){ // (i - 1)桁目までで, '0' でない桁が, (j - 1)個出現する形で, 確定している場合, // i桁目は, '1' ~ '9'(9通り) を取り得る(※). // ※もし, i桁目が, '0' の場合, i桁目までで, '0' でない桁が, j個とならないので矛盾. dp0[i][j] = dp0[i - 1][j - 1] * 9; // (i - 1)桁目までで, '0' でない桁が, j個出現する形で, 確定している場合, // i桁目は, '0'(1通り) のみ取り得る(※). // ※もし, i桁目が, '1' ~ '9' の場合, i桁目までで, '0' でない桁が, (j + 1)個となり矛盾. dp0[i][j] += dp0[i - 1][j] * 1; // i桁目が, '1' ~ '(N[i] - '1')' で 確定(※)するためには, (i - 1)桁目までで, // '0' でない桁が, (j - 1)個出現している必要がある. // ※もし, i桁目が, 'N[i]' の場合, N より小さいか確定していないので, 矛盾. // => N = 12 K = 2 として, 1桁目 を 1 を 確定させると, 最大 11, ... , 19 がカウントされ, 9個 となるが, // 実際は, 2通りなので, 誤った結果となる. dp0[i][j] += dp1[i - 1][j - 1] * (N[i] > '1') * (N[i] - '1'); // i桁目が, '0' (1通り) で 確定するためには, i桁目が, '0' より 大きい必要がある. // -> この1通りは, N[i] > '0' の 値で, 表現可能である. dp0[i][j] += dp1[i - 1][j] * (N[i] > '0'); } } // rep(i, d){ // rep(j, 4) printf("%d ", dp0[i][j]); // puts(""); // } // 3. 出力. printf("%d\n", dp0[d - 1][K] + dp1[d - 1][K]); return 0; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 |
[入力例] 100 1 [出力例] 19 ※AtCoderテストケースより [入力例] 25 2 [出力例] 14 ※AtCoderテストケースより [入力例] 314159 2 [出力例] 937 ※AtCoderテストケースより [入力例] 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999 3 [出力例] 117879300 ※AtCoderテストケースより [入力例] 1 2 [出力例] 0 [入力例] 100 3 [出力例] 0 [入力例] 1111 3 [出力例] 820 [入力例] 3500125 3 [出力例] 18019 [入力例] 123454321 3 [出力例] 42645 [入力例] 12345678987654321 1 [出力例] 145 [入力例] 12345678987654321 2 [出力例] 9857 [入力例] 12345678987654321 3 [出力例] 417009 [入力例] 100200300400500600700800900 3 [出力例] 1916283 [入力例] 3971059109076882976283276868823325568475235692362086997028948054557023320411225092214081379099432804 2 [出力例] 395604 [入力例] 3316624790355399849114932736670686683927088545589353597058682146116484642609043846708843399128290650 3 [出力例] 115516414 |
■参照サイト
AtCoder Beginner Contest 154