AtCoder Beginner Contest 145 F - Laminate

問題

 H_{i}のいずれとも異なる高さに変更する意味はないので、 a_{i}:=i番目に小さい列の高さとおき、 a_{i}に高さを変更する場合を考える。 左端から塗っていくことを考えると、新たに塗り直さなければならない回数は最も右側の列の高さから求められるので、以下のようなdpを考えられる。

 dp_{i,j,k} := i列目まで見たとき、このうちj個の高さを変更したとき、i列目の高さがa_{k}であるときの最小コスト

遷移式は、 a_{k} = h_{i-1} のとき、

 dp_{i,j,k} =  min(x, min_{l=0}^{H}\{ dp_{i-1,j,l}+max(0, k-l)\})

となり、そうでないとき、

 dp_{i,j,k}=x

となる。ただし、 x= min_{l=0}^H \{dp_{i-1,j-1,l} + max(0, k-l) \}である。

これをそのまま計算すると O(N^{4})となってしまうので工夫する必要がある。

まず、a_{k}=h_{i-1}となるのは各(i,j)に対して一度だけなので、min_{l=0}^{H}\{ dp_{i-1,j,l}+max(0, k-l)\}はそのままでもよく、各(i,j,k)に対してxO(1)で求めることを考えれば良い。

 max(0, k-l)の項に注目すると、


x=min(a_{k}+min_{l=0}^{k}\{dp_{i-1,j-1,l}-a_{l}\}, min_{l=k}^{H}\{dp_{i-1,j-1,l}\})

と変形することができる。ここで、

 b_{i,j,k} = min_{l=0}^{k}\{dp_{i-1,j-1,l}-a_{l}\}

 c_{i,j,k} = min_{l=k}^{H}\{dp_{i-1,j-1,l}\}

と定義すると、各 k=0,...,Hについて b_{i-1,j-1,k} c_{i-1,j-1,k}を予め求めておくことで、 dp_{i,j,k}O(1)で更新できる。

...

using namespace std;

#define rep(i, n) for (int64_t i = 0; i < (n); i++)
#define irep(i, n) for (int64_t i = 0; i <= (n); i++)
#define rrep(i, n) for (int64_t i = (n)-1; i >= 0; i--)
#define rirep(i, n) for (int64_t i = n; i >= 0; i--)

int main()
{
    int n, k;
    cin >> n >> k;

    vector<int> h(n);
    rep(i, n)
    {
        cin >> h[i];
    }

    vector<int> a(n);
    copy(h.begin(), h.end(), a.begin());
    a.push_back(0);
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());

    const int64_t M = 1'000'000'000L * n;
    vector<vector<vector<int64_t>>> dp(n + 1, vector<vector<int64_t>>(k + 1, vector<int64_t>(a.size())));
    irep(i, n) irep(j, k)
    {
        if (i == 0) {
            rep(l, a.size())
            {
                dp[i][j][l] = j == 0 && l == 0 ? 0 : M;
            }
        } else {
            rep(l, a.size())
            {
                dp[i][j][l] = M;
                if (a[l] == h[i - 1]) {
                    rep(l2, a.size())
                    {
                        dp[i][j][l] = min(dp[i][j][l], dp[i - 1][j][l2] + max(0L, (int64_t)a[l] - a[l2]));
                    }
                }
            }
            if (j > 0) {
                int64_t x = M;
                rep(l, a.size())
                {
                    x = min(x, dp[i - 1][j - 1][l] - a[l]);
                    dp[i][j][l] = min(dp[i][j][l], x + a[l]);
                }

                int64_t y = M;
                rrep(l, a.size())
                {
                    y = min(y, dp[i - 1][j - 1][l]);
                    dp[i][j][l] = min(dp[i][j][l], y);
                }
            }
        }
    }

    int64_t result = M;
    irep(j, k) rep(l, a.size())
    {
        result = min(result, dp[n][j][l]);
    }
    cout << result << endl;

    return 0;
}

遷移式にmax/minが含まれているときは、場合分けすることで式から遷移先の添字を消去することができる場合がある。式に遷移先の添字が含まれていないならば、複数の遷移先で計算結果を共有できる。

第2回全国統一プログラミング王決定戦予選 C - Swaps

問題

任意の置換は巡回置換の積に分解できる。また、n要素の巡回置換は、n-1個の互換の積に分解できる。したがって、ある置換がn-2個の互換で表せる⇔2つ以上の巡回置換の積に分解できる。

ここで、\{A_{i}\}を昇順にソートするような置換pを考える。pが2個以上の巡回置換の積に分解できるなら明らかにYES。

pが2個以上の巡回置換に分解できないならば、pはn要素の巡回置換である。ここで、 b_{i} \ge a_{i+1}となるiが存在するなら、置換(p_{1}, ... , p_{i+1}, p_{i}, ... p_{N})は条件を満たす。 なぜなら、(p_{1}, ... , p_{i+1}, p_{i}, ... p_{N}) = p(p_{i}, p_{i+1})であり、pp(p_{i}, p_{i+1})は偶奇が異なるが、n要素の置換は高々n-1個の互換に分解できるので、p(p_{i}, p_{i+1})はn-1個より少ない数の互換の積で表せるはずだからである。一方、 b_{i} \ge a_{i+1}となるiが存在しないなら、 b_{i} \ge a_{i} を満たすような置換はpのみである。

pがいくつの巡回置換に分解できるかはUnion-Find木を用いて求めることができる。

...

#define rep(i, n) for (int64_t i = 0; i < (n); i++)

class UFTree{ //Union-Find木
    ...
};

int main()
{
    int n;
    cin >> n;

    using P = tuple<int, int>;
    vector<int> a(n), b(n);
    vector<P> p(n);
    rep(i, n)
    {
        cin >> a[i];
    }
    rep(i, n)
    {
        cin >> b[i];
    }

    rep(i, n)
    {
        p[i] = P(b[i], a[i]);
    }
    sort(p.begin(), p.end());

    vector<P> q(n);
    rep(i, n)
    {
        int c;
        tie(ignore, c) = p[i];
        q[i] = P(c, i);
    }

    sort(q.begin(), q.end());

    rep(i, n)
    {
        int c, d;
        tie(c, ignore) = q[i];
        tie(d, ignore) = p[i];
        if (d < c) {
            cout << "No" << endl;
            return 0;
        }
    }

    UFTree uft(n);
    rep(i, n)
    {
        int j;
        tie(ignore, j) = q[i];
        uft.merge(i, j);
    }

    int cnt = 0;
    vector<bool> isCounted(n, false);
    rep(i, n)
    {
        if (!isCounted[uft.root(i)]) {
            cnt++;
            isCounted[uft.root(i)] = true;
        }
    }

    if (cnt > 1) {
        cout << "Yes" << endl;
    } else {
        rep(i, n - 1)
        {
            int a, b;
            tie(b, ignore) = p[i];
            tie(a, ignore) = q[i + 1];
            if (b >= a) {
                cout << "Yes" << endl;
                return 0;
            }
        }
        cout << "No" << endl;
    }

    return 0;
}

コンテスト中は何故か場合分けする発想がなくて解けなかった。