三井住友信託銀行プログラミングコンテスト2019 D-Lucky PIN

はじめに

精選100問をちゃんと埋めることにしました。
以前やりかけり，すでに解いた問題が混じってますが，改めてやってみます。

レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】 - Qiita

問題　精選６

N文字（N>=$)の数字からなる文字列Sから（N-3)文字を消してできる文字列の種類の数を求める問題です。

D - Lucky PIN

誤答

（N-3）文字を消して残る３文字からつくることができる３ケタの数字の種類を出力する問題と誤読しWAになりました。

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

int main(){
  int n;
  cin>>n;
  string S;
  cin>>S;
  map<int,int>mp;
  map<int,int>sp;
  for(int i=0;i<S.length();i++){
    mp[S.at(i)-'0']++;
  }
  int cnt=0;
  for(int k1=0;k1<10;k1++){
    for(int k2=0;k2<10;k2++){
      for(int k3=0;k3<10;k3++){
        for(int i=0;i<10;i++){
          sp[i]=mp[i];
        }
        sp[k1]--;
        sp[k2]--;
        sp[k3]--;
        if(sp[k1]>=0 && sp[k2]>=0 && sp[k3]>=0){
          cnt++;
        }
      }
    }
  }
  cout<<cnt<<endl;
  return 0;
}

正答

000から999までのすべてについてSから順序を維持したままとれるかを全探索していきます。

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

int main(){
  int n;
  cin>>n;
  string S;
  cin>>S;
  int cnt=0;
  for(int k1=0;k1<10;k1++){
    for(int k2=0;k2<10;k2++){
      for(int k3=0;k3<10;k3++){
        int flag=1;
        for(int i=0;i<n;i++){
          if(flag==1 && (S.at(i)-'0')==k1){
            flag=2;
            continue;
          }
          if(flag==2 && (S.at(i)-'0')==k2){
            flag=3;
            continue;
          }
          if(flag==3 && (S.at(i)-'0')==k3){
            flag=4;
            break;
          }
        }
        if(flag==4){
          cnt++;
        }
      }
    }
  }
  cout<<cnt<<endl;
  return 0;
}

>||