Atcoder Beginner Contest 189 풀이

F를 푼사람이 244명으로 F가 꽤 어려웠던 라운드같다. 아마 나도 문제에 쓰인 아이디어를 이 문제서 처음 봤다면 감도 안 왔을거 같다. E가 좀 수학적인 성향이 강한 느낌이다.

라운드 링크

A - Slot

정말 기본적인 문제. 길이 3인 문자열을 입력받고 세 글자가 전부 같은지 확인하자. 출력문이 Won, Lost로 좀 특이하니 주의

#include<bits/stdc++.h>
using namespace std;
string s; 
int main() {
  cin >> s;
  if(s[0] == s[1] && s[1] == s[2]) cout << "Won" << '\n';
  else cout << "Lost" << '\n';
  return 0;
}

B - Alcoholic

하나 하나 입력받으면서 섭취한 알콜의 용량이 주어진 $X$보다 높아지면 그 때가 몇 번째인지 출력하면 된다. 다만, 곧이 곧대로 퍼센트를 쓰면 실수오차 때문에 고통받을 가능성이 매우 높다.

용액의 용량이 $V$고 $P%$의 용량이면 $V*P/100$이 되지만, 분모의 100을 그냥 없애고 전부 100을 곱해서 연산을 수행하면 정수만으로도 연산이 가능하다.

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using ll = long long;
int N, X;
int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N >> X;
    X *= 100;
    int taken = 0;
    for (int i = 0; i < N; ++i) {
        int v, p; cin >> v >> p;
        int a = v * p;
        taken += a;
        if (taken > X) {
            cout << i + 1 << '\n';
            return 0;
        }
    }
    cout << -1 << '\n';
    return 0;
}

C - Mandarin Orange

히스토그램에서 가장 큰 직사각형이란 유명한 문제와 동일한 문제다. 해당 문제에 대해서는 $O(N^2)$, $O(NlogN)$, $O(N)$ 풀이 전부 있으며 이 문제에선 $N \le 10^4$기 때문에 어떤 걸 써도 통과 가능하다. 아래는 $O(N^2)$풀이

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using ll = long long;
int N;
ll a[10005];

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N;
    for (int i = 0; i < N; ++i) cin >> a[i];
    ll ans = 0;
    for (int i = 0; i < N; ++i) {
        ll h = a[i];
        for (int j = i; j < N; ++j) {
            h = min(h, a[j]);
            ans = max(ans, h * (j - i + 1));
        }
    }
    cout << ans << '\n';
    return 0;
}

D - Logical Expression

DP로 해결할 수 있다. $dp(i, j)$를 $x_0, \cdots , x_i$까지 정했을 때 결과가 $j(=0,1)$인 경우의 수라고 하자.

$S_i$.가 AND라면 $x_i$를 1로 했을 때 $dp(i,1)$에 $dp(i-1, 1)$만이 더해지고, 0으로 했을 때는 $dp(i, 0)$에 $2 \times dp(i-1, 0) + dp(i-1, 1)$가 더해진다.

$S_i$가 OR라면 $x_i$를 1로 했을 때, $dp(i, 1)$에 $dp(i-1, 0) + 2 \times dp(i-1, 1)$이 더해지고, 0으로 했을 때 $dp(i, 0)$에 $dp(i-1, 0)$이 더해진다.

답은 $dp(N, 1)$이 된다.

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using ll = long long;
ll dp[61][2];
int N;
int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N;
    vector<string> vs(N + 1);
    for (int i = 1; i <= N; ++i) cin >> vs[i];
    ll tot = 2;
    dp[0][0] = dp[0][1] = 1;
    for (int i = 1; i <= N; ++i) {
        if (vs[i] == "AND") {
            // choose true -> can make true
            dp[i][1] += dp[i - 1][1];
            dp[i][0] += dp[i - 1][0];
            // choose false -> all become false
            dp[i][0] += dp[i - 1][1];
            dp[i][0] += dp[i - 1][0];
        }
        else {
            // choose true -> all become true
            dp[i][1] += dp[i - 1][1];
            dp[i][1] += dp[i - 1][0];
            // choose false -> true is true
            dp[i][1] += dp[i - 1][1];
            dp[i][0] += dp[i - 1][0];
        }
    }
    cout << dp[N][1] << '\n';
    return 0;
}

E - Rotate and Flip

1번부터 4번까지의 변환을 행렬로 생각하고 $transform_i$를 0부터 $i$까지의 변환들의 변환 행렬을 곱한 행렬로 생각하면 쿼리를 $O(1)$에 해결이 가능하다.

문제는 3, 4번의 대칭은 선형변환이 아니라는 점이다. 그래서 $2 \times 2$의 변환 행렬 말고 $3 \times 3$의 변환 행렬을 관리해주면 된다.

1번 변환행렬은 $\begin{bmatrix}0 & 1 & 0 \\ -1 & 0 & 0 \\ 0 & 0 & 1\end{bmatrix}$이고, 2번 변환행렬은 $\begin{bmatrix}0 & -1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1\end{bmatrix}$, 3번 변환행렬은 $\begin{bmatrix}-1 & 0 & 2p \\ 0 & 1 & 0 \\ 0 & 0 & 1\end{bmatrix}$, 4번 변환행렬은 $\begin{bmatrix}1 & 0 & 0 \\ 0 & -1 & 2p \\ 0 & 0 & 1\end{bmatrix}$다.

0번째 변환 행렬은 그냥 단위행렬이고, 변환 쿼리가 들어올 때마다 위에서 정의한 행렬들을 왼쪽에 곱해주면 된다.

그리고 답을 구할 때는 $A_i, B_i$로 들어왔을 때 $transform_{A_i} \begin{bmatrix} x_{B_i} \\ y_{B_i} \\ 1\end{bmatrix}$를 구하고 첫번째, 두번째 원소를 답으로 구하면 된다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using mat = vector<vector<ll>>;
mat trans[4] = {
    {{0, 1, 0},
     {-1, 0, 0},
     {0, 0, 1}},
    {{0, -1, 0},
     {1, 0, 0},
     {0, 0, 1}},
    {{-1, 0, 0},
     {0, 1, 0},
     {0, 0, 1}},
    {{1, 0, 0},
     {0, -1, 0},
     {0, 0, 1}}
};
int N, M, Q;
mat mult(mat a, mat b) {
    mat ret(3, vector<ll>(3, 0));
    for(int i=0;i<3;++i) {
        for(int k=0;k<3;++k) {
            int temp = a[i][k];
            for(int j=0;j<3;++j) {
                ret[i][j] += temp * b[k][j];
            }
        }
    }
    return ret;
}

vector<mat> trans_mat;

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N;
    vector<pair<ll,ll>> a(N+1);
    for(int i=1;i<=N;++i) cin >> a[i].first >> a[i].second;
    cin >> M;
    mat A = {{1,0,0}, {0,1,0}, {0,0,1}};
    trans_mat.push_back(A);
    for(int i=0;i<M;++i) {
        ll x, p; cin >> x;
        if(x == 1) A = mult(trans[x-1], A);
        else if(x == 2) A = mult(trans[x-1], A);
        else if(x == 3) {
            cin >> p;
            trans[x-1][0][2] = 2*p;
            A = mult(trans[x-1], A);
            trans[x-1][0][2] = 0;
        }
        else if(x == 4) {
            cin >> p;
            trans[x-1][1][2] = 2*p;
            A = mult(trans[x-1], A);
            trans[x-1][1][2] = 0;
        }
        trans_mat.push_back(A);
    }
    cin >> Q;
    for(int i=0;i<Q;++i) {
        int q, idx; cin >> q >> idx;
        auto v = trans_mat[q];
        ll x = v[0][0]*a[idx].first + v[0][1]*a[idx].second + v[0][2];
        ll y = v[1][0]*a[idx].first + v[1][1]*a[idx].second + v[1][2];
        cout << x << ' ' << y << '\n';
    }
    return 0;
}

F - Sugoroku 2

$X_i$를 $i$번째 칸에서 출발 했을 때 $N$번째 칸에 도착할 때까지의 기댓값이라고 하자. 그러면 아래와 같이 정의할 수 있다. 우리가 원하는 값은 $X_0$다.
$$
X_i =\frac{1}{M}\sum_{k=1}^{M} X_{i+k} + 1
$$
이 때, $i$가 $A_i$ 중의 하나라면 $X_i = X_0$가 된다. 여기서 문제가 생긴다. 우리가 원하는 값이 $X_0$인데 이 $X_0$가 계산식에 포함되는 것이다.

일단 그런 $X_i$가 없다면(K=0)일 때는 $X_N = 0$이기 때문에 누적합으로 $O(N)$에 $X_0$를 구할 수 있다.

그렇지 않을 때 우리가 생각해볼만 한 것은 $X_0$를 유추해보는 것이다. 적당한 값으로 $X_0$일 것이라고 정한 뒤에 위 식을 이용해서 $X_0$를 계산하는 것이다.

그렇게 계산한 $X_0$를 $X_0'$라고 하자. $X_0' \lt X_0$라면, 그러니까 우리가 유추한 값이 계산된 값보다 크다면 우리는 실제 값보다 크게 유추한 것이다.

반대로 $X_0' \gt X_0$라면 우리는 실제 값보다 작게 유추한 것이다. 이를 이용해서 이분탐색을 진행할 수 있다. $X_0$가 실수이기 때문에 적절히 많은 반복횟수만큼 진행하면 답을 구할 수 있다.

그리고 불가능한 경우에는 -1을 출력하라고 나와 있는데 이게 불가능한 경우는 $M$개 이상의 칸이 연속으로 사용불가능한 경우 뿐이다.

이렇게 구해야 되는 DP값을 유추해서 이분탐색하는 유형의 문제로는 이 문제가 있다. 해당 문제에 대한 풀이도 블로그에 있다.

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using ll = long long;
using ld = double;
bool banned[100005];
ld dp[100005];
int N, M, K;

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N >> M >> K;
    for (int i = 0; i < K; ++i) {
        int x; cin >> x;
        banned[x] = true;
    }
    int seg = 0;
    for (int i = 1; i <= N; ++i) {
        if (banned[i]) {
            int idx = i;
            while (idx <= N && banned[idx]) ++idx;
            seg = max(seg, idx - i);
        }
    }
    if (seg >= M) {
        cout << -1 << '\n';
        return 0;
    }
    ld lo = 1, hi = 1e18;

    for (int iter = 0; iter < 150; ++iter) {
        ld mid = (lo + hi) / 2.0;
        ld sum = 0;
        for (int i = N - 1; i > max(0, N - M); --i) {
            if (banned[i]) dp[i] = mid;
            else dp[i] = sum / (ld)M + 1;
            sum += dp[i];
        }
        if (N - M <= 0) {
            dp[0] = sum / (ld)M + 1;
            if (mid >= dp[0]) hi = mid;
            else lo = mid;
        }
        for (int i = N - M; i >= 0; --i) {
            if (banned[i]) dp[i] = mid;
            else dp[i] = sum / (ld)M + 1;
            sum += dp[i];
            sum -= dp[i + M];
        }
        if (mid >= dp[0]) hi = mid;
        else lo = mid;
    }
    cout << fixed << setprecision(15) << (lo + hi) / 2.0 << '\n';
    return 0;
}