ARC 120

Wed, May 28, 2025

A. Max Add

https://atcoder.jp/contests/arc120/tasks/arc120_a

自力 AC.

$i = 1, 2, \cdots, k$ の順に現在の $a$ の要素の最大値を $a_i$ に足すという操作を操作1と呼ぶことにする。また $g(a)$ を数列 $a$ に対して操作1を行った後の状態の数列とする。

$a_k = \{A_1, A_2, \cdots, A_k\}$ とし、$f(a_k)$ と $f(a_{k+1})$ との関係性を考える。

$m_k = \max a_k$ とし、$x_k = \max g(a_k)$ とする。

$A_{k+1} \leq m_k$ のとき、操作1の過程で $A_{k+1}$ は $i \in [1, k]$ 番目の操作に影響を及ぼさないため

\begin{align*} x_{k+1} &= x_k + A_{k+1} \\ f(a_{k+1}) &= f(a_k) + x_{k+1} \end{align*}

となる。

$A_{k+1} > m_k$ のとき、 $i = 1, 2, \cdots, k$ 番目の要素について $a_k$ に対して操作1を行ったときよりも $a_{k+1}$ に対して操作1を行ったときのほうが $A_{k+1} - m_k$ だけ大きくなる。また $k+1$ 番目の要素の数は $x_k + A_{k+1} + (A_{k+1} - m_k)$ になる。よって以下の式が成り立つ。

\begin{align*} x_{k+1} &= x_k + A_{k+1} + (A_{k+1} - m_k) \\ f(a_{k+1}) &= f(a_k) + k (A_{k+1} - m_k) + x_{k+1} \end{align*}

これを $k$ 小さい方から求めて行けばよい。

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

    int N;
    cin >> N;
    vll A(N + 1);
    rep(i, N) cin >> A[i + 1];

    vll f(N + 1), amx(N + 1), M(N + 1);
    rep2(i, 1, N + 1) {
        int k = i - 1;
        amx[i] = max(A[i], amx[k]);
        if (A[i] <= amx[k]) {
            M[i] = A[i] + M[k];
            f[i] = f[k] + M[i];
        } else {
            M[i] = A[i] + M[k] + (A[i] - amx[k]);
            f[i] = f[k] + (A[i] - amx[k]) * k + M[i];
        }
        cout << f[i] << endl;
    }
}

B. Uniformly Distributed

https://atcoder.jp/contests/arc120/tasks/arc120_b

スタートからの距離が等しいマスは同じ色で塗られている必要がある。例えばスタートから $(i,j)$ への移動は同じ、$(i+1, j+1)$ からゴールへの移動も同じだが $(i,j)$ から $(i+1, j+1)$ への移動は異なる場合を考える。移動の仕方としては $(i,j) \rightarrow (i+1,j) \rightarrow (i+1,j+1)$ と $(i,j) \rightarrow (i,j+1) \rightarrow (i+1,j+1)$ がある。

$(i+1, j)$ と $(i, j+1)$ のマスの色が異なる場合、経路に問わず赤の数が一定という条件に反してしまう。よって $(i+1, j)$ と $(i, j+1)$ のマスの色は同じである必要がある。

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

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

    vint red(H + W), blue(H + W), white(H + W);
    rep(i, H) rep(j, W) {
        if (grid[i][j] == 'R') red[i + j]++;
        if (grid[i][j] == 'B') blue[i + j]++;
        if (grid[i][j] == '.') white[i + j]++;
    }

    int ok = 1;
    rep(i, H + W) {
        if (red[i] > 0 && blue[i] > 0) {
            ok = 0;
            break;
        }

        if (red[i] > 0) white[i] = 0;
        if (blue[i] > 0) white[i] = 0;
    }

    if (!ok) {
        cout << 0 << endl;
        return;
    }

    mint two = 2;
    int cnt = 0;
    rep(i, H + W) {
        if (white[i] > 0) cnt++;
    }
    cout << two.pow(cnt).val() << endl;
}