Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

C. Element Extermination (Codeforces Global Round 9)

Codeforces こどふぉ competitive programming c++

考察で迷走したあげく、ギャグ問であったことを知ったときの衝撃たるや・・・

問題

https://codeforces.com/contest/1375/problem/C

問題概要

長さnの順列が与えられる。あなたは順列中のa_i \lt a_{i+1}となるようなiについて、a_iとa_{i+1}のいずれかを除去することができる。

上記の操作を繰り返すことで、順列の長さを1にできるかどうか答えよ。

考察

最初、1より右とnより左は任意の一つが残せるとか、1とnの位置関係とかあまり実のないことを延々考えてしまいました。

落ち着いて、端から順に操作していくことを考えてみます。

a_1 \lt a_2のとき、いずれかを消すことができます。あとの処理を考えて、小さい方を残したほうが明らかに得なので、a_2を消してa_1を残します。

a_1 \gt a_2のとき、消すことができません。ここでさらに先に進んで、a_1 \lt a_{j} (j \lt 2)となるjが現れたときのことを考えます。

これは実はa_1のみを残して他をすべて消すことが可能です。a_j \gt a_1 \gt a_i (1 \lt i \lt j)が成り立ち、jの左に現れている数はすべてa_jより小さいからです。

このような操作を繰り返していくと、a_1より大きな数の右にa_1より小さな数があるときはそれが残ってしまうことがわかります。

結局、a_1 \lt a_nならば長さを1にできるし、a_1 \gt a_nならば少なくとも両端は残るため長さを1にできないということになります。

なお、a_nはいかなる操作によってもより大きな数に変換することができません。それができるのはa_nの右により大きな数があるときのみですが、そもそもa_nは一番右にあるからです。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int a, b;
        cin >> a;
        for (int i = 1; i < n; i++) cin >> b;
        cout << (a < b ? "YES" : "NO") << endl;
    }
}