予鈴

アウトプットとメモ書きの中間みたいな記事がたくさん出ます。

C. Element Extermination

Problem

Problem - C - Codeforces

I could not solve problem A, so I have no rating change in this contest :(
You are given an array of permutation of $N$ .
You can perform the following operation any number of time :
choose two-element such that $a_i < a_j , i < j$ , and remove $a_j$ or $a_i$ .
if you can make array length 1, print "YES".

Solution

単調増加部分列であれば、任意の要素を残すことができる。
例えば、 [4 5 6 7 ] → [4 5 7] → [4,7 ]→[7]みたいにな感じ。

与えられた数列を単調増加列に分ける。 $b_i$ を連続増加列として、 $b_1,b_2,...., b_m$ とする。
さて、右から左に向かって数列をマージ(?)していくことを考える。
$b_i ,b_{i+1}$ に操作を適用する。このとき、 $min(b_i) < max(b_{i+1})$ が成り立てば、操作を適用することで $b_i ,b_{i+1}$ を $min(b_i)$ とすることができる。
さらに、明らかに $min(b_0) = a_0, max(b_m)=a_{N - 1}$ であることから、これらを考えると条件は $a_0 < a_{N-1}$ のときYes.

#include<bits/stdc++.h>
using namespace std;
inline int  solve(){
    int N; cin >> N;
    vector<int>A(N); for(auto& e : A) cin >> e;
    cout << (A.front() < A.back() ? "YES"  : "NO") << endl;
    return 0;
}
signed main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int Q = 1; cin >> Q;
    while(Q--){solve();}
}