ABC 405

Sun, May 11, 2025

D - Escape Route

まず複数ある非常口から通路マスへの距離の最短を求める。マス $(i,j)$ から隣のマスへの距離が -1 のとき、その方向に進む記号を記録して出力する。

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

    ll H, W;
    cin >> H >> W;
    vector<string> grid(H);
    rep(i, H) cin >> grid[i];

    int si = 0, sj = 0;
    vector<pair<int, int>> exits;
    rep(i, H) rep(j, W) {
        if (grid[i][j] == 'E')
            exits.push_back({i, j});
    }

    // i,j, cost
    vvll dist(H, vll(W, INF));
    deque<tuple<ll, ll, ll>> deq;
    for (auto [i, j] : exits) {
        deq.push_back({i, j, 0});
        dist[i][j] = 0;
    }

    vll di = {0, 1, 0, -1};
    vll dj = {1, 0, -1, 0};
    while (deq.size()) {
        auto [nowi, nowj, cost] = deq.front();
        deq.pop_front();

        if (dist[nowi][nowj] < cost)
            continue;

        rep(dir, 4) {
            ll ni = nowi + di[dir], nj = nowj + dj[dir];
            if (clamp(ni, 0ll, H - 1) != ni || clamp(nj, 0ll, W - 1) != nj)
                continue;
            if (grid[ni][nj] == '#')
                continue;
            if (dist[ni][nj] <= cost + 1)
                continue;
            dist[ni][nj] = cost + 1;
            deq.push_back({ni, nj, dist[ni][nj]});
        }
    }

    vector<char> dir_mark = {'>', 'v', '<', '^'};

    vector<string> ans = grid;

    rep(i, H) {
        rep(j, W) {
            if (grid[i][j] == '#' || grid[i][j] == 'E')
                continue;
            rep(dir, 4) {
                ll ni = i + di[dir], nj = j + dj[dir];
                if (clamp(ni, 0ll, H - 1) != ni || clamp(nj, 0ll, W - 1) != nj)
                    continue;
                if (dist[i][j] == dist[ni][nj] + 1) {
                    ans[i][j] = dir_mark[dir];
                }
            }
        }
    }

    for (auto s : ans)
        cout << s << endl;
}

E - Fruit Lineup

解説 AC

無駄に難しく考えてしまって TLE コードを書いてしまった。

TLE 方針

$\mathrm{comb}(n,r) = \frac{n!}{(n-r)!r!}$ とする。

一番右端のリンゴの位置を $k$ とするとリンゴより左に来るのはオレンジだけだから $A \leq k \leq A+B$ の範囲で $k$ は動かせる。 $k$ を固定したとき、$k$ より左側には $A-1$ 個のリンゴと $k-A$ 個のオレンジがある。これら $k-1$ 個の並べ方は $\mathrm{comb}(k-1, A-1)$ 通りである。

$k$ より右側ではまずオレンジとブドウをこの順に並べた後($B-(k-A) + D$ 個並んでいる)、両端と間の $B-(k-A)+D+1$ 箇所から $m$ 箇所を選んでバナナを1個以上挿入すると考えた。 $m$ を固定したとき $C$ 個を $m$ 分割する方法は $\mathrm{comb}(C-1){m-1}$ 通りである。($C$ 個のバナナを並べたときの隙間 $C-1$ からどこで区切るかの $m-1$ 個通りの組み合わせ)

以上をまとめると右側の並べ方は

\begin{align*} \sum_{k=A}^{A+B} \left\{ \mathrm{comb}(k-1, A-1) \cdot \left( \sum_{m=1}^{C} \mathrm{comb}(B-(k-A)+D+1, m) \cdot \mathrm{comb}(C-1, m-1) \right) \right\} \end{align*}

これだと最大で $O(10^{12})$ くらいかかるので TLE する。

想定解法

オレンジ、バナナ、ブドウの並べ方のところをより効率化できる。 $B-(k-A)+C+D$ 箇所からバナナを配置する $C$ 箇所を選び、残りの場所にはオレンジ・ブドウの順に並べればよい。

これだとループが一つになるので $O(A+B)$ で済む。

\begin{align*} \sum_{k=A}^{A+B} \mathrm{comb}(k-1, A-1) \cdot \mathrm{comb}(B-(k-A)+C+D, C) \end{align*}

公式解説ではブドウ基準に解いている。

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

    ll A, B, C, D;
    cin >> A >> B >> C >> D;

    ll tot = A + B + C + D;

    vector<mint> fac(tot + 1), invfac(tot + 1);
    fac[0] = invfac[0] = 1;
    rep2(i, 1, tot + 1) {
        fac[i] = fac[i - 1] * i;
    }
    rep2(i, 1, tot + 1) {
        invfac[i] = fac[i].inv();
    }

    auto comb = [&](ll n, ll r) -> mint {
        return fac[n] * invfac[n - r] * invfac[r];
    };

    mint ans = 0;
    for (ll k = A; k <= A + B; k++) {
        ll left_orange = k - A;
        ll right_orange = B - left_orange;
        ans += comb(k - 1, A - 1) * comb(right_orange + C + D, C);
    }
    // rep(k, C + 1) {
    //     ans += comb(A + B + k, B) * comb(D - 1 + C - k, C - k);
    // }
    cout << ans.val() << endl;
}

F - Chord Crossing