ログインしてください。
公式
K - 正しいチェックディジット / Correct Check Digit 解説
by
K - 正しいチェックディジット / Correct Check Digit 解説
by
physics0523
この問題は、以下のような DP を復元付きで行うことで解くことができます。
\(dp[i][j] = \) { \(i\) 桁目までを決めた時、ここまでの(問題文中の)値を \(10\) で割った余りが \(j\) であるようにすることができるか?}
\(dp[N][0]\) が偽であるとき、答えは No です。そうでない時、この \(dp\) の各要素について「どこから DP の遷移が来たか」というような情報を保持することで、最終的な文字列 \(S\) も復元することができます。
#include<bits/stdc++.h>
using namespace std;
using pi=pair<int,int>;
int main(){
int n;
string s;
cin >> n >> s;
vector<vector<pi>> dp(n+1,vector<pi>(10,{-1,-1}));
dp[0][0]={0,0};
for(int i=0;i<n;i++){
int ce=(i+1)%10;
for(int j=0;j<10;j++){
if(dp[i][j].first==-1){continue;}
for(char k='0';k<='9';k++){
if(s[i]=='?' || s[i]==k){
int aim=(j+ce*(k-'0'))%10;
dp[i+1][aim]={k-'0',j};
}
}
}
}
if(dp[n][0].first==-1){cout << "No\n";return 0;}
string res;
int p=n,q=0;
while(p>0){
res.push_back('0'+dp[p][q].first);
q=dp[p][q].second;
p--;
}
reverse(res.begin(),res.end());
cout << "Yes\n";
cout << res << "\n";
return 0;
}
投稿日時:
最終更新:
