랜덤 마라톤 · 코스 50

작성일 | In

random marathon result

솔브드의 랜덤 마라톤이 베타를 종료하고 나서 처음으로 마라톤을 완주해 봤습니다.
앞으로도 랜덤 마라톤 풀이를 지속적으로 올릴 생각입니다.
한번 문제를 풀어봅시다.

A. 가지 한 두름 주세요

브론즈 III 브론즈 III

단순한 구현 문제입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<vector<string>> eggPlants(10, vector<string>(10));
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++)
            cin >> eggPlants[i][j];
    }

    for (int i = 0; i < 10; i++) {
        bool row = true, column = true;
        for (int j = 1; j < 10; j++) {
            if (eggPlants[i][j] != eggPlants[i][j - 1])
                row = false;
            if (eggPlants[j][i] != eggPlants[j - 1][i])
                column = false;
        }
        if (row or column) {
            cout << 1;
            return 0;
        }
    }
    cout << 0;
}

B. 귀찮아 (SIB)

실버 V 실버 V

문제에서 구해야 하는 것은 아래와 같습니다.

\[\sum_{1 \leq a < b \leq n} x_ax_b = \sum_{b = 2}^n\sum_{a = 1}^{b-1} x_a\]

누적합을 전처리 해 두면 $\sum\limits_{a = 1}^{b-1} x_a$를 $O(1)$에 구할 수 있습니다. 따라서 전체 시간복잡도는 $O(N)$ 입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<ll> x(n);
    for (int i = 0; i < n; i++)
        cin >> x[i];
    vector<ll> prefixSum(x);
    for (int i = 0; i + 1 < n; i++)
        prefixSum[i + 1] += prefixSum[i];

    ll answer = 0;
    for (int i = 1; i < n; i++)
        answer += x[i] * prefixSum[i - 1];

    cout << answer;
}

C. 차집합

실버 IV 실버 IV

단순한 집합 + 정렬 문제입니다.
집합 $A$에서 집합 $B$에 속하는 원소들을 모두 제거한 뒤, 남은 원소들을 정렬하여 출력하면 됩니다.

C++의 std::set을 쓰면 직접 정렬하지 않아도 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int nA, nB;
    cin >> nA >> nB;

    set<int> a;
    while (nA--) {
        int e;
        cin >> e;
        a.insert(e);
    }

    while (nB--) {
        int e;
        cin >> e;
        a.erase(e);
    }

    cout << a.size() << '\n';
    for (int e : a)
        cout << e << ' ';
}

D. 별 찍기 - 19

실버 IV 실버 IV

구현 문제입니다.
저는 사각형을 2칸씩 좁혀가면서 반복문으로 풀었습니다.
재귀로 구현해도 되고, 중심으로부터 떨어진 거리를 이용해 풀어도 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    int len = 4 * (n - 1) + 1;
    vector<vector<bool>> star(len, vector(len, false));

    for (int i = 0; i < n << 1; i += 2) {
        for (int j = i; j < i + len; j++) {
            star[i][j] = star[i + len - 1][j] =            // 가로
                star[j][i] = star[j][i + len - 1] = true;  // 세로
        }
        len -= 4;
    }

    for (auto row : star) {
        for (bool b : row) {
            cout << (b ? "*" : " ");
        }
        cout << '\n';
    }
}

E. 바지 구매

실버 IV 실버 IV

문제에서 주어진 그래프는 시루가 오른쪽으로 엎드려 있는 그림입니다.
시루의 하체와 딱 맞도록 바지를 입었을 때, 바지의 끝부분이 지면과 일치해야 하므로 $u = f(v)$여야 함을 알 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int a, b, c, d, n;
    cin >> a >> b >> c >> d >> n;

    auto f = [a, b, c, d](int x) { return max(a * (x - b) * (x - b) + c, d); };

    int answer = 0;
    while (n--) {
        int u, v;
        cin >> u >> v;
        if (u == f(v)) answer++;
    }

    cout << answer;
}

F. 황소 다마고치

실버 II 실버 II

황소의 현제 체력을 $h$라 하면 생존 가능 일수는 $\log_2 h$입니다.
먹이를 주어 $\log_2$의 값을 올려 주면 생존 가능 일수를 1 늘려줄 수 있습니다.
$h \neq 1$이면 $\log_2$ 값을 올리기 위한 먹이의 개수가 $1$ 이상입니다.
따라서 $h = 1$일 때 먹이를 하나씩 주면서 하루 하루 연명하는 것이 최선의 방법입니다.

엄밀하게 증명해 보겠습니다. 그러니까 먹이를 $m$개 주었을 때 $m$일 보다 많이 더 버틸 수 있는 경우가 없음을 증명하겠습니다.
식으로 쓰면 $\log_2 (h + m) \leq \log_2 h + m$입니다.

\[\begin{align} \log_2 (h + m) &\leq \log_2 h + m \\ \log_2 \frac{h+m}{h} &\leq m \\ \log_2 \left(1 + \frac{m}{h}\right) &\leq m \\ 1 + \frac{m}{h} &\leq 2^m \end{align}\]

$m = 1$일 때 자명하게 성립합니다.
$m = k$일때 성립한다고 합시다. 그렇다면 $1 + \dfrac{k}{h} \leq 2^k$ 입니다.
양변에 $2$를 곱하면 $2 + \dfrac{2k}{h} \leq 2^{k+1}$ 입니다.
여기서 $1 + \dfrac{k + 1}{h} \leq 2 + \dfrac{2k}{h}$ 이므로
$1 + \dfrac{k + 1}{h} \leq 2 + \dfrac{2k}{h} \leq 2^{k+1}$
따라서 성립합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        ll n, m;
        cin >> n >> m;
        cout << (int)floor(log2(n)) + m + 1 << '\n';
    }
}

G. 너의 티어는?

실버 I 실버 I

단순한 DP 문제입니다.
$p[i][j]$를 랭크전을 $j$판 하여 점수가 $i$일 확률이라고 합시다.
$p$는 아래의 점화식으로 구할 수 있습니다.

\[\begin{align} &p[1000][0] = 1 \\ &p[i][j] = w \cdot p[i - 50][j - 1] + l \cdot p[i + 50][j - 1] + d \cdot p[i][j - 1] \end{align}\]

코드에서는 $p[i][j]$를 한번에 구하는 방식이 아니라 따로 더하는 방식으로 구했습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cout.precision(8);
    cout << fixed;

    double w, l, d;
    cin >> w >> l >> d;

    vector<vector<double>> prob(3500, vector<double>(21));
    prob[2000][0] = 1;
    for (int k = 0; k < 20; k++) {
        for (int i = 1000; i <= 3000; i += 50) {
            prob[i + 50][k + 1] += prob[i][k] * w;
            prob[i - 50][k + 1] += prob[i][k] * l;
            prob[i][k + 1] += prob[i][k] * d;
        }
    }

    vector<double> answers(5);
    for (int i = 0; i < 5; i++) {
        int lb = 500 * (i + 2);
        for (int j = lb; j < lb + 500; j += 50)
            answers[i] += prob[j][20];
    }

    for (double p : answers)
        cout << p << '\n';
}

H. 가장 큰 값

골드 V 골드 V

단순 브루트 포스 문제입니다. 붙어 있는 수도 다른 그룹으로 생각할 수 있음에 유의합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<int> arr(n);
    for (int i = 0; i < n; i++)
        cin >> arr[i];

    int answer = -1e9;
    for (int k = 0; k < 1 << n; k++) {
        int sum = 0, count = 0, groupCnt = 0;
        bool group = false;

        for (int i = 0; i < n; i++) {
            if (k & (1 << i)) {
                sum += arr[i];
                count++;
                if (not group) {
                    group = true;
                    groupCnt++;
                }
            } else
                group = false;
        }

        if (groupCnt <= m and count >= m) {
            answer = max(answer, sum);
        }
    }

    cout << answer;
}

랜덤 마라톤 · 코스 50