AtCoder Beginner Contest 207-A부터 C까지 업솔빙

AtCoder Beginner Contest 207 A부터 C까지 업솔빙

C번 문제 이거는 모르면 그냥 당하는 문제라고 생각했다. 문제 제목도 많은 조건 분기라서 이렇게 많은 조건을 분기해야 하나? 라는 생각을 하면서 문제를 풀었는데 결국은 못풀고 보니까 애초에 이런 문제를 푸는 방법이 있었다. 진짜 PS는 고인물 판인거 같다.

1. 두 구간이 교차하는 조건 쉽게 구하기
2. 닫힌구간과 열린구간에 대한 처리 방법

문제 옆에 붙어있는 난이도는 Atcoder Problems 에서 추정한 것으로 작성했다는 것을 미리 알린다.

A - Repression (*6)

접기/펼치기

문제 설명
책상에 카드 3개가 있고 각 카드에는 양수가 적혀져 있다. 각 카드에 적혀있는 정수는 $A, B, C$이다.

두 카드를 선택하고 두 카드를 집는다.

집은 카드에 있는 숫자의 합의 최대값을 구하라.

문제 해설
설명이 필요한가? 경우의 수는 3개 밖에 없다. max함수 써서 해결. 이때 3개 이상의 원소에 대한 max함수는 중괄호를 사용해야한다.

정답 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int a, b, c; cin >> a >> b >> c;
    cout << max({a + b, a + c, b + c});
    return 0;
}

B - Hydrate (*98)

접기/펼치기

문제 설명
파란색 공 $A$가 들어있는 상자가 있다. 철수는 원하는 만큼 다음 연산을 반복할 수 있다. (0번 반복할 수도 있음)

• 파란색 공 $B$개와 빨간색 공 $C$개를 상자에 넣는다.

철수의 목표는 다음 상황을 만드는 것이다.

• 상자에 들어있는 파란공의 개수가 상자 안에 들어 있는 빨간공의 개수의 최대 $D$배 인 상황.

이 목표가 달성할 수 있는지 결정하고 만약 달성할 수 있다면 달성하기 위해서 필요한 최대 연산 횟수를 구하라.

문제 해설
철수의 목표를 식으로 나타내면 다음과 같다. 연산의 횟수를 $K$번이라고 하면, $A + BK \le CDK$ 이 식을 $K$에 대한 식으로 정리하면 $A \le K(CD - B)$ 이다. 이때 이 식이 정의되려면 $CD - B > 0$ 이어야 한다. 따라서 $CD - B \le 0$ 이라면 목표를 달성할 수 없고 따라서 -1을 출력한다.

$CD - B > 0$ 이라면 $A / (CD - B) \le K$ 가 되고 이 식을 만족하는 최소 $K$를 구하기 위해서는 $CD - B$를 $DIV$라고 하면 $K = (A + DIV - 1) / DIV$ 로 구할 수 있다.

정답 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int a, b, c, d; cin >> a >> b >> c >> d;
    int mod = c * d - b;
    cout << (mod < 1 ? -1 : (a + mod - 1) / mod);
    return 0;
}

C - Many Segments (*397)

접기/펼치기

문제 설명
$1$ 부터 $N$까지 번호가 부여된 구간 $N$개가 다음과 같이 주어진다.

• 만약 $t_i = 1$ 이면, 구간 $i$는 $[l_i, r_i]$ 이다.
• 만약 $t_i = 2$ 이면, 구간 $i$는 $[l_i, r_i)$ 이다.
• 만약 $t_i = 3$ 이면, 구간 $i$는 $(l_i, r_i]$ 이다.
• 만약 $t_i = 4$ 이면, 구간 $i$는 $(l_i, r_i)$ 이다.

구간 $i$와 $j$가 서로 교차하는 순서쌍 $(i, j) (1 \le i < j \le N)$ 의 개수는 몇개 일까?

문제 해설
서로 교차하는 구간을 파악하기 위해서는 두 두간이 서로 닫힌 구간인지, 열린구간인지 일일이 따져가며 구해야 하는 불편함이 있다. 따라서 보통 다음과 같은 방법을 쓴다고 하니 잘 알아두자. 모를 때 찾아볼 수라도 있게.

1. 닫힌 구간과 열린 구간이 한 점에서 겹치는 예외 조건 처리를 쉽게 하기 위해서 오른쪽 열린 구간에는 $0.5$ 를 빼고, 왼쪽 열린 구간에는 $0.5$를 더해서 열린 구간과 닫힌 구간이 서로 한 점에 만날 때 답이 잘못 출력되는 경우를 막는다.

2. 이런 처리를 하고 나서 두 순서쌍이 각각 $i, j$, 각 순서쌍의 왼쪽을 $l_i, l_j$, 각 순서쌍의 오른쪽을 $r_i, r_j$라고 하면 $max(l_i, l_j) \le min(r_i, r_l)$ 를 만족하면 반드시 두 순서쌍은 겹친다. 그렇지 않으면 순서쌍은 겹치지 않는다.

정답 코드

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    double l[n], r[n];
    for(int i = 0; i < n; i++){
        int type; cin >> type;
        cin >> l[i] >> r[i];
        if(type == 2) r[i] -= 0.5;
        if(type == 3) l[i] += 0.5;
        if(type == 4) l[i] += 0.5, r[i] -= 0.5;
    }
    int res = 0;
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            if(max(l[i], l[j]) <= min(r[i], r[j])) res++;
        }
    }
    cout << res;
}