結果

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

ソースコード

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