AtCoder Beginner Contest 189

AtCoder Beginner Contest 189

AtCoder Beginner Contest 189

 

AtCoder Beginner Contest 189에 대한 해설입니다.

 

 * 이 글은 code-review 항목의 포스트입니다. code-review 항목에 대해 자세히 알아보고 싶다면, 클릭!

 * 문항 원문은 아래 주소에서 확인 가능합니다. AtCoder Beginner Contest 189

 - atcoder.jp/contests/abc189 [ 바로 가기 ]

 

[2021.01.23] 초판 발행

 

 AtCoder Beginner Contest 189에 대한 해설입니다. 실전에서는 A에서 E가찌만 풀고 F는 푸지 못했습니다. E번까지의 해설만 먼저 올리겠습니다.

 

[A번] Slot

 

[문제 및 풀이]

 

 주어진 세 글자의 문자가 동일한지 판단하는 문제이다.

 

[구현]

 

 문제에서 원하는 바를 잘 구현하면 된다.

 

[예시 답안]

 

#include <stdio.h>
 
int main() {
    char in[10];
 
    scanf("%s", in);
    printf("%s", (in[0] == in[1] && in[1] == in[2]) ? "Won" : "Lost");
 
    return 0;
}
 

 

[B번] Alcoholic

 

[문제 및 풀이]

 

 $N$개의 정수쌍이 주어질 때, 그 정수쌍의 곱을 $M$에서 빼어나갈 때 처음으로 $0$이 되는 지점을 찾는 문제이다.

 

[구현]

 

 문제에서 원하는 바를 잘 구현하면 된다.

 

 <유의 사항> 원래 문제는 정수쌍이 아니라 부피와 백분율로 주어진 농도가 제시된다. 만약 원래 문제대로 부피와 농도를 곱하고 $100$으로 나누는 방식으로 접근할 수 있다. 이렇게 구할 경우에는 부동소수점의 정밀도 문제가 주어지기 때문에, 초기 $M$에 $100$을 곱해서 정수만 처리하는 방식으로 해결하는 것이 좋다.

 

[예시 답안]

 

#include <stdio.h>
 
long long N, M;
 
int main() {
    long long i, a, b;
 
    scanf("%lld%lld", &N, &M);
    M *= 100;
 
    for (i = 0; i < N; i++) {
        scanf("%lld%lld", &a, &b);
        M -= (a*b);
        if (M < 0) break;
    }
 
    printf("%d", (i == N) ? -1 : i + 1);
 
    return 0;
}
 

 

[C번] Mandarin Orange

 

[문제 및 풀이]

 

 $N$개의 정수로 이루어진 수열이 주어진다. 이 수열의 특정 구간으로 잡았을 때 그 구간에 있는 최솟값과 구간에 있는 길이를 구하는 문제이다.

 

[구현]

 

 $N$ 제한이 작기 때문에, $O(N^2)$로 해결할 수 있다. 각 지점에서 최솟값을 갱신해나가면서, 최솟값과 구간의 길이를 구해가면서 갱신해나가면 된다.

 

[예시 답안]

 

#include <stdio.h>
 
int N;
long long Val, Ans;
long long d[15000];
 
int main() {
    int i, u;
    long long Min, Cnt;
 
    scanf("%d", &N);
    for (i = 0; i < N; i++) scanf("%lld", &d[i]);
 
    for (i = 0; i < N; i++) {
        Min = d[i];
        for (u = i, Cnt = 1; u < N; u++, Cnt++) Min = (Min < d[u]) ? Min : d[u], Ans = (Ans > Min*Cnt) ? Ans : Min * Cnt;
    }
 
    printf("%lld", Ans);
 
    return 0;
}
 

 

[D번] Logical Expression

 

[문제 및 풀이]

 

 $N$개의 논리 연산자(AND, OR)가 주어진다. 각 연산자 사이에 참이나 거짓을 넣었을 때, 논리식의 전체 값이 참이 되는 경우의 수를 구하는 문제이다.

 

 동적계획법(다이나믹 프로그래밍)으로 해결할 수 있다. $D[i][0]$는 $i$개의 값이 있을 때 참이 되는 경우의 수, $D[i][1]$는 $i$개의 값이 있을 때 거짓이 되는 경우의 수이다.

 

 $D[0][0]$과 $D[0][1]$은 $1$로 정의하고, 이후에는 연산자가 AND인자 OR인지에 따라서 다음과 같이 정의한다.

 

 1) AND인 경우

 $D[i+1][0] = D[i][0] \times 2 + D[i][1]$

 $D[i+1][1] = D[i][1]$

 

 1) OR인 경우

 $D[i+1][0] = D[i][0]$

 $D[i+1][0] = D[i][0] + D[i][1] \times 2$

 

 점화식은 $i$개의 항까지 완성된 논리식에 참을 넣은 경우와 거짓이 되는 경우를 추가했을 때, 만들어지는 $i+1$개의 항까지 완성된 논리식이 참이 되는지 거짓이 되는지르 생각해보면 이해할 수 있다.

 

[구현]

 

 해설에 있는 점화식을 구현하면 된다. $N$의 제한이 $60$이기 때문에 long long 자료형을 이용하면 해결할 수 있다.

 

[예시 답안]

 

#include <stdio.h>
#include <string.h>
 
int N;
char in[100][10];
long long D[100][2];
 
int main() {
    int i;
 
    scanf("%d", &N);
    for (i = 0; i < N; i++) scanf("%s", in[i]);
 
    D[0][0] = D[0][1] = 1;
    for (i = 0; i < N; i++) {
        if (!strcmp(in[i], "AND")) D[i + 1][0] = D[i][0] * 2 + D[i][1], D[i + 1][1] = D[i][1];
        else D[i + 1][0] = D[i][0], D[i + 1][1] = D[i][0] + D[i][1] * 2;
    }
 
    printf("%lld", D[N][1]);
 
    return 0;
}
 

 

[E번] Rotate and Flip

 

[문제 및 풀이]

 

 $N$개의 좌표와 $M$개의 변환이 주어진다. 이 때, 다음 쿼리(query)를 수행하는 문제이다.

 

$Q_ij$ : "$i$번째 변환까지 수행하였을 때, $j$번째 좌표의 변환 결과는 무엇인가?"

 

 여기서 주어지는 변환은 시계방향으로 90도 회전, 반시계방향으로 90도 회전, $x=a$에 대한 선대칭 변환과 $y=a$에 대한 선대칭 변환이다. 이 문제를 해결하기 위해서는 다음 두 가지 아이디어가 필요하다.

 

 1) 회전과 선대칭에 대한 기술해야 한다.

 

 $(x, y)$를 변환하면 다음 좌표로 변환된다.

 

 (a) 시계방향으로 90도 회전 : $(y, -x)$

 (b) 반시계방향으로 90도로 회전 : $(-x, y)$

 (c) $x=a$에 대한 선대칭 : $(2-x, y)$

 (d) $y=a$에 대한 선대칭 : $(x, 2-y)$

 

 2) 각 쿼리를 한 번에 해결할 수 있다.

 

 [접근 1] 오프라인 쿼리 (offline query)

  쿼리 $Q_ij$들을 $i$ 순서대로 변환을 한다. $i$번째 변환까지를 누적해서 계산한 $T$를 만들어 나간다. 그리고 $T$를 $j$번째 좌표에 작용한다. 그리고 쿼리를 원래 순서대로 정렬해서 출력한다.

 

 [접근 2] 특정 변환까지 수행한 결과를 배열에 저장

  $i$번째 수행한 변환을 $T_i$로 저장을 한다. 그리고 $T_i$를 $j$번째 좌표에 적용한다.

 

 일차변환을 잘 구현하는 것이 중요한 문제다.

 

 [Tip] (고등학교를 졸업한 지 너무 오래되어서) 변환식이 기억이 안 날 수 있다. 이 때에는 차분하게 좌표평면을 그리고 $(1,2)$를 찍고 표현해보자. 시계방향으로 90도 회전하면 $(2,-1)$로 간다. 이것을 바탕으로 $(x, y)$가 $(y, -x)$로 이동한다. (물론, 이걸 할려면 대략적인 모양은 기억 해야 한다.)

 

[구현]

 

 일차변환을 구현하는 부분이 상대적으로 어렵다. 이를 저장하기 위해서 (1) $x$와 $y$가 바뀌었는지, (2) $x$와 $y$의 부호와 (3) 선대칭 과정에서 더하고 빼는 상수를 저장해 나가면서 계산하였다. 물론 이 부분은 3차원 배열을 이용해서 구현할 수 있고, 이 부분은 AtCoder Editorial에 설명이 되어 있다.

 

[예시 답안]

 

* 이 코드는 [접근 1]에 따라 구현한 것이다.

 

#include <stdio.h>
#include <algorithm>
#define Max 250000
 
using namespace std;
 
struct query { long long i, t, p, x, y; };
struct cf1 { bool operator () (const query &A, const query &B) { return A.t < B.t; } };
struct cf2 { bool operator () (const query &A, const query &B) { return A.i < B.i; } };
 
struct num { long long N, C, xy; };
struct op { num X, Y; };
 
int N, M, Q;
long long d[Max][2], R[Max][2];
query q[Max];
 
int main() {
    int i, u;
    op A, B;
 
    scanf("%d", &N);
    for (i = 0; i < N; i++) scanf("%lld%lld", &d[i][0], &d[i][1]);
 
    scanf("%d", &M);
    for (i = 0; i < M; i++) {
        scanf("%lld", &R[i][0]);
        if (R[i][0] >= 3) scanf("%lld", &R[i][1]);
    }
 
    scanf("%d", &Q);
    for (i = 0; i < Q; q[i].i = i, q[i].p--, i++) scanf("%lld%lld", &q[i].t, &q[i].p);
    sort(q, q + Q, cf1());
 
    A.X.N = A.Y.N = 1, A.X.C = A.Y.C = 0, A.X.xy = 0, A.Y.xy = 1;
 
    for (u = 0; u < Q && q[u].t == 0; u++) q[u].x = d[q[u].p][0], q[u].y = d[q[u].p][1];
 
    for (i = 0; i < M; i++) {
        B = A;
 
        if (R[i][0] == 1) B.X = A.Y, B.Y = A.X, B.Y.N *= -1, B.Y.C *= -1, B.X.xy = A.Y.xy, B.Y.xy = A.X.xy;
        else if (R[i][0] == 2) B.X = A.Y, B.Y = A.X, B.X.N *= -1, B.X.C *= -1, B.X.xy = A.Y.xy, B.Y.xy = A.X.xy;
        else if (R[i][0] == 3) B.X.N *= -1, B.X.C = (R[i][1] * 2) - A.X.C;
        else if (R[i][0] == 4) B.Y.N *= -1, B.Y.C = (R[i][1] * 2) - A.Y.C;
 
        for (; u < Q && q[u].t == i + 1; u++) q[u].x = d[q[u].p][B.X.xy] * B.X.N + B.X.C, q[u].y = d[q[u].p][B.Y.xy] * B.Y.N + B.Y.C;
        A = B;
    }
 
    sort(q, q + Q, cf2());
    for (i = 0; i < Q; i++) printf("%lld %lld\n", q[i].x, q[i].y);
 
    return 0;
}
 

 

[F번] (작성 전)

 

[문제 및 풀이]

 

[구현]

 

[예시 답안]