ABC 403

Table of Contents

https://atcoder.jp/contests/abc403

A. Odd Position Sum

https://atcoder.jp/contests/abc403/tasks/abc403_a

B. Four Hidden

https://atcoder.jp/contests/abc403/tasks/abc403_b

C. 403 Forbidden

https://atcoder.jp/contests/abc403/tasks/abc403_c

D. Forbidden Difference

https://atcoder.jp/contests/abc403/tasks/abc403_d

index の情報は重要ではなく数の出現頻度が重要なのでまずはそれを調べる。

$D=0$ のとき

数 $x$ の頻度が $C_x$ のとき、$x$ を1つ残すのが最適なので削除する個数は $C_x - 1$ 個。これを出現する全ての数に対して足し合わせたものが答え。

$D>0$ のとき

$D$ 離れている数をグルーピングして DP を行う。

配列 $B$ に $x$ の出現頻度を格納する。

$dp_{i,j}$ を $j$ 番目の数を $i=1$ のときは削除する、$i=0$ のときは削除しないときの、$1~j$ までの数を削除した最小の個数とすると

\begin{align*} dp_{0,j} &= dp_{1,j-1} \\ dp_{1,j} &= \min(dp_{0,j-1}, dp_{1,j-1}) + B_{j} \end{align*}

となる。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, D;
    cin >> N >> D;
    vll A(N);
    rep(i, N) cin >> A[i];

    if (D == 0) {
        ll ans = 0;
        map<ll, ll> cnt;
        for (ll x : A)
            cnt[x]++;
        for (auto [k, v] : cnt) {
            ans += v - 1;
        }
        cout << ans << endl;
        return;
    }

    map<ll, ll> cnts;
    for (ll x : A)
        cnts[x]++;

    ll ans = 0;
    set<int> used;
    for (auto [k, v] : cnts) {
        if (used.count(k))
            continue;
        vll B = {v};
        used.insert(k);
        ll t = k;
        while (cnts.count(t + D)) {
            t += D;
            B.push_back(cnts[t]);
            used.insert(t);
        }

        // dp[i][j] : i 1 捨てる, 0 捨てない
        // j 個目の数に対して
        vvll dp(2, vll(B.size() + 1, INF));
        dp[0][0] = dp[1][0] = 0;
        rep2(i, 1, B.size() + 1) {
            dp[0][i] = dp[1][i - 1];                                // i 番目を採用する場合は i-1 番目は削除する必要がある
            dp[1][i] = min(dp[0][i - 1], dp[1][i - 1]) + B[i - 1];  // i 番目を削除する場合は i-1 番目は削除してもしなくてもどっちでもいい
        }
        ans += min(dp[0][B.size()], dp[1][B.size()]);
    }
    cout << ans << endl;
}

コンテスト中は出現しない数に対しては DP の対象にしなかったが、出現しない数も頻度が 0 として扱えば $\mod D$ 毎にグルーピングして DP するという風にできた

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, D;
    cin >> N >> D;
    vll A(N);
    rep(i, N) cin >> A[i];

    map<ll, ll> cnts;
    for (ll x : A)
        cnts[x]++;

    if (D == 0) {
        // 公式解説の方式
        cout << N - (ll)cnts.size() << endl;
        return;
    }

    ll mx = *max_element(all(A));
    auto cal = [&](ll mod) -> ll {
        vll B = {0};
        for (int i = mod; i <= mx; i += D) {
            B.push_back(cnts[i]);
        }

        int m = B.size();
        // dp[i][j]: j 番目の要素を捨てる(i=1)/捨てない(i=0)
        vvll dp(2, vll(m, INF));
        dp[0][0] = dp[1][0] = 0;

        rep2(i, 1, m) {
            dp[0][i] = dp[1][i - 1];
            dp[1][i] = min(dp[0][i - 1], dp[1][i - 1]) + B[i];
        }
        return min(dp[0][m - 1], dp[1][m - 1]);
    };

    ll ans = 0;
    rep(i, D) {
        ans += cal(i);
    }
    cout << ans << endl;
}

E. Forbidden Prefix

https://atcoder.jp/contests/abc403/tasks/abc403_e

解説 AC

// https://www.youtube.com/live/Ujaynq2mMW4?si=T0QDmJM-3b-YL5a8&t=7922
struct Trie {
    vector<map<char, int>> to;
    Trie()
        : to(1) {};

    int add(string s) {
        int v = 0;
        for (char c : s) {
            if (to[v].count(c) == 0) {
                int u = to.size();
                to.push_back(map<char, int>());
                to[v][c] = u;
            }
            v = to[v][c];
        }
        return v;
    }

    vector<bool> ng;
    vint ynode;
    int ynum;
    void init() {
        ng.resize(to.size(), false);
        ynum = 0;
        ynode.resize(to.size());
    }

    void addx(int x) {
        if (ng[x])
            return;
        ng[x] = true;
        if (ynode[x] > 0)
            ynum -= ynode[x];
        for (auto [k, v] : to[x]) {
            addx(v);
        }
    }
    void addy(int x) {
        if (ng[x])
            return;
        ynum++;
        ynode[x]++;
    }
};

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    cin >> q;
    Trie trie;

    vector<pair<int, int>> query;
    rep(i, q) {
        int t;
        string s;
        cin >> t >> s;
        int v = trie.add(s);
        query.push_back({t, v});
    }
    trie.init();

    for (auto [t, v] : query) {
        if (t == 1) {
            trie.addx(v);
        } else {
            trie.addy(v);
        }
        cout << trie.ynum << endl;
    }
}

F. Shortest One Formula

https://atcoder.jp/contests/abc403/tasks/abc403_f

解説 AC

長さが最小のものを採用すれば良いと思って提出して AC したが嘘解法だった。

https://atcoder.jp/contests/abc403/submissions/65294916

不正解になる $N$

144 = 11+11+11+111 (12 文字) = (11+1)*(11+1) (13 文字)

1584 = (11+1)*(11+1)*11
1585
1728
1739
1839
1950

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    int mx = 2005;
    vll exprsz(mx, INF), termsz(mx, INF);
    vector<string> expr(mx), term(mx);
    string ones = "1";
    rep(i, 4) {
        int one = stoi(ones);
        expr[one] = term[one] = ones;
        exprsz[one] = termsz[one] = i + 1;
        ones.push_back('1');
    }

    rep2(i, 2, N + 1) {
        rep2(j, 1, i) {
            string plus = expr[j] + "+" + expr[i - j];
            int plussz = plus.size();
            if (exprsz[i] > plussz) {
                exprsz[i] = plussz;
                expr[i] = plus;
            }
            if (termsz[i] >= plussz + 2) {
                termsz[i] = plussz + 2;
                term[i] = "(" + plus + ")";
            }

            if (j != 1 && i % j == 0) {
                string mul = term[i / j] + "*" + term[j];
                int mulsz = mul.size();
                if (exprsz[i] > mulsz) {
                    exprsz[i] = mulsz;
                    expr[i] = mul;
                }
                if (termsz[i] > mulsz) {
                    termsz[i] = mulsz;
                    term[i] = mul;
                }
            }
        }
    }

    cout << expr[N] << endl;
}