カラフル円盤通し [パソコン甲子園2020 予選 D]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0431

解説

https://onlinejudge.u-aizu.ac.jp/solutions/problem/0431/review/5787948/hamayanhamayan/C++14

問題で要求されている問題をさばいていこう。
要求されている事項をプログラムで計算できるようにもう少しアルゴリズムに寄せた感じで解釈していく。
「真上から見えない」という状況は与えられている半径で言うと、下に積まれている円盤の方が半径が小さい場合に成り立つ。
よって、円盤群を上から見下ろしたときに見えている円盤というのは、その円盤よりも上にあるどの円盤よりも
半径が大きい円盤であるものが見えていて、その条件を満たす枚数を数えていけばいい。

少し遅いがACできる回答

よって、各円盤についてその円盤よりも上にあるすべての円盤がその円盤の半径よりも小さいことを確かめて、
上から見えている円盤の数を数えていく解法があげられる。
これはN通りの円盤に対して、他の円盤、最大N-1枚を確認していくので、全体で大体N²回確認作業が発生するが、
Nの上限が1000であることを考えると間に合うので、これでも答えるためには問題ない。

今回実装した高速化した解法

自分が実装した解法は少し高速化をしている。
上から見えている円盤の条件を少し言い換えてみると、上から順番に円盤の最大値を取るような操作を行っているのが分かる。
例えば上から3 4 1 6 5 9となっていれば、

• 3はとりあえず使う
• 4はこれまでの最大値が3なので、使う
• 1はこれまでの最大値が4なので、見えてないので使わない
• 6がこれまでの最大値が4なので、使う
• 5はこれまでの最大値が6なので、見えてないので使わない
• 9はこれまでの最大値が6なので、使う

となり、4が答えとなる。
なので、これまでの最大値を持ちながら上から見ていけば、最大値が更新されたタイミングで答えもインクリメントしていけば
答えを導くことができる。
これならN回ループを書くだけで済むので、だいぶ計算が早くなる。

ちなみに…

入力は下から順の入力になっているが、ループの関係上、反転させて上から順の入力にしている。

int N, r[1010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> r[i];

    reverse(r, r + N);

    int ma = -1;
    int ans = 0;
    rep(i, 0, N) if (ma < r[i]) {
        ma = r[i];
        ans++;
    }

    cout << ans << endl;
}