[코포 라운드 글 #2] Educational Codeforces Round 102 (Rated for Div. 2)

Round : Educational Codeforces Round 102 (Rated for Div. 2)

rank : 1304

solved : 4

Performance : 1777
Rating Change : +90 (1476->1566)

 

꽤 기적같은 라운드였다.

처음으로 내가 대회에서 세그를 써본거라 아주 자랑스러운(?) 라운드였다.

 

A. codeforces.com/contest/1473/problem/A

Problem - A - Codeforces

그냥 두가지 경우면 YES라고 판단할 수 있다.

1. 가장 작은 두 원소가 k의 합보다 크지 않을 때

2. 가장 큰 원소가 k보다 작거나 같을 때

#include <bits/stdc++.h>
#define MEM 5005
#define sanic ios_base::sync_with_stdio(0)
#define MOD 1000000
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;
const ll INF = 1e13+7;
ll n,m,k,t;
ll a[MEM];
main(){
    sanic; //cin.tie(0); cout.tie(0);
    cin >> t;
    while(t--){
        cin >> n >> k;
        for(int i=0; i<n; i++)
            cin >> a[i];
        sort(a,a+n);
        if(a[0]+a[1]<=k || a[n-1]<=k) cout << "YES";
        else cout << "NO";
        cout << '\n';
    }
}

B. codeforces.com/contest/1473/problem/B

Problem - B - Codeforces

그냥 lcm이 만들어질때의 특징을 이용해서 구현하면 된다.

 

#include <bits/stdc++.h>
#define MEM 5005
#define sanic ios_base::sync_with_stdio(0)
#define MOD 1000000
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;
const ll INF = 1e13+7;
ll gcd(ll a, ll b){
    if(a%b) return gcd(b, a%b);
    return b;
}
ll n,m,k,t;
main(){
    sanic; //cin.tie(0); cout.tie(0);
    cin >> t;
    while(t--){
        string a,b;
        cin >> a >> b;
        m = a.size()*b.size()/gcd(a.size(),b.size());
        k=0;
        string f;
        for(int i=0; i<m; i++){
            if(a[i%(a.size())]!=b[i%(b.size())]){
                k=1;
                break;
            }
            f += a[i%(a.size())];
        }
        if(k) cout << -1;
        else cout << f;
        cout << '\n';
    }
}

C. codeforces.com/contest/1473/problem/C

Problem - C - Codeforces

proof by ac

얘는 몇번 노트에 적어서 규칙을 찾아 풀었다.

기적

#include <bits/stdc++.h>
#define MEM 5005
#define sanic ios_base::sync_with_stdio(0)
#define MOD 1000000
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;
const ll INF = 1e13+7;
ll gcd(ll a, ll b){
    if(a%b) return gcd(b, a%b);
    return b;
}
ll n,m,k,t;
main(){
    sanic; //cin.tie(0); cout.tie(0);
    cin >> t;
    while(t--){
        cin >> n >> k;
        m = n-k;
        for(int i=0; i<k-m-1; i++)
            cout << i+1 << ' ';
        ll j=k;
        for(int i=k-m-1; i<k; i++){
            cout << j << ' ';
            j--;
        }
        cout << '\n';
    }
}

 

D. codeforces.com/contest/1473/problem/D

Problem - D - Codeforces

기적 시즌 2

구간합 + segment tree이다. 사실 세그는 안써도 된다. 거의 소 잡는 칼로 닭 잡는 것이랄까

먼저 구간합 배열을 만든 다음, 쿼리가 주어졌을때 구간합에서 뺄 원소들을 빼면서 최댓값 최소값을 찾으면 된다.

이를 세그먼트 트리를 이용한다.

#include <bits/stdc++.h>
#define MEM 200005
#define sanic ios_base::sync_with_stdio(0)
#define MOD 1000000
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;
const ll INF = 1e13+7;
int maxseg[4 * MEM], minseg[4 * MEM], a, b;
int maxupdate(int pos, int val, int node, int x, int y) {
    if (y < pos || pos < x)
        return maxseg[node];
    if (x == y)
        return maxseg[node] = val;
    int mid = (x + y) >> 1;
    return maxseg[node] = max(maxupdate(pos, val, node * 2, x, mid), maxupdate(pos, val, node * 2 + 1, mid + 1, y));
}
int maxquery(int lo, int hi, int node, int x, int y) {
    if (y < lo || hi < x)
        return -INF;
    if (lo <= x&&y <= hi)
        return maxseg[node];
    int mid = (x + y) >> 1;
    return max(maxquery(lo, hi, node * 2, x, mid), maxquery(lo, hi, node * 2 + 1, mid + 1, y));
}
int minupdate(int pos, int val, int node, int x, int y) {
    if (y < pos || pos < x)
        return minseg[node];
    if (x == y)
        return minseg[node] = val;
    int mid = (x + y) >> 1;
    return minseg[node] = min(minupdate(pos, val, node * 2, x, mid), minupdate(pos, val, node * 2 + 1, mid + 1, y));
}
int minquery(int lo, int hi, int node, int x, int y) {
    if (y < lo || hi < x)
        return INF;
    if (lo <= x&&y <= hi)
        return minseg[node];
    int mid = (x + y) >> 1;
    return min(minquery(lo, hi, node * 2, x, mid), minquery(lo, hi, node * 2 + 1, mid + 1, y));
}
int n,m,k,t;
int p[MEM];
main(){
    sanic; cin.tie(0); cout.tie(0);
    cin >> t;
    while(t--){
        cin >> n >> m;
        string s;
        cin >> s;
        for(int i=1; i<=s.size(); i++){
            ll g=(s[i-1]=='+' ? 1:-1);
            p[i] = p[i-1]+g;
            maxupdate(i, p[i], 1, 1, n);
            minupdate(i, p[i], 1, 1, n);
        }
        while(m--){
            ll l,r;
            cin >> l >> r;
            int d=p[l-1]-p[r];
            ll ma=max({maxquery(1, l-1, 1, 1, n), maxquery(r+1, n, 1, 1, n)+d,0});
            ll mi=min({minquery(1, l-1, 1, 1, n), minquery(r+1, n, 1, 1, n)+d,0});
            //cout << ma << ' ' << mi << ' ';
            cout << ma-mi+1 << '\n';
        }
    }
}