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

2019年12月2日

問題

方針

長さが \( N \) の文字列から \( 3 \) 文字取り出すことを考えると、計算量は \( {}_{N} \mathrm{ C }_{3}\) となってしまうので、別の方法を考えます。考えられる文字列は \( 1000 \) 通りなので、ある文字列が作成可能かどうかを調べます。ここで、各数字が何番目に出現したかというリストを作成し、全探索を行います。\( a(i, j) \) を数字 \( i \) が \( j \) 番目に出現した値とします。次の条件を満たす文字列 \(ijk\) は作成可能なので、\( i, j, k, l \) を全探索します。

\[a(i, 1) < a(j, l) < a(k, |a(k)|)\]

\( a(k, |a(k)|) \) は 数字 \( k\) が最後に出現した箇所です。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N;
    string S;
    cin >> N >> S;
    vector<int> a[10];
    for (int i = 0; i < N; i++) {
        int t = S[i] - '0';
        a[t].push_back(i);
    }
    int ans = 0;
    for (int i = 0; i < 10; i++) {
        if (a[i].size() == 0) continue;
        for (int j = 0; j < 10; j++) {
            if (a[j].size() == 0) continue;
            for (int k = 0; k < 10; k++) {
                if (a[k].size() == 0) continue;
                for (int l = 0; l < a[j].size(); l++) {
                    if (a[i][0] < a[j][l] && a[j][l] < a[k][a[k].size() - 1]) {
                        ans++;
                        break;
                    }
                }
            }
        }
    }
    cout << ans << "\n";
    return 0;
}