三井住友信託銀行プログラミングコンテスト2019の問題Dを100 x N程度の計算量で解く

解説のおまけ問題にもあるが，100 x N程度の計算量で解くようなコードを生成できた…と思う。

$\displaystyle{S}$ が仮に $\displaystyle{ 1067381902499 }$ というような数列だった場合，暗証番号の一桁目を全探索していくときに，2回目の $\displaystyle{ 1 }$ については見る必要がない。なぜなら，一回目の $\displaystyle{1}$ を一桁目とすると，暗証番号の二，三桁目の候補となるのは $\displaystyle{ 067381902499 }$ だが，二回目の $\displaystyle{1}$ を一桁目とすると，候補は $\displaystyle{ 902499 }$ となり，明らかに一回目の全探索は二回目の全探索を含むからである。すなわち，一桁目の全探索時に $\displaystyle{0}$ から $\displaystyle{9}$ までのbool型配列を作っておき，探索したことがある数字についてはフラグを立てて次は読み飛ばせば良い。この方針に従ってコードを書くと次のようになる：

#define _USE_MATH_DEFINES
#include "bits/stdc++.h"

using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
typedef long long ll;

int main() {
    int n;
    string s;
    cin >> n >> s;
    
    vector<bool> firstdigit(10, false);
    vector<bool> seconddigit(10, false);
    vector<bool> thirddigit(10, false);
    vector<int> int_s(n);
    int counter = 0;
    rep(i, n) {
        int_s.at(i) = (int)s.at(i) - (int)'0';
    }

    rep(i, n - 2) {
        if (firstdigit.at(int_s.at(i)) == false) {
            firstdigit.at(int_s.at(i)) = true;
            rep(j, 10) {
                seconddigit.at(j) = false;
            }
            for(int j = i+1; j < n - 1; j++) {
                if (seconddigit.at(int_s.at(j)) == false) {
                    seconddigit.at(int_s.at(j)) = true;
                    rep(k, 10) {
                        thirddigit.at(k) = false;
                    }
                    for(int k = j+1; k < n; k++) {
                        if (thirddigit.at(int_s.at(k)) == false) {
                            thirddigit.at(int_s.at(k)) = true;
                            counter++;
                        }
                    }
                }
            }
        }
    }

    cout << counter << endl;
}

3 x Nについてはわからんかった。