AtCoder Beginner Contest 268（ABC268）

atcoder.jp

Bondo416さんのユニークビジョンプログラミングコンテスト2022 夏(AtCoder Beginner Contest 268)での成績：1012位
パフォーマンス：1447相当
レーティング：1525→1518 (-7) :(#AtCoder #ユニークビジョンプログラミングコンテスト2022夏(ABC268) https://t.co/gt14QNjcFp

— ボンド@競プロ (@bond_cmprog) September 10, 2022

A - Five Integers

setで個数を数える

提出コード

void solve() {
    set<int> st;
    REP(i, 5) {
        int x;
        cin >> x;
        st.insert(x);
    }
    cout << st.size() << endl;
}

B - Prefix?

$ |S| \leq |T| $ のときに、SがTの先頭 $ |S| $ 文字と一致するかを判定

提出コード

void solve() {
    string S, T;
    cin >> S >> T;
    if (S.size() > T.size()) {
        cout << "No" << endl;
        return;
    }
    REP(i, S.size()) {
        if (S[i] != T[i]) {
            cout << "No" << endl;
            return;
        }
    }
    cout << "Yes" << endl;
}

C - Chinese Restaurant

人 $ i $ が満足するかどうかを何回操作を行ったときに満足するか、をmapで管理しその最大値を出力

提出コード

void solve() {
    int N;
    cin >> N;
    vector<int> p(N);
    vector<int> idx(N);
    REP(i, N) {
        cin >> p[i];
        idx[p[i]] = i;
    }
    map<int, set<int>> mp;
    REP(i, N) {
        for (int j = -1; j <= 1; j++) {
            int nxt = (i + j + N) % N;
            mp[(i - idx[nxt] + N) % N].insert(i);
        }
    }
    int ans = 0;
    for (auto [k, v] : mp) {
        chmax(ans, (int)v.size());
    }
    cout << ans << endl;
}

D - Unique Username

$ S $ の並べ方をnext_permutationで全探索をする
_をどこにいれるかは、$ N - 1 $ 箇所についてそれぞれ何個使うかを全通り試す

提出コード

void solve() {
    int N, M;
    cin >> N >> M;
    vector<string> S(N);
    int sz = 0;
    set<string> T;
    REP(i, N) {
        cin >> S[i];
        sz += S[i].size();
    }
    REP(i, M) {
        string s;
        cin >> s;
        T.insert(s);
    }
    vector<int> idx(N);
    iota(ALL(idx), 0);
    string ans = "-1";
    auto dfs = [&](auto &&self, string s, int n, int res) -> void {
        bool ok = false;
        s += S[idx[n]];
        if (n == N - 1) {
            if (T.count(s) == 0 and s.size() >= 3) {
                ans = s;
                return;
            }
            else return;
        }
        if (n <= N - 2 and res <= 0) return;

        for (int i = 1; i <= res; i++) {
            string next_s = s;
            next_s += string(i, '_');
            self(self, next_s, n + 1, res - i);
        }
    };
    do {
        string s = "";
        dfs(dfs, s, 0, 16 - sz);
    } while (next_permutation(ALL(idx)));
    cout << ans << endl;
}