1284-B, *1400

Problem - B - Codeforces

문제

• $n$개의 수열이 주어진다
• $a_{i} < a_{j}$인 $1\leq i < j \leq n$인 순서쌍 (i, j)가 존재하면 수열이 ascent 라고 한다
• 임의의 두 수열을 합쳐서 ascent 인 수열이 되는 경우의 수는?

 

$O(nlog\ n)$

ascent 인 수열에 임의의 순열을 더해도 ascent 이다
그러므로 먼저 n개의 수열을 ascent 인 것과 아닌 것으로 분류하자

수열 p, q에 대해 p+q 가 ascent 가 되는 경우를 고려하자.
ascent 인 수열의 개수를 k 개라고 하면
i) ascent 를 포함한 수열의 합이 ascent 가 되는 경우의 수
   가. p가 ascent, q가 non-ascent ~ k(n-k)
   나. p가 non-ascent, q가 ascent ~ (n-k)k
   다. p, q 모두 ascent ~ $k^{2}$

ii) ascent 를 포함하지 않은 수열의 합이 ascent 가 되는 경우의 수
non-ascent 수열의 최대값, 최소값을 저장한 배열을 최대값을 기준으로 오름차순으로 sort 한다
이제 각각의 수열이 p 라고 가정할 때, p+q 가 ascent 인 경우는
$$\mathrm{min\left \{ p \right \}<max\left \{ q \right \}}$$

인 경우이므로 이분탐색을 통해 q의 개수를 구할 수 있다.

예를들어 다음 예제를 생각해보자

10
3 62 24 39
1 17
1 99
1 60
1 64
1 30
2 79 29
2 20 73
2 85 37
1 100

 

최대값	17	30	60	64	79	85	99	100
최소값	17	30	60	64	29	37	99	100
q 개수	7	6	5	4	7	6	1	0

p 가 수열 {79, 29} 라고 가정하고 p+q가 ascent 인 q의 개수를 구하자
p의 최소값이 29 이므로 최대값이 29 보다 큰 모든 수열 구하여는 수열이므로 총 7개 존재한다

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;
 
ll n;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
    ll ascent_num = 0;
    vector<pii> non_ascent;
 
    loop(i, n){
        int s, first;
        cin >> s;
        cin >> first;
        if(s == 1) non_ascent.push_back({first, first});
        else{
            int max_val = first;
            int min_val = first;
            bool is_descent = true;
            int pre = first;
            int tmp;
            loop(j, s-1){
                cin >> tmp;
                if(pre < tmp) is_descent = false;
                if(min_val > tmp) min_val = tmp;
                if(max_val < tmp) max_val = tmp;
                pre = tmp;
            }
            if(is_descent) non_ascent.push_back({max_val, min_val});
            else ascent_num++;
        }
    }
 
    ll res = 0;
    if(ascent_num){
        res += 2*ascent_num*(n-ascent_num);
        res += ascent_num*ascent_num;
    }
 
    sort(non_ascent.begin(), non_ascent.end());
    ll non_cnt = n - ascent_num;
    for(auto [max, min]: non_ascent){
        int ind = (upper_bound(non_ascent.begin(), non_ascent.end(), pii(min, 0), [](const pii& me, const pii& parent){
            return me.first < parent.first;
        }) - non_ascent.begin());
        res += non_cnt - ind;
    }
 
    cout << res << endl;
 
    return 0;
}cs

python 3

import sys
from bisect import bisect_right
 
class keyWrapper:
    def __init__(self, iter, key):
        self.iter = iter
        self.key = key
 
    def __getitem__(self, ind):
        return self.key(self.iter[ind])
 
    def __len__(self):
        return len(self.iter)
 
n = int(input())
asc_num = 0
non_ascent = []
for _ in range(n):
    s, *l = list(map(int, sys.stdin.readline().split()))
    if s == 1: non_ascent.append((l[0], l[0]))
    else:
        isascent = False
        for i in range(s-1):
            if l[i] < l[i+1]:
                asc_num += 1
                isascent = True
                break
        if not isascent: non_ascent.append((max(l), min(l)))
 
res = 2 * asc_num * (n - asc_num) + asc_num * asc_num
non_ascent.sort()
for b, s in non_ascent:
    res += len(non_ascent) - bisect_right(keyWrapper(non_ascent, lambda x: x[0]), s)
print(res)cs

 

$O(nlog\ n)$

여사건을 이용하자

ascent 인 수열에 임의의 순열을 더해도 ascent 이다
따라서 non-ascent 의 결합이 non-ascent 인 경우의 수를 전체 경우의 수($n^{2}$)에서 빼주면 구하려는 값이다

한편 non-ascent 인 순열은 strictly decreasing 이다
따라서 non-ascent 인 순열 p, q의 결합이 non-ascent 이려면 p.last ≥ q.first 이면 된다

#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++)
#define all(v) (v).begin(), (v).end()
 
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);
 
    ll n;
    cin >> n;
    ll res = n*n;
    vector<pii> non_ascent;
    loop(i, n){
        int m; cin >> m;
        vector<ll> v(m);
        for(auto& e: v) cin >> e;
        if(is_sorted(v.rbegin(), v.rend())){
            non_ascent.emplace_back(v.front(), v.back());
        }
    }
 
    sort(all(non_ascent));
    for(auto& [first, last]: non_ascent){
        res -= upper_bound(all(non_ascent), pii(last, 1e6)) - non_ascent.begin();
    }
 
    cout << res << endl;
 
 
 
    return 0;
}cs

※ is_sorted 처음 사용해봄
※ 32번째 줄 pii(last, 0)이 아닌 pii(last, 최대 입력값) 을 사용하므로써 첫번째 원소만 비교하여 이진탐색을 진행할 수 있었다(그렇지 않으면 compare 함수를 넣어주어야한다)