ABC 391

Table of Contents

D - Gravity

https://atcoder.jp/contests/abc391/tasks/abc391_d

嘘解法で通してしまった。$x$ が同じ時ブロックではあとからのほうが $y$ が大きいとしてしまったがそんな制約はなかった。 $y$ に sort 入れなかったときにバグる入力例

4 2
1 2
1 1
2 1
2 2
2
1 2
1 3

解法

列 $x$ のあるブロックのうち下から $j$ 番目のブロックの $y$ 座標を $y_{x,j}$ とする。

$k$ 回目の行が消える操作は $t_k = \max \\{ y_{x,k} | x \in [1,W], x \in \mathbb{Z} \\}$ の時刻に実行される。 このような $y_{x,k}$ が存在しない場合は $t_k = \infty$ とする。

ブロック $i$ が 列 $X_i$ の下から k 番目のブロックであるとき、消えるのは時刻 $t_k$ のときである。 これらの情報からクエリの時刻においてブロック $i$ が存在しているかどうかを判定する。

void solve() {
    ll N, W;
    cin >> N >> W;

    vector<pair<ll, ll>> blocks(N);
    rep(i, N) {
        ll x, y;
        cin >> x >> y;
        x--;
        blocks[i] = {x, y};
    }

    int Q;
    cin >> Q;
    vector<pair<ll, ll>> queries(Q);
    rep(i, Q) {
        ll t, a;
        cin >> t >> a;
        a--;
        queries[i] = {t, a};
    }

    // lane[x][{y,id}]
    // x: column number
    // y: row number
    // id: block id
    vector<vector<pair<ll, ll>>> lane(W);
    rep(i, N) {
        auto [x, y] = blocks[i];
        lane[x].push_back({y, i});
    }
    for (auto& v : lane)  // y で sort する。コンテスト中のコードではこれを入れていなかった
        sort(all(v));

    // disappear_time[i]: i 回目の消える操作が行われる時刻
    vll disappear_time(3 * N, INF);
    ll min_cnt = INF;
    for (auto& v : lane)
        chmin(min_cnt, (ll)v.size());
    rep(j, min_cnt) {
        ll t = 0;
        rep(i, W) {
            chmax(t, lane[i][j].first);
        }
        disappear_time[j] = t;
    }

    // block_disappear_time[i]:
    // block i が消える時刻
    vll block_disappear_time(N, INF);
    for (auto& v : lane) {
        rep(i, v.size()) {
            auto [_, id] = v[i];
            block_disappear_time[id] = disappear_time[i];
        }
    }

    rep(i, Q) {
        auto [t, id] = queries[i];
        ll dt = block_disappear_time[id];
        yesno(t < dt);
    }
}

E - Hierarchical Majority Vote

https://atcoder.jp/contests/abc391/tasks/abc391_e

コンテスト終了20分後に自力 AC。

$dp(i,j,target)$ を $A$ の $[i,j)$ の範囲のに対して多数決の操作をした結果 $target$ にするのに必要な要素を変える回数の最小値とする。

(1) $j-i=3$ のとき

以下のコストが掛かる

A\target01
00002
00101
01001
10001
10110
11010
01110
11120

(2) $j-i > 3$ のとき

\begin{align} dp(i,j,0) &= \nonumber \min \nonumber \{& \\ &dp(a,b,0) + dp(b,c,0) + dp(c,d,0), \nonumber \\ &dp(a,b,0) + dp(b,c,0) + dp(c,d,1), \nonumber \\ &dp(a,b,0) + dp(b,c,1) + dp(c,d,0), \nonumber \\ &dp(a,b,1) + dp(b,c,0) + dp(c,d,0), \nonumber \\ \} \nonumber \end{align}

\begin{align} dp(i,j,1) &= \nonumber \min \nonumber \{& \\ &dp(a,b,1) + dp(b,c,0) + dp(c,d,1), \nonumber \\ &dp(a,b,1) + dp(b,c,1) + dp(c,d,0), \nonumber \\ &dp(a,b,0) + dp(b,c,1) + dp(c,d,1), \nonumber \\ &dp(a,b,1) + dp(b,c,1) + dp(c,d,1), \nonumber \\ \} \nonumber \end{align}

ここで $a = i, b = i + \frac{j-i}{3}, c = i + \frac{j-i}{3} \times 2, d = j$.

何も変えなかったときの $A_1^\prime = target$ はコストは 0 で、$A_1^\prime \neq target$ のコストは nonzero だから $\max \\{ dp(0,3^N, 0), dp(0,3^N,1) \\}$ が最終的な答え。

ll N;
string A;
vvint cand = {
    {0, 0, 0},
    {0, 0, 1},
    {0, 1, 0},
    {1, 0, 0},
};

map<tuple<ll, ll, ll>, ll> memo;

// [i,j) の範囲の数字を target にするのにかかるコストの最小値
ll dfs(ll i, ll j, int target) {
    if (j - i == 3) {
        vint cnt(2);
        rep2(k, i, j) {
            cnt[A[k] - '0']++;
        }
        if (cnt[target] >= 2)
            return 0;
        else
            return 2 - cnt[target];
    }

    if (memo.count({i, j, target}))
        return memo[{i, j, target}];

    ll ans = INF;
    ll sz = j - i;
    ll diff = sz / 3;
    ll a = i;
    ll b = i + diff;
    ll c = i + 2 * diff;
    // 領域を3分割して最終的に target になる4パターンを
    // 全て試しコストが一番低いものを採用する
    rep(d, 4) {
        ll x1 = dfs(a, b, abs(target - cand[d][0]));
        ll x2 = dfs(b, c, abs(target - cand[d][1]));
        ll x3 = dfs(c, j, abs(target - cand[d][2]));
        chmin(ans, x1 + x2 + x3);
    }
    return memo[{i, j, target}] = ans;
}

void solve() {
    cin >> N >> A;
    ll sz = A.size();

    // target が 0, 1 のどちらかは、何もしなくても達成できるので
    // コストが0になる。
    // コストが nonzero のほうが今回求めたい答え
    ll a = dfs(0, sz, 0);
    ll b = dfs(0, sz, 1);
    cout << max(a, b) << endl;
}