codeforce div 2

COFO::Round 707

cofo round

COFO::Round #707

Link : COFO::round 707 (div 2)
solved :
- A : ( 01:00 )
- B : ( 01:31 )
- rank : 4531
- score : 1013

Problem A : Alexey and Train

level : 800
tag : implementation

Point

n이 주어집니다.
n개의 pair{a, b}가 주어집니다.
- i번째 pair는 i번째 기차역에 도착하는 시간 a와 해당 역을 떠나는 시간 b를 의미합니다.
n개의 t값이 주어집니다.
- 기차가 pair{a,b}대로 움직이면 좋겠지만, 의도치않게 delay가 발생합니다.
- 그 delay에 대한 값이 t[i]입니다.
이때, n번째 기차역에 도착하는 시간을 출력하면 됩니다.

Design

로직을 간단하게 설명하면 다음과 같습니다.
기차역 A -> 기차역 B -> 기차역 C가 있다고 합시다.
- 각 역에 대해서 주어진 pair는 다음과 같다고 합시다.
- {a1, b1}, {a2, b2}, {a3, b3}
delay t[i]들로 인해서, 기차역에 도착하는 시간과 기차역에서 출발하는 시간이 달라집니다.
기차역 i를 떠나는 시간은 다음 두 가지를 모두 만족해야 합니다.
- 기차역 i에 ceil((b[i] - a[i])/2) 시간 이상 머물러야 합니다.
- 현재 시간이 b[i]이상이어야 합니다.
위의 조건에 따라서, t[i]뿐만 아니라 또 하나의 delay가 더 생길 수 있는 셈입니다.
그럼 이제 정말 로직을 얘기해봅시다.
기차역 A에 도착하는 시간 : t[1]
기차역 A에서 출발하는 시간 : max(b[i], ceil((b[i]-a[i])/2)) + current time)
기차역 B에 도착하는 시간 : 기차역 A에서 출발하는 시간 + (b[i] - a[i-1])
…

Big O(time)

O(N)

Big O(memory)

Code

#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define r_rep(i, a, b) for(int i=(a); i>(b); i--)
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;

int n;
vector<int> a, b, t;
void input(){
    cin >> n;
    a.clear(); b.clear(); t.clear();
    a.resize(n+1); b.resize(n+1); t.resize(n+1);
    rep(i, 1, n+1) cin >> a[i] >> b[i];
    rep(i, 1, n+1) cin >> t[i];
}
void solve(){
    input();
    int ans = 0;
    rep(i, 1, n+1){
        ans += (t[i] + a[i] -b[i-1]);
        if(i == n) break;
        int leave = (b[i] - a[i])/2;
        if((b[i] - a[i]) %2) leave++;
        ans = max(b[i], ans + leave);
    }
    cout << ans << '\n';
}
int main(){
    //freopen("input.txt", "r", stdin);
    int tc; cin >> tc;
    while(tc--){
        solve();
    }
    return 0;
}

Problem B : Napoleon Cake

level : 900
tag : dp, implementation, sortings

Point

n이 주어집니다.
n개의 숫자가 주어집니다.
총 n번의 작업이 끝난 후, 빵의 상태를 출력합니다.
각 작업은 다음과 같은 요소 작업으로 구성되어있습니다.
- 먼저, 빵 1장을 맨 위에 쌓습니다.
- 그리고, 위에서부터 a[i]개의 빵에 색칠을 합니다.
결론적으로, a[i]를 모두 순회한 이후 각 빵이 색칠되었는지 여부를 맨 아래빵부터 출력합니다.

Design

n개의 작업에 대해서 빵을 하나씩 칠하면 TLE가 예상됩니다.
따라서, 표기만 해두는 방법을 사용했습니다.
예를 들어, a[6] = 3이라고 했을때,
- 4, 5, 6번 빵이 색칠되어야 합니다.
- 따라서, count[4]++, count[7]– 를 해둡니다.
- 그리고, cnt += count[i] 를 이용하여 cnt값이 음수인지 양수인지로 빵에 색칠되었는지 여부를 확인합니다.
- 즉, 시작점과 끝점에만 표기해두는 방법입니다.

Big O(time)

O(N)

Big O(memory)

Code

#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define r_rep(i, a, b) for(int i=(a); i>(b); i--)
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;


int n;
vector<int> a;
void solve(){
    cin >> n;
    a.clear(); a.resize(n+2);
    rep(i, 1, n+1){
        int x;
        cin >> x;
        if(x == 0) continue;
        int mx = max(((i+1) - x), 1);
        a[mx] ++;
        a[i+1] --;
        
    }
    int cnt = 0;
    vector<int> ans;
    rep(i, 1, n+1){
        cnt += a[i];
        if(cnt > 0) ans.push_back(1);
        else ans.push_back(0);
    }
    rep(i, 0, ans.size()){
        cout << ans[i] <<" ";
    }
    cout << '\n';
    
}
int main(){
    //freopen("input.txt", "r", stdin);
    int tc; cin >> tc;
    while(tc--){
        solve();
    }
    return 0;
}

Problem C : Going Home

level : 1800
tag : brute force, implementation, math
투포인터로 비벼보았지만 택도 없던 문제입니다.
O(N^2) 알고리즘을 사용하지만, 실제 복잡도가 무조건 문제에 제시된 2.5 * 10^이내에 들어온다는 관찰을 할 줄 알아야 합니다.
아직도 명확하게 이해되지 않습니다만, 몇 번 보며 이해해보려 합니다.

Point

n이 주어집니다.
n개의 음수가 아닌 정수가 주어집니다.
이 수들 중 다음 조건을 만족하는 인데스 x, y, z, w가 있는 지 찾습니다.
- a_x + a_y = a_z + a_w
존재한다면, YES 와 x, y, z, w를 출력합니다.
그렇지 않은 경우 NO를 출력합니다.

Design

editorial과 Green님의 설명을 포함하고 있습니다.
정말 간단하게 O(N^2)으로 sum을 구합니다.
a[i] + a[j] = sum이라고 하겠습니다.
해당 sum과 같은 값을 가지는 쌍 (i, j)가 4개 있으면 항상 거기서 답이 있다는 것을 뽑을 수 있습니다.
sum의 범위가 [0 ~ 250]만 이라서, 비둘기집의 원리로 250만 * 3번 정도 (i, j)를 확인했으면 무조건 답이 있습니다.

Big O(time)

Big O(memory)

Code

#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define r_rep(i, a, b) for(int i=(a); i>(b); i--)
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
typedef long long ll;
using namespace std;

struct point {int id; int val;};

int n;
vector<point> a;
bool cmp(const point x, const point y){
    return x.val < y.val;
}

const ll maxN = 5e6 + 100;
//map<int, pair<int,int> > mp;
vector<pair<int, int>>res(maxN, make_pair(-1, -1));
void input(){
    a.clear();
    cin >> n;
    a.resize(n);
    rep(i, 0, n){ cin >> a[i].val; a[i].id = i; }
    sort(a.begin(), a.end(), cmp);
}
void solve(){
    input();
    
    for(int i = 0; i < n; i++){
        for(int j = i+1; j < n; j++){
            int sum = a[i].val + a[j].val;
            if(a[i].id != res[sum].first && a[i].id != res[sum].second && a[j].id != res[sum].first & a[j].id != res[sum].second){
                if(res[sum].first == -1){
                    res[sum] = { a[i].id, a[j].id};
                    continue;
                }
                cout << "YES\n";
                cout << res[sum].first +1 << " " << res[sum].second + 1 << " " << a[i].id+1 << " " << a[j].id+1 << '\n';
                return ;
            }
        }
    }
    cout << "NO\n";
}
int main(){
    //freopen("input.txt", "r", stdin);
    int tc; tc = 1;
    while(tc--){
        solve();
    }
    return 0;
}