2020 KOI 1차대회 고등부 문제 풀이

작성일 | In

문제 링크

1교시
2교시

1교시 유형1 - 01번

  • 이긴 사람이 AA일 확률: 1/4
  • BAA일 확률: 1/8
  • ABA일 확률: 1/8
  • BBAA일 확률: 1/16
  • BABA일 확률: 1/16
  • ABBA일 확률: 1/16

다 더하면 11/16

1교시 유형1 - 02번

위 그림에서 빨간색으로 칠한 곳(0이 적힌 칸 주변 8개)에는 지뢰가 있을 수 없습니다.
오른쪽 위에 1이 있기 때문에 (가) 위치에는 무조건 지뢰가 있어야 합니다.

1교시 유형1 - 03번

버블 정렬은 매 단계마다 가장 큰 수가 맨 뒤로 갑니다. 세번째로 큰 수인 11이 답이 됩니다.

1교시 유형1 - 04번

  • 첫번째 문장이 참이라고 가정하면, 1번과 2번 상자에 금화가 들어가게 됩니다. (불가능)
  • 두번째 문장이 참이라고 가정하면, 모순이 생깁니다. (불가능)
  • 세번째 문장이 참이라고 가정하면, 2번 상자에 금화가 들어가게 됩니다. (가능)

2번 상자에만 금화가 있을 수 있습니다.

1교시 유형1 - 05번

$\frac{190}{400} = \frac{19}{40}$

1교시 유형1 - 06번

벤다이어그램을 그려보면 쉽게 알 수 있습니다.
$9+9-x=12, \space x = 6$

1교시 유형1 - 07번

$x$의 약수의 개수가 짝수라면 $x$번 문은 초기 상태를 유지하고, 홀수라면 그렇지 않습니다.
2, 5, 7은 약수가 2개, 49는 3개, 72는 12개이므로 49가 정답이 됩니다.

1교시 유형1 - 08번

$n$를 만드는 경우의 수를 $F(n)$라고 정의합시다.

  • $F(1) = 1$
  • $F(2) = 2$
  • $F(3) = 4$
  • $F(n) = F(n-1) + F(n-2) + F(n-3)$

열심히 계산해주면 $F(8) = 81$이라는 결과가 나옵니다.

1교시 유형1 - 09번

  • 13은 만들 수 없습니다.
  • 14는 7+7로 만들 수 있습니다.
  • 15는 5+5+5, 16은 11+5, 17은 5+5+7로 만들 수 있습니다.

14가 정답이 됩니다.

1교시 유형1 - 10번

길이가 n미터인 바닥을 채우는 경우의 수를 $F(n)$이라고 정의합시다.

  • $F(1) = 1$
  • $F(2) = 2$
  • $F(n) = F(n-1) + F(n-2)$

열심히 계산해주면 $F(10) = 89$라는 결과가 나옵니다.

1교시 유형1 - 11번

b 다음에는 a가 올 수 없고 c 다음에는 c만 올 수 있습니다. 즉, a…ab…bc…c 꼴의 문자열만 만들 수 있습니다.
문자열의 suffix를 바꿔가면서 잘 카운팅해주면 답을 구할 수 있습니다.
aaaabbbbbb가 답이 됩니다.

1교시 유형1 - 12번

nim게임입니다. 두 더미에 있는 돌의 개수를 xor한 결과가 0이면 후공이 이기고, 0이 아니면 선공이 이깁니다.
n과 m이 다르기 때문에 두 수를 xor한 값은 항상 0이 아니게 되고, 따라서 A가 항상 승리합니다.

1교시 유형2 - 01번

1, 2, 3, 4, 5
31, 32, 33, 34, 35
61, 62, 63, 64
14개입니다.

1교시 유형2 - 02번

어떤 더미에 동전이 X개 있을 때, 한 번의 “행동”으로 0 혹은 X-1로 만들 수 있습니다. 그러므로 동전이 X개 있는 더미의 Grundy Number $G(X) = 1$입니다. 단, 예외적으로 $G(2) = 2$입니다.
초기 상태에서 모든 더미의 Grundy Number를 xor한 값 $G$는 0이 아니기 때문에 선공이 항상 승리할 수 있습니다. 자신의 차례에서, 돌을 적당히 가져가서 $G$가 0이 아니도록 만드는 것을 반복하면 이기게 됩니다. 이는 동전이 2개 이상 있는 더미를 선택해서 동전 1개를 가져가는 것으로 구현할 수 있습니다.

1교시 유형2 - 03번

열심히 하면 됩니다. 화이팅

1교시 유형2 - 04번

손으로 DP를 계산하면 됩니다. 혹은 여러 번 시도해서 더 좋은 해를 구하는 작업을 반복해도 됩니다.
최댓값은 137입니다.

1교시 유형2 - 05번

열심히 하면 됩니다. 화이팅
최솟값은 11입니다.

1교시 유형2 - 06번

작년 11월에 풀이를 쓴 문제입니다. (링크)
남은 정점 중 degree가 가장 작은 정점을 선택하는 것이 최적이고, 위 링크에 증명이 잘 나와있습니다.
최댓값은 2입니다.

1교시 유형2 - 07번

차이가 더 작아지는 방향으로 swap을 해주면 0을 만들 수 있습니다.

1교시 유형2 - 08번

Nordic Olympiad in Informatics 2017 Subway와 동일한 문제입니다.

편의상 문제에서 주어진 두 트리를 $T_1, T_2$, 트리 $T$의 간선 집합을 $E(T)$, 정점의 개수를 $N$이라고 합시다.
간선 교체 횟수의 하한이 $(N-1) - n(E(T_1) ∩ E(T_2))$라는 것은 쉽게 알 수 있습니다. $T_1, T_2$ 중 한 곳에만 있는 간선은 교체를 해야하기 때문입니다.
$T_1, T_2$에 모두 존재하는 간선은 10개이므로 19번의 간선 교체로 문제를 풀 수 있습니다.

2교시 1번 - 박 터뜨리기

간단한 식 정리로 풀 수 있습니다.
$n’ = n - \frac{k(k+1)}{2}$로 정의하면, 정답은 ($k-1$ + (n’이 k의 배수면 0, 아니면 1))이 됩니다. 물론, $n’ < 0$이면 -1을 출력해야 합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    ll n, k; cin >> n >> k; n -= k*(k+1)/2;
    if(n < 0){ cout << -1; return 0; }
    if(n % k) cout << k;
    else cout << k-1;
}

2교시 2번 - 햄버거 분배

간단한 그리디 문제입니다. 왼쪽에 있는 사람부터 보면서, 먹을 수 있는 햄버거 중 가장 왼쪽에 있는 것을 먹으면 됩니다.
이분 그래프를 만들어서 최대 매칭을 구해도 100점을 받을 수 있습니다. 아래 코드는 이분매칭 코드입니다.

chk 배열을 매번 초기화해주면 40점 정도 나온다고 하는데, 매번 초기화하는 대신 timeframe을 관리한다는 느낌으로 해주면 100점을 받을 수 있습니다. 자세한 것은 코드를 참고해주세요.

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
39
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

int n, k, a[101010];
vector<int> g[101010];
int chk[101010], par[101010], pv;

int dfs(int v){
    if(chk[v] == pv) return 0; chk[v] = pv;
    for(auto i : g[v]) if(chk[i] != pv) {
        chk[i] = pv;
        if(par[i] == -1 || dfs(par[i])){ par[i] = v; return 1; }
    }
    return 0;
}

int match(){
    int ret = 0; memset(par, -1, sizeof par);
    for(int i=1; i<=n; i++) if(a[i]) pv++, ret += dfs(i);
    return ret;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> k;
    for(int i=1; i<=n; i++){
        char c; cin >> c; a[i] = c == 'P';
    }
    for(int i=1; i<=n; i++) if(a[i]) {
        for(int j=max(1, i-k); j<=min(n, i+k); j++) if(!a[j]) {
            g[i].push_back(j); g[j].push_back(i);
        }
    }
    cout << match();
}

2교시 3번 - 조명등

IOI’16 Aliens에서 K 조건 없애고 45도 돌려놓은 문제입니다.

먼저, 필요 없는 조각품을 먼저 제거합시다.


검은색 조각품을 조명으로 커버하면, 초록색 내부에 있는 조각품(파란색 조각품)은 무조건 커버하게 됩니다. 이런 조각품을 제거할 것입니다.
식으로 표현하자면, $i < j$일 때 $H_i - X_i \leq H_j - X_j$이면 $i$는 필요 없습니다. 또한 $j < i$일 때 $H_i + X_i \geq H_j + X_j$이면 $i$는 필요 없습니다. 이런 장식품을 제거하고 생각합시다.

45도 기울기를 생각하기도 귀찮기 때문에 좌표축을 45도 회전시킵시다.
좌표 평면 상에 점 여러 개가 주어졌을 때, 두 점이 $y = x$ 위에 있는 정사각형으로 덮는 문제로 바뀌게 됩니다. 넓이는 최소화해야하고요. IOI’16 Aliens와 동일한 문제로 바뀌었습니다.

$i$번째 점의 위치를 $(X_i, -X_i)$라고 합시다. $D(i)$를 $i$번째 점까지 커버하는 최소 비용으로 정의합시다.
$D(i) = \min( D(j) + (X_i - X_{j+1}+1)^2 - max(0, X_j-X_{j+1}+1)^2 )$입니다. 이 식을 그대로 계산하면 $O(N^2)$이고, 31점을 받게 됩니다.

식에 제곱식이 들어가있고 N이 최대 10만인 것을 보니, Convex Hull Trick을 써야할 것 같습니다. CHT를 이용해 점화식을 계산해주면 $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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

struct CHT{
    struct Line{
        ll a, b, c;
        Line() : Line(0, 0, 0) {}
        Line(ll a, ll b, ll c) : a(a), b(b), c(c) {}
        ll f(ll x){ return a * x + b; }
    };
    Line v[101010]; int pv, top;
    void init(){ pv = top = 0; }
    int chk(const Line &a, const Line &b, const Line &c){
        return (__int128_t)(a.b - b.b) * (b.a - c.a) <= (__int128_t)(c.b - b.b) * (b.a - a.a);
    }
    void update(Line l){
        while(top >= pv+2 && chk(v[top-2], v[top-1], l)) top--;
        v[top++] = l;
    }
    void update(ll a, ll b, ll c = 0){ update({a, b, c}); }
    p query(ll x){
        while(pv+1 < top && v[pv].f(x) >= v[pv+1].f(x)) pv++;
        return {v[pv].f(x), v[pv].c};
    }
} cht;

ll n, x[101010], h[101010];
p a[101010]; ll dp[101010];


void pre_process(){
    vector<p> stk;
    for(int i=1; i<=n; i++){
        if(stk.empty()){ stk.emplace_back(x[i], h[i]); continue; }
        while(stk.size() && stk.back().y-stk.back().x <= h[i]-x[i]) stk.pop_back();
        stk.emplace_back(x[i], h[i]);
    }
    for(int i=1; i<=stk.size(); i++) x[i] = stk[i-1].x, h[i] = stk[i-1].y;
    n = stk.size(); stk.clear();
    for(int i=n; i; i--){
        if(stk.empty()){ stk.emplace_back(x[i], h[i]); continue; }
        while(stk.size() && stk.back().y+stk.back().x <= h[i]+x[i]) stk.pop_back();
        stk.emplace_back(x[i], h[i]);
    }
    for(int i=stk.size(); i; i--) x[i] = stk[i-1].x, h[i] = stk[i-1].y;
    n = stk.size();
}

void solve(){
    cin >> n;
    for(int i=1; i<=n; i++) cin >> x[i] >> h[i];
    pre_process();

    dp[0] = 0;
    cht.update(2*(h[1]-x[1]), (h[1]-x[1])*(h[1]-x[1]));
    for(int i=1; i<=n; i++){
        ll t = x[i] + h[i];
        dp[i] = cht.query(t).x + t*t;
        cht.update(2*(h[i+1]-x[i+1]), (h[i+1]-x[i+1])*(h[i+1]-x[i+1]) + dp[i]);
    }
    cout << dp[n]/4 << ".";
    switch(dp[n] & 3){
        case 0: cout << "00\n"; break;
        case 1: cout << "25\n"; break;
        case 2: cout << "50\n"; break;
        case 3: cout << "75\n"; break;
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int t; cin >> t; while(t--) solve();
}