結果

問題 No.3157 Nabeatsu
コンテスト
ユーザー TKTYI
提出日時 2025-05-06 17:42:13
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 726 ms / 2,000 ms
コード長 2,039 bytes
コンパイル時間 3,734 ms
コンパイル使用メモリ 297,056 KB
実行使用メモリ 304,024 KB
最終ジャッジ日時 2025-05-06 17:42:31
合計ジャッジ時間 17,357 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

int main(){
    string N;
    cin >> N;
    int D = N.size();
    
    vector<vector<vector<int>>> DP(D + 1, vector<vector<int>>(2, vector<int>(3, -1)));
    vector<vector<vector<pair<int, int>>>> pre(D + 1, vector<vector<pair<int, int>>>(2, vector<pair<int, int>>(3)));
    DP[0][1][0] = 0;
    for(int i = 0; i < D; i++){
        for(int j = 0; j < 2; j++){
            for(int k = 0; k < 3; k++){
                if(DP[i][j][k] < 0) continue;
                for(int l = 0; l < 10; l++){
                    if(l == 3) continue;
                    if(j && N[i]-'0' < l) break;
                    int _j = j && (N[i] - '0' == l);
                    int _k = (k + l) % 3;
                    if(DP[i + 1][_j][_k] < 10 * DP[i][j][k] + l){
                        DP[i + 1][_j][_k] = 10 * DP[i][j][k] + l;
                        pre[i + 1][_j][_k] = make_pair(l, j);
                    }
                }
            }
        }
        vector<int> cmp;
        for(int j = 0; j < 2; j++){
            for(int k = 0; k < 3; k++){
                if(DP[i + 1][j][k] >= 0){
                    cmp.emplace_back(DP[i + 1][j][k]);
                }
            }
        }
        sort(cmp.begin(), cmp.end());
        cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end());
        for(int j = 0; j < 2; j++){
            for(int k = 0; k < 3; k++){
                if(DP[i + 1][j][k] >= 0){
                    DP[i + 1][j][k] = find(cmp.begin(), cmp.end(), DP[i + 1][j][k]) - cmp.begin();
                }
            }
        }
    }
    
    string ans;
    int j = 0, k = 1;

    for(int _j = 0; _j < 2; _j++){
        for(int _k = 1; _k < 3; _k++){
            if(DP[D][j][k] < DP[D][_j][_k]) j = _j, k = _k;
        }
    }
    for(int i = D - 1; i >= 0; i--){
        int l = pre[i + 1][j][k].first;
        ans += (char)('0' + l);
        j = pre[i + 1][j][k].second;
        k = (k + 12 - l) % 3;
    }
    reverse(ans.begin(), ans.end());
    cout << ans << endl;

    return 0;
}
0