1604-B, *1100

Problem - B - Codeforces

문제

• 순열 $a_{1}a_{2}...a_{n}$이 주어진다
• 순열을 subarray 로 분할했을 때 각각의 subarray 에서의 LIS(longest increasing subsequence)를 $h_{i}$라 하자
• $h_{1}\oplus h_{2} \oplus ...\oplus h_{t} = 0$이 될 수 있게 순열을 분할할 수 있는가?

 

$O(n)$

i) n = 1 일때 ~ NO 

ii) n 이 짝수일때 ~ YES
순열을 크기가 1인 subarray로 나누면 1^1^...^1 = 0 (∵1이 짝수개)

iii) n 이 홀수일때
가. $a_{i+1}\leq a_{i}$인 항이 존재할 때 ~ YES
그 두 항을 묶어 하나의 subarray 로 두고 나머지 항들은 크기가 1인 subarray 로 분할한다
그러면 1^1^...^1 = 0 (∵1이 짝수개)

나. a 가 strictly increase ~ NO
$n = h_{1}+h_{2}+...+h_{t}$ --- ⓐ
$n = h_{1}\oplus h_{2} \oplus ... \oplus h_{t}$ --- ⓑ
인 분할이 존재한다고 가정하자

가장 낮은 비트(가장 오른쪽에 위치한 비트)를 관찰하자
ⓐ : n 이 홀수이므로 가장 낮은 비트에서 1은 홀수번 등장한다
ⓑ : 가장 낮은 비트에서 1은 짝수번 등장한다

ⓐ, ⓑ 는 모순이므로 위 조건을 만족하는 분할은 존재하지 않는다

※ 이부분은 실전에서는 논증하지 못했었다

c++

#include <bits/stdc++.h>
#define endl "\n"
#define ooop(i, n) for(int i = 0; i < n; i++)
#define loop(i, n) for(int i = 1; i <= n; i++)
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int t, n;
    cin >> t;
    while(t--){
        cin >> n;
        vector<int> v(n);
        for(auto& e: v) cin >> e;
        bool partial_decrease = false;
        loop(i, n-1){
            if(v[i] <= v[i-1]) partial_decrease = true;
        }
 
        if(partial_decrease or n%2 == 0) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
 
    return 0;
}cs

python 3

import sys
 
for _ in range(int(input())):
    n = int(input())
    l = list(map(int, sys.stdin.readline().split()))
    if n == 1: print("NO")
    elif n%2 == 0: print("YES")
    else:
        isStrictlyincreasing = True
        for i in range(n-1):
            if l[i] >= l[i+1]: isStrictlyincreasing = False
        print("NO" if isStrictlyincreasing else "YES")cs