公式

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;
}

投稿日時:
最終更新: