制約的に $O(N^{2})$ でも通るが、スタックを用いて $O(N)$ でも解ける！

問題へのリンク（仮）

問題概要

$N$ マスからなるマス目があり、最初各マスには 0 が書かれている。このマス目に対して、以下の操作を行う。

正の整数値 $x$ と、連続するいくつかのマスを選ぶ（ただし、どのマスに書かれた数値も $x$ 以下でなければならない）
これらのマスに対して、その値が $x$ より小さいならば、 $x$ に書き換える

操作を繰り返すことにより、各マスの数値が $d_{1}, d_{2}, \dots, d_{N}$ となるようにしたい。これを実現するための操作回数の最小値を求めよ。

制約

$1 \le N \le 100$
$1 \le d_{i} \le 100$

考えたこと

基本的には、 $d_{1}, \dots, d_{N}$ の中に含まれる整数値のうち、小さい整数値から順に書き込んでいけばよいと考えた。その際に、すでに「より小さい整数値」が書き込まれているマスは飛ばさないといけないことに注意する。一方、「自分以上の整数値」が書き込まれているマスは一緒に塗ってしまうとしてよい。

たとえば、 $d = (20, 20, 10, 20, 30, 20)$ であれば、次のように 4 回の操作でできる。

操作「10 の部分」
- マス目全体に操作して、 $(10, 10, 10, 10, 10, 10)$ とする
操作「20 の部分」
- 10 の左側に操作して、 $(20, 20, 10, 10, 10, 10)$ とする
- 10 の右側に操作して、 $(20, 20, 10, 20, 20, 20)$ とする
操作「30 の部分」
- 5 番目の要素に操作して、 $(20, 20, 10, 20, 30, 20)$ とする

この方法が最小回数になることは次のように示せる。

$d_{1}, \dots, d_{N}$ に含まれる各整数値について、その整数値よりも小さいマス目でマス目全体を分割したときの、その整数値を含む連結成分の個数を考える。このとき、操作回数を、その個数の総和よりも小さくはできない
上記の方法は、この回数を実現できる。

高速化

上記の方法を愚直に実装すると $O(N^{2})$ の計算量となる。それでも十分通るが、スタックを用いると $O(N)$ の計算量の解法に高速化できる。

具体的には、 $i = 1, 2, \dots, N$ について、次のようにすればよい。回数を表す変数 res を用意して、0 で初期化しておく。

スタックから、 $d_{i}$ よりも大きいものは pop していく
その後、
- スタックの末尾の要素が $d_{i}$ に一致する場合は何もしない
- それ以外の場合は、スタックに $d_{i}$ を push して、res を 1 増やす

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> d(N);
    for (int i = 0; i < N; i++) cin >> d[i];

    int res = 0;
    vector<int> st;
    for (int i = 0; i < N; i++) {
        while (!st.empty() && st.back() > d[i]) st.pop_back();

        if (!st.empty() && st.back() == d[i]) continue;
        else {
            res++;
            st.push_back(d[i]);
        }
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 1455 Ribbon on the Christmas Present (ICPC アジア 2024 A)

問題概要

制約

考えたこと

高速化

コード