ABC 402

Sun, Apr 20, 2025

C - Dislike Foods

食材 $i$ を使用している料理の番号、料理 $j$ が使用している苦手な食材の数をそれぞれ保存しておく。食材 $B_i$ を克服したとき、料理 $j$ が食材 $B_i$ を使用していたら、料理 $j$ の苦手な食材の数を1減らす。苦手な食材の数が 0 になったら食べられる料理の個数を1増やす。これを繰り返す

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

    int N, M;
    cin >> N >> M;
    vvll A(M);
    rep(i, M) {
        int K;
        cin >> K;
        rep(j, K) {
            ll a;
            cin >> a;
            a--;
            A[i].push_back(a);
        }
    }

    vll B(N);
    rep(i, N) {
        cin >> B[i];
        B[i]--;
    }

    // shokuzai[i]: 食材 i を使っている料理の番号
    vvll shokuzai(N);
    rep(i, M) {
        for (ll a : A[i]) {
            shokuzai[a].push_back(i);
        }
    }

    // nums[i]: 料理 i に含まれる苦手な食材の数
    vll nums(M, 0);
    rep(i, M) nums[i] = A[i].size();

    ll ans = 0;
    for (ll b : B) {
        for (ll i : shokuzai[b]) {
            nums[i]--;
            if (nums[i] == 0)
                ans++;
        }
        cout << ans << endl;
    }
}

D - Line Crossing

AC したが、実験して多分これで通るんじゃないかなぁくらいののりで提出して AC した。

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

    ll N, M;
    cin >> N >> M;
    vector<pair<ll, ll>> lines(M);
    rep(i, M) {
        ll a, b;
        cin >> a >> b;
        a--, b--;
        lines[i] = {a, b};
    }

    // 線が重なることはない
    // 平行になっているものをグループ分け

    vll grp(N);
    rep(i, M) {
        auto [a, b] = lines[i];
        ll d = N - a;
        b = (N + (b - d)) % N;
        grp[b]++;
    }

    fenwick_tree<ll> fw(N);
    rep(i, N) {
        fw.add(i, grp[i]);
    }

    ll ans = 0;
    rep(i, N - 1) {
        ans += fw.sum(i, i + 1) * fw.sum(i + 1, N);
    }
    cout << ans << endl;
}

F - Path to Integer

解説 AC

マス $(i, j)$ の値 ($i, j$ は 0-index とする)の余りへの寄与分は $A_{i,j} \times 10^{2N-2-i-j} \mod M$ である。マスを移動する毎に $A_{i,j} \times 10^{2N-2-i-j} \mod M$ の値を加算して mod を取るほうが楽なので予め $A_{i,j}$ を $A_{i,j} \times 10^{2N-2-i-j} \mod M$ に置き換えておく。

マス $(0,0)$ から $N-1$ 回の移動でたどり着くマスは下に移動する回数を $k$ 回とすると $(k,N-1-k)$ である。 $(0,0)$ から $(k,N-1-k)$ までの移動により得られる値の集合を $g1_k$ とする。同様に $(N-1,N-1)$ から $(k,N-1-k)$ までの移動により得られる値の集合を $g2_k$ とする。ただし、このとき $A_{k,N-1-k}$ 分の値は加算しない。(なぜなら $g1$ の方ですでに加算されているから。)

$(k,N-1-k)$ を経由するような移動をしたときに得られる値の最大値は $\max_{x \in g1_k,~ y \in g2_k} (x+y \mod M)$ である。 $x$ を固定すると $g2_k$ の中から $M-x$ 未満の数字の最大値を選んだとき最大になる。そのような数字がないときは $g2_k$ の最大値を選ぶ。($M-x$ 未満の数字を選べるときどの数字を選んでも $M$ を超えることはないので $x \leq x+y < M$ となる。一方 $M-x$ 以上の数字を選ぶとき、$M$ を超えるので $0 \leq x+y < x$ となる。)

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

    ll N, M;
    cin >> N >> M;

    using mint = modint;
    mint::set_mod(M);

    vector<vector<mint>> A(N, vector<mint>(N));
    rep(i, N) rep(j, N) {
        ll a;
        cin >> a;
        A[i][j] = a;
    }

    vector<mint> tenth(50);
    mint ten = 10;
    rep(i, 50) {
        tenth[i] = ten.pow(i);
    }

    rep(i, N) rep(j, N) {
        A[i][j] *= tenth[2 * N - 2 - (i + j)];
    }

    vvll g1(N), g2(N);
    rep(i, 1 << (N - 1)) {
        mint sum = 0;
        int x = 0, y = 0;
        rep(j, N - 1) {
            sum += A[x][y];
            if ((i >> j) & 1)
                x++;
            else
                y++;
        }
        sum += A[x][y];
        g1[x].push_back(sum.val());
    }
    rep(i, 1 << (N - 1)) {
        mint sum = 0;
        int x = N - 1, y = N - 1;
        rep(j, N - 1) {
            sum += A[x][y];
            if ((i >> j) & 1)
                x--;
            else
                y--;
        }
        g2[x].push_back(sum.val());
    }

    for (auto& v : g2)
        sort(all(v));

    ll ans = 0;
    rep(i, N) {
        for (ll x : g1[i]) {
            auto it = lower_bound(all(g2[i]), M - x);
            if (it != g2[i].begin())
                it = prev(it);
            else
                it = prev(g2[i].end());
            chmax(ans, (x + *it) % M);
        }
    }
    cout << ans << endl;
}

ABC 402

Table of Contents

C - Dislike Foods

D - Line Crossing

F - Path to Integer