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

AtCoder 貪欲法(Greedy)

問題概要

\(N\)桁のラッキーナンバーから\(N-3\)桁を消して残りの\(3\)桁を暗証番号として設定する。

このとき、暗証番号は何種類考えられるか？ただし、ラッキーナンバーや暗証番号はいずれも\(0\)から始まって良いものとする。

制約

  • \(4\ \leq \ N\ \leq \ 30000\)
  • Sは半角数字からなる長さNの文字列

この問題のポイント

暗証番号になる数字は、高々 1000通りだけしかないことに気がつけるかどうか。

解説

作成される暗証番号は、000 ~ 999 までの1000通りしか存在しません。この範囲のある数字を\(n\)とすると、

  • 100の位・・・Sの左から探索する
  • 10の位・・・100の位で見つかった位置から探索する
  • 1の位・・・10の位で見つかった位置から探索する。

そして、各桁に対して見つからない場合は、次の数字にいくようにします。今回は、各桁の数字が見つかった場合を数え上げることで正解となります。

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
typedef long long ll;

int main() {
  int N; cin >> N;
  string S; cin >> S;
  int ans = 0;
  for(int i = 0; i < 1000; i++) {
    string s; s = "00" + to_string(i);
    s = s.substr(s.size() - 3);
    bool found = true;
    for(int j = 0; j < 3; j++) {
      int pos;
      if(j == 0) pos = S.find(s[j]);
      else pos = S.find(s[j], pos+1);
      if(pos == string::npos) {
        found = false;
        continue;
      }
    }
    if(found) ans++;
  }
  cout << ans << endl;
  return 0;
}