Codeforces Hello 2020 (div.2)

05 Nov 2021

Codeforces Hello 2020 (div.2)

B. New Year and Ascent Sequence

길이 l인 배열이 주어질때, $1≤𝑖<𝑗≤l$ 인 인덱스에 대해 $𝑎_𝑖<𝑎_j$ 인 원소가 있다면 ascent 하다고 합니다. 배열 n개가 주어지고, n개의 array에 대한 모든 pair sequence 에 대해 ascent한 개수를 세는 문제입니다.

1개의 배열 자체가 ascent한 경우와 아닌 경우를 분리하여 풀었습니다. (매우 코드가 깁니다.) editorial의 정해는 전체 pair의 개수 $n^2$에서 non-increasing sequence pair의 개수를 빼는 것 입니다.

non-increasing sequence인지 확인하는 방법은 vector의 모든 원소를 reverse한 뒤에 오름차순인지 확인하면 됩니다. non-increasing sequence a,b에 대해 a의 마지막 원소가 b의 첫번쨰 원소보다 크거나 같은 경우를 세서 전체에서 빼주면 됩니다.

code

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#define endl '\n'
#define INF 1e9
#define LINF 9223372036854775807
using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int> tup;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
priority_queue<tup,vector<tup>,greater<tup>> edge;

int t;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int n;
    cin>>n;
    vector<pi>w;
    for(int i=0;i<n;i++){
        int l ;
        cin>>l;
        vector<int>v;
        for(int j=0,p1;j<l;j++){
            cin>>p1;
            v.push_back(p1);
        }
        reverse(v.begin(),v.end());
        if(is_sorted(v.begin(),v.end())){
            w.push_back({v[0],v.back()});
        }
    }
    ll ans = n*n;
    sort(w.begin(),w.end());
    for(auto k: w){
        ans -= (w.end()- lower_bound(w.begin(),w.end(),pi(k.second,0)));
    }
    cout<<ans<<endl;

    return 0;
}

C. New Year and Permutation

1부터 n까지의 수로 이루어져 있는 순열이 있고, 순열의 framed segment 중 인덱스 l,r(1≤l≤r≤n)에 대해 $max(𝑝_𝑙,𝑝_{𝑙+1},…,𝑝_𝑟)−min(𝑝_𝑙,𝑝_{𝑙+1},…,𝑝_𝑟)=𝑟−l$ 을 만족하는 segment를 세주는 문제입니다. 순열을 고정하는 것이 아닌 l과 r을 고정하여 문제를 풉니다.

만약 framed segment [l,r] 이 위 조건을 만족한다면, l부터 r까지의 인덱스에 l부터 r까지의 원소가 들어가 있습니다.

그래서 전체 경우의 수를 계산하면 (r-l+1)! * (n-(r-l+1))! * (r-l을 만족하는 순열의 개수) 이 문제의 답이 됩니다. factorial를 1부터 n까지 모두 배열에 저장해두면, O(N)의 시간에 해결할 수 있습니다.

code

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#define endl '\n'
#define INF 1e9
#define LINF 9223372036854775807
using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int> tup;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
priority_queue<tup,vector<tup>,greater<tup>> edge;
vector<vector<pi>> v;

int t;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    ll n,m;
    cin>>n>>m;
    ll d[250001];
    d[0]=1;
    d[1]=1;
    for(ll i=2;i<=n;i++){
        d[i]=i*d[i-1]%m;
    }
    ll ans = 0;
    for(ll i=0;i<n;i++){
        ans += (n-i)*(d[i+1]*d[n-i]%m);
        ans %=m;
    }
    cout<<ans<<endl;
    return 0;
}

D. New Year and Conference

장소 a,b가 있고, n개의 수업이 있을때, speaker는 시간인터벌 $[sa_i,ea_i], [sb_i,eb_i]$가 정해진다. a에서 conference가 열리면 전자의 시간 인터벌, b에서 열리면 후자의 시간 인터벌을 사용한다. 장소에 상관없이 수업들이 overlap되지 않을 경우인지 아닌지를 구하는 문제이다.인터벌에서 어떠한 시점이라도 겹치면 overlap된다고 본다. (아직 못풀었습니다.. ㅠㅜ)

ChangHyeon Nam's Blog notes and thoughts

Codeforces Hello 2020 (div.2)