AtCoder ABC 261 풀이

https://atcoder.jp/contests/abc261/tasks

Tasks - AtCoder Beginner Contest 261

 

A. 

두 선분이 겹치는 길이를 구해주면 됩니다.

1. 안 겹치는 경우

2. 1번이 앞에서 겹치는 경우

3. 2번이 앞에서 겹치는 경우

4. 1번이 2번 안에 있는 경우

5. 2번이 1번 안에 있는 경우

5가지를 조건문으로 처리해줍시다.

#include<bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    if (b <= c || d <= a) {
        cout << 0;
    }
    else if (a <= c && d <= b) {
        cout << d - c;
    }
    else if (c <= a && b <= d) {
        cout << b - a;
    }
    else if (a <= c && c <= b && b <= d) {
        cout << b - c;
    }
    else if (c <= a && a <= d && d <= b) {
        cout << d - a;
    }
}

 

 

B. 

y=-x 대칭하여 항상 W와 L or  D와 D가 등장하면 됩니다. 

#include<bits/stdc++.h>
using namespace std;
char a[1001][1001];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = i+1; j <= n; j++) {         
            if (a[i][j] == 'W') {
                if (a[j][i] != 'L') {
                    cout << "incorrect";
                    return 0;
                }
            }
            if (a[i][j] == 'D') {
                if (a[j][i] != 'D') {
                    cout << "incorrect";
                    return 0;
                }
            }
            if (a[i][j] == 'L') {
                if (a[j][i] != 'W') {
                    cout << "incorrect";
                    return 0;
                }
            }
        }
    }
    cout << "correct";
}

 

 

C. 

map을 이용하여 문자열이 나타난 횟수를 문자열과 같이 출력해주면 됩니다. 

#include<bits/stdc++.h>
using namespace std;
map<string, int>mp;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        string s; cin >> s;
        if (mp[s]) {
            cout << s << "(" << mp[s] << ")" << '\n';
            mp[s]++;
        }
        else {
            cout << s << '\n';
            mp[s]++;
        }
    }
}

 

 

D. 

dp(idx, c)를 idx를 채울 것이고, 지금까지 콤보가 C개인 상태라고 정의합니다. 

만약 다음번이 뒷면이면 dp(idx+1,0)로 전이됩니다. 

만약 다음번이 앞면이면 dp(idx+1, c+1)+x[idx]+bonus[c+1]이 됩니다. 끝입니다.  

 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, m, x[5005], c, y, bonus[5005];
ll dp[5005][5005];

ll go(int idx, int c) {
    if (idx == n + 1) return 0;
    ll& ret = dp[idx][c];
    if (~ret) return ret;
    ret = max(go(idx + 1, 0), go(idx + 1, c + 1) + x[idx] + bonus[c + 1]);
    return ret;
}


int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)cin >> x[i];
    for (int i = 1; i <= m; i++) {
        cin >> c >> y;
        bonus[c] = y;
    }
    memset(dp, -1, sizeof(dp));
    cout << go(1, 0);
}

 

E. 

풀이 예정

 

 

F. 

오름차순 정렬하는 최소횟수를 구하는데, 추가조건이 같은 색인 경우 비용이 0이라는 점입니다. 

생각하는데 오래걸렸지만 아이디어는 정말 간단합니다. 

모두 다른 색이라 가정하고 inversion counting 을 한 후에 색깔별로 다시 inversion counting 해서 그 값을 

빼주면 됩니다. 그럼 비용이 0이 되겠죠.  inversion counting은 펜윅트리로 O(NlogN)에 해줄 수 있습니다. 

 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAX = 300005;
ll n, c[MAX], x[MAX], tree[MAX];
vector<int>v[MAX];

void upd(int i, int v) {
    while (i <= n) tree[i] += v, i += i & -i;
}

ll sum(int i) {
    ll ret = 0;
    while (i) ret += tree[i], i -= i & -i;
    return ret;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> c[i];
    for (int i = 1; i <= n; i++) {
        cin >> x[i];
        v[c[i]].push_back(x[i]);
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += sum(n) - sum(x[i]);
        upd(x[i], 1);
    }
    memset(tree, 0, sizeof(tree));
    for (int c = 1; c <= n; c++) {
        if (v[c].empty())continue;
        for (int j : v[c]) {
            ans -= sum(n) - sum(j);
            upd(j, 1);
        } 
        for (int j : v[c]) {
            upd(j, -1);
        }
    }
    cout << ans << '\n';
}