結果

問題 No.2934 Digit Sum
ユーザー GOTKAKO
提出日時 2024-10-13 16:29:25
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,582 bytes
コンパイル時間 2,282 ms
コンパイル使用メモリ 207,488 KB
最終ジャッジ日時 2025-02-24 19:17:02
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 24 WA * 1
権限があれば一括ダウンロードができます

ソースコード

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;
    if(N > 100000*9){cout << K << endl; return 0;}
    

    vector<vector<__int128_t>> dp(1000+1,vector<__int128_t>(171+1)),dp2 = dp;
    //1000C9->10^18以上,9*19.
    dp.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) += dp.at(i-1).at(l);
                    if(dp.at(i-1).at(l) == -1 || dp2.at(i).at(k) > K) dp2.at(i).at(k) = -1;
                }
                dp.at(i).at(k) += dp.at(i-1).at(l);
                if(dp.at(i-1).at(l) == -1 || dp.at(i).at(k) > K){dp.at(i).at(k) = -1; break;}
            }
        }
    }

    int n = 100000;
    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; 
                }
                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; break;}
            }
        }
    }

    for(int i=0; i<=1000; i++){
        for(int k=1; k<=171; k++){
            if(dp.at(i).at(k) == -1) continue; 
            dp.at(i).at(k) += dp.at(i).at(k-1);
            if(dp.at(i).at(k-1) == -1 || dp.at(i).at(k) > K) dp.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 = dp.at(i).at(left);
                if(next == -1){N -= k; answer += '0'+k; break;}
                if(next > K){
                    answer += '0'+k; N -= k;
                    break;
                }
                K -= dp.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