Codeforces Educational Round 80 후기 + 풀이

Div2 기준 137등으로, 59점이 올라 2035점이 되었다. Max Rating 보다 약간 낮다.

전반적으로 셋은 재밌었는데, C번에서 약간의 뇌절 + E번에서 분명 풀었던 문제와 매우 비슷한데 실패해서 아쉽다. 

---

A. Deadline 

정수 $d$ 가 주어졌을 때 다음을 최소화하는 문제이다,

$$x + \left\lceil\frac{d}{x+1}\right\rceil$$

잠깐 Ceiling 을 무시하고 산술기하 평균을 이용하면, $x+1 = \sqrt{d}$ 가 최적임을 알 수 있다. ceiling 함수가 붙으므로 약간의 오차가 발생할 수 있으므로, $\sqrt{d}$ 를 기준으로 좌우 100개 정도씩 값을 확인해 보면 된다. 대략 수학적으로 최적을 구하고 그 주위를 보는 문제는 UCPC때도 풀어 본 적 있었고, 그때 한개인가 두개만 봐서 한번 틀렸었다. 

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define all(x) ((x).begin()),((x).end())
using pii = pair <int, int>;
#define int ll
 
inline int divv(int a, int b)
{
    return (a/b)+1 - (a%b==0?1:0);
}
bool solve()
{
    int n, d;
    cin >> n >> d;
    int u = sqrt(d);
    int st = max(u-100,0ll);
    int opt = INT_MAX;
    int ed = min(u+100,d);
    for (int i = st; i<=ed; i++)
        opt = min(opt, i + divv(d,i+1));
    return (opt <= n);
}
int32_t main()
{
    int t;
    cin >> t;
    while(t--)
        cout << (solve()?"YES\n":"NO\n");
}

---

B. Yet Another Meme Problem

$$ab + a + b = a \texttt{concat} b$$ 를 만족하는 $(a, b)$ 쌍의 개수를 찾는 문제.

잘 생각해 보면, $a \texttt{concat} b$ 의 값은 $b$의 자릿수를 $d$자리라고 할 때, $10^d a + b$ 이다. 따라서, $10^d a = ab + a$ 가 우리가 원하는 식이고, $b = 10^d - 1$, 즉 $b$ 가 9, 99, 999, 9999 와 같은 숫자이면 $a$의 값은 아무 것이나 상관이 없음을 안다. 

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define all(x) ((x).begin()),((x).end())
using pii = pair <int, int>;
#define int ll
 
void solve()
{
    int a, b;
    cin >> a >> b;
    int t = 10;
    int ans = 0;
    while(t-1 <= b)
    {
        t *= 10;
        ans++;
    }
    cout << ans * a << '\n';
}
int32_t main()
{
    int t; cin >> t; while(t--) solve();
}

---

C. Two Arrays

1부터 $n$까지의 수로 $m$개짜리 배열을 2개 만드는데, 배열 $A$는 단조증가, $B$는 단조감소여야 한다. 그리고 모든 인덱스에 대하여 \texttt{A[i] <= B[i]} 여야 한다는 조건이 있을 때, 경우의 수를 구하는 문제.

$A$의 끝은 $A$의 최댓값이고, $B$의 끝은 $B$의 최솟값이다. 이 인덱스에서 조건을 만족해야 하므로, $B$의 최소보다도 $A$의 최대가 더 작아야 한다.

$A$의 최대값을 $t$ 로 제한하였다고 생각해 보자. 이때, 맨 끝이 $t$가 아니라면 $t-1$ 로 제한한 것과 구분할 수 없으므로, 반드시 맨 끝에서는 $t$를 쓴다고 하자. 이때, 가능한 $A$배열의 경우의 수는 $_{t}H_{m-1}$ 가지이다. 이때 $B$를 뽑는 경우는 사실 $n-t+1$ 개 ($n$ 부터 $t$이상까지) 중 중복을 허용하여 $m$개를 뽑고 있으므로 $_{n-t+1}H_{m}$가지이다. 즉, 다음 식의 값이 그대로 답이 된다.

$$\sum_{i = 1}^{n} \ _{i}H_{m-1} \times \ _{n-i+1}H_{m}$$

중복조합을 반대로 써서 예제가 안 나오는걸 한참 동안 디버깅하느라, 시간을 엄청 많이 날렸다.

D번보다 더 오래 걸렸다;;;

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define all(x) ((x).begin()),((x).end())
#define int ll
#define MOD 1000000007
int binomial[2010][2010];
int n, m;
 
int nhr(int a, int b)
{
    if (a == 0 || b == 0) return 1;
    return binomial[a+b-1][b];
}
int32_t main()
{
    for (int i = 0; i<=2000; i++)
        binomial[i][0] = binomial[0][i] = 1;
    for (int i = 1; i<=2000; i++)
    {
        for (int j = 1; j<=i; j++)
        {
            if (i==j)
                binomial[i][j] = 1;
            else
                binomial[i][j] = (binomial[i-1][j-1]+binomial[i-1][j])%MOD;
        }
    }
    cin >> n >> m;
    int ans = 0;
    for (int i = 1; i<=n; i++)
    {
        ans += nhr(i, m-1)*nhr(n-i+1,m);
        ans %= MOD;
    }
    cout << ans%MOD << '\n';
}

---

D. Minimax Problem

굉장히 마음에 들었던 문제.

두 배열의 '연산' 을 index-wise maximum 으로 정의하고, '길이' 를 minimum value 로 정의하자. 이때, 주어진 $n$개의 배열들 중 $i \star j$ 의 길이를 최대화하는 문제. 

답이 $k$ 이상인지를 빠르게 판정할 수 있으면, $\log A \approx 30$ 번 정도 돌려 보면 답을 얻을 수 있다. (답에 대한 parametric search)

이제 $k$ 이상이 가능한지를 판정하는 문제인데, 전체 배열들을 한번 돌면서 이 배열들이 각각 $k$보다 크거나 같은 값을 가진 인덱스를 bitmask로 표시하고 나면, $2^m = 256$ 의 제곱 시간 만에 답이 존재하는지 여부를 판정할 수 있다. 말로 설명하기는 뭔가 꼬이지만, 이렇게 하면 $\mathcal{O}(\log A (nm + 2^{2m}))$ 시간에 문제를 해결할 수 있다. 

 

코딩은 비트연산을 잘 이용하면 매우 빠르게 짤 수 있었다 :)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define all(x) ((x).begin()),((x).end())
using pii = pair <int, int>;
#define int ll
#define MOD 1000000007
pii answer = {-1, -1};
int n, m, arr[303030][10];
int chk[303030];
int occ[256];
bool ok(int k)
{
    memset(occ,0,sizeof(occ));
    memset(chk,0,sizeof(chk));
    for (int i = 1; i<=n; i++)
    {
        for (int j = 0; j<m; j++)
        {
            if (arr[i][j]>=k)
                chk[i] += (1<<j);
        }
        occ[chk[i]] = i;
    }
    for (int i = 0; i<(1<<m); i++)
    {
        for (int j = 0; j<(1<<m); j++)
        {
            if ((i|j) != ((1<<m)-1))
                continue;
            else if (occ[i]==0 || occ[j]==0) continue;
            else
            {
                answer = {occ[i], occ[j]};
                return true;
            }
        }
    }
    return false;
}
int32_t main()
{
    usecppio
    cin >> n >> m;
    for (int i = 1; i<=n; i++)
        for (int j = 0; j<m; j++)
            cin >> arr[i][j];
    int lo = -1, hi = 1e9+5;
    while(lo + 1 < hi)
    {
        int mid = (lo+hi)/2;
        if (ok(mid))
            lo = mid;
        else hi = mid;
    }
    cout << answer.first << ' ' << answer.second << '\n';
}

---

E. Messenger Simulator

뭔가 결과적으로는 어떤 range에서 distinct 한 원소의 개수를 세는 문제 (수열과 쿼리 5) 로 환원되고, 이걸 이용해서 잘 하는 문제인 것은 캐치했다. 그런데 여기서 왜인지 잘 모르겠지만 업데이트 가능한 Merge Sort Tree를 짜야 잘 해결할 수 있다는 생각 (쿼리정렬을 해야 한다고 생각했다) 이 들었다. 뭔가 Persistent Segment Tree 를 짤 줄 몰라서 한 생각인데 어차피 저것도 짤 줄 모르긴 마찬가지기도 하고...

그래서 엄청 느리고 메모리도 많이 먹는 gnu_pbds의 order statistics tree 같은걸로 이상한 코드를 작성하다가 망했다. 

---

고급 자료구조에 대한 이해가 절대적으로 부족한 듯...ㅠ 

대충 이제 별일없으면 D까지 풀수있는거 같고, E에 수학이 나오면 좋겠지만 저런 자료구조가 나오면 바로 뇌절하는것 같다 :( PST는 언제 짜보지...