結果

問題 No.2934 Digit Sum
ユーザー GOTKAKOGOTKAKO
提出日時 2024-10-13 16:36:45
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 109 ms / 2,000 ms
コード長 4,071 bytes
コンパイル時間 2,507 ms
コンパイル使用メモリ 214,288 KB
実行使用メモリ 48,000 KB
最終ジャッジ日時 2024-10-13 16:36:52
合計ジャッジ時間 6,232 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 85 ms
47,616 KB
testcase_01 AC 101 ms
47,744 KB
testcase_02 AC 85 ms
47,744 KB
testcase_03 AC 86 ms
47,744 KB
testcase_04 AC 88 ms
47,744 KB
testcase_05 AC 88 ms
47,744 KB
testcase_06 AC 87 ms
47,744 KB
testcase_07 AC 92 ms
47,744 KB
testcase_08 AC 89 ms
47,616 KB
testcase_09 AC 93 ms
47,872 KB
testcase_10 AC 109 ms
48,000 KB
testcase_11 AC 99 ms
47,744 KB
testcase_12 AC 96 ms
47,744 KB
testcase_13 AC 100 ms
47,616 KB
testcase_14 AC 99 ms
47,616 KB
testcase_15 AC 98 ms
47,744 KB
testcase_16 AC 99 ms
47,744 KB
testcase_17 AC 97 ms
47,616 KB
testcase_18 AC 96 ms
47,744 KB
testcase_19 AC 97 ms
47,744 KB
testcase_20 AC 99 ms
47,744 KB
testcase_21 AC 108 ms
47,744 KB
testcase_22 AC 98 ms
47,744 KB
testcase_23 AC 95 ms
47,616 KB
testcase_24 AC 97 ms
47,616 KB
testcase_25 AC 98 ms
47,616 KB
testcase_26 AC 97 ms
47,616 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    long long N,K; cin >> N >> K;

    vector<vector<__int128_t>> dp1(1000+1,vector<__int128_t>(171+1)),dp2 = dp1;
    //1000C9->10^18以上,9*19.
    //dp1,2->Nが大きい時にi桁で桁和j未満の数(先頭0を認めるかどうか).
    //dp3,4->Nが小さい時バージョン.
    dp1.at(0).at(0) = 1;
    for(int i=1; i<=1000; i++){
        for(int k=0; k<=171; k++){
            for(int l=max(k-9,0); l<=k; l++){
                if(l != k && dp2.at(i).at(k) != -1){
                    dp2.at(i).at(k) += dp1.at(i-1).at(l);
                    if(dp1.at(i-1).at(l) == -1 || dp2.at(i).at(k) > K) dp2.at(i).at(k) = -1;
                }
                if(dp1.at(i).at(k) != -1){
                    dp1.at(i).at(k) += dp1.at(i-1).at(l);
                    if(dp1.at(i-1).at(l) == -1 || dp1.at(i).at(k) > K) dp1.at(i).at(k) = -1;
                }
            }
        }
    }

    int n = 100010;
    vector<vector<__int128_t>> dp3(n+1,vector<__int128_t>(10)),dp4 = dp3;
    dp3.at(0).at(0) = 1;
    for(int i=1; i<=n; i++){
        for(int k=0; k<=9; k++){
            for(int l=max(k-9,0); l<=k; l++){
                if(l != k && dp4.at(i).at(k) != -1){
                    dp4.at(i).at(k) += dp3.at(i-1).at(l);
                    if(dp3.at(i-1).at(l) == -1 || dp4.at(i).at(k) > K) dp4.at(i).at(k) = -1; 
                }
                if(dp3.at(i).at(k) != -1){
                    dp3.at(i).at(k) += dp3.at(i-1).at(l);
                    if(dp3.at(i-1).at(l) == -1 || dp3.at(i).at(k) > K) dp3.at(i).at(k) = -1;
                }
            }
        }
    }

    for(int i=0; i<=1000; i++){
        for(int k=1; k<=171; k++){
            if(dp1.at(i).at(k) == -1) continue; 
            dp1.at(i).at(k) += dp1.at(i).at(k-1);
            if(dp1.at(i).at(k-1) == -1 || dp1.at(i).at(k) > K) dp1.at(i).at(k) = -1;
        }
    }
    for(int i=0; i<=1000; i++){
        for(int k=1; k<=171; k++){
            if(dp2.at(i).at(k) == -1) continue;
            dp2.at(i).at(k) += dp2.at(i).at(k-1);
            if(dp2.at(i).at(k-1) == -1 || dp2.at(i).at(k) > K) dp2.at(i).at(k) = -1;
        }
    }
    for(int i=0; i<=n; i++) for(int k=1; k<10; k++){
        if(dp3.at(i).at(k) == -1) continue;
        dp3.at(i).at(k) += dp3.at(i).at(k-1);
        if(dp3.at(i).at(k) > K || dp3.at(i).at(k-1) == -1) dp3.at(i).at(k) = -1;
    }
    for(int i=0; i<=n; i++) for(int k=1; k<10; k++){
        if(dp4.at(i).at(k) == -1) continue;
        dp4.at(i).at(k) += dp4.at(i).at(k-1);
        if(dp4.at(i).at(k) > K || dp4.at(i).at(k-1) == -1) dp4.at(i).at(k) = -1;
    }

    N = min(N,171LL);
    string answer = "";
    if(N < 10){
        int digit = 0;
        long long all = 0;
        for(int i=0; i<=n; i++){
            all += dp4.at(i).at(N);
            if(all > K || dp4.at(i).at(N) == -1){digit = i; break;}
        }
        for(int i=digit; i>=0; i--){
            int d = 0;
            for(int k=0; k<=N; k++){
                int left = N-k;
                __int128_t now = dp3.at(i).at(left);
                if(now > K || now == -1){N -= d; answer += '0'+d; break;}
                K -= now; d++;
            }
        }
    }
    else{
        int digit = 0;
        long long all = 0;
        for(int i=0; i<=1000; i++){
            all += dp2.at(i).at(N);
            if(all > K || dp2.at(i).at(N) == -1){digit = i; break;}
        }
        for(int i=digit; i>=0; i--){
            for(int k=0; k<=min(N,9LL); k++){
                int left = N-k;
                __int128_t next = dp1.at(i).at(left);
                if(next == -1){N -= k; answer += '0'+k; break;}
                if(next > K){
                    answer += '0'+k; N -= k;
                    break;
                }
                K -= dp1.at(i).at(left);
            }
        }
    }
    reverse(answer.begin(),answer.end());
    while(answer.back() == '0') answer.pop_back();
    reverse(answer.begin(),answer.end());
    cout << answer << endl;
}
0