A. Domino Disaster
문제 의역
엘리스에게 2개의 행과 n개의 열로 이루어진 격자가 있다. 그녀는 그 격자들을 N개의 1 X 2 크기의 도미노로 모두 덮고 싶다. 엘리스는 도미노를 마음대로 회전시켜 배치할 수 있다. 하지만 도미노가 서로 겹치게 배치할 수는 없다.
격자판을 모두 덮은 후, 엘리스는 밥에게 격자판의 두 행 중, 하나를 보여줬다. 밥을 도와서 격자판의 나머지 부분들을 맞춰보자!
입력
입력은 여러 개의 Test Case로 이루어져 있다. 첫번 째 줄에 정수 t ( 1 <= t <= 5000 ) 테스트 케이스의 갯수가 주어진다. 이하 각각의 테스트 케이스에 대한 입력 형식이다.
첫 줄에 정수 n ( 1 <= n <= 100 ) 격자판의 넓이가 주어진다.
두번째 줄에는 n개의 문자로 이루어진 문자열 s가 주어진다. 문자열은 L, R, U, D로 이루어져 있으며 각각 도미노의 왼쪽, 오른쪽, 위쪽, 아랫쪽을 의미한다. 이 문자열은 도미노 격자판의 위쪽이나 아래쪽을 의미한다.
불가능한 도미노 배열은 입력으로 주어지지 않는다.
출력
각각의 테스트 케이스에 대해서 한 줄의 문자열을 출력한다 : 입력으로 주어진 격자판의 니머지 부분에 해당하는 도미노 를 L, R, U, D 를 적절히 조합하여 출력한다.
입출력 예시
| input |
| 4 1 U 2 LR 5 LRDLR 6 UUUUUU |
| output |
| D LR LRULR DDDDDD |
풀이
각각의 열에 대해서 대응하는 부분을 출력한다.
L 혹은 R 인경우, 해당 도미노는 횡 방향으로 누워있는 상태다.
입력된 문자열을 보며 L/R인 경우 그대로 출력하고 U/D인 경우, 반대 문자열을 출력한다.
코드
#define _CRT_SECURE_NO_WARNGINS
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <cstdio>
#include <string>
using namespace std;
int main()
{
int tc; cin >> tc;
while (tc--) {
int n; cin >> n;
string s; cin >> s;
for (auto v : s) {
if (v == 'L' || v == 'R') {
cout << v;
}
else if (v == 'D') {
cout << 'U';
}
else if (v == 'U') {
cout << 'D';
}
}
cout << "\n";
}
return 0;
}
B. MEXor Mixup
문제 의역
엘리스는 밥에게 두 정수 a와 b(a > 0 and b>= 0) 를 줬다. 밥은 호기심이 많아서 MEX값이 a이고 XOR값이 b인 0 이상인 정수 배열을 적어보았다.
밥이 적은 정수 배열 중, 가장 짧은 배열이 무엇일까?
배열의 MEX 값은 배열에 포함되지 않은 0 이상의 정수 중, 가장 작은 값을 의미한다.
예를 들면 [ 0, 2, 3, 5, 10 ] 에서 MEX 값은 1이다.
입력
입력은 여러개의 테스트 케이스로 주어진다. 첫 줄은 테스트 케이스의 수를 의미하는 정수 t ( 1<= t <= 50000 ) 가 주어진다. 각 테스트 케이스에 대한 설명은 아래와 같다:
각 줄마다 배열의 MEX값과 XOR값인 정수 a와 b ( 1 <= a <= 300000 . 0 <= b <= 300000 ) 가 주어진다.
출력
각각의 테스트 케이스에 대해서 밥이 쓸 수 있는 정수 배열의 길이 중 가장 작은 것을 출력한다. 배열이 항상 존재하는 것이 자명하다.
입출력 예시
| input |
| 5 1 1 2 1 2 0 1 10000 2 10000 |
| output |
| 3 2 3 2 3 |
풀이
MEX 값인 a까지는 모든 정수가 존재해야 하므로 최소 a개의 정수가 필요하다.
a까지의 XOR값에 따라서 출력이 달라진다. 아래에서 XOR(0~a) 값을 c라 하겠다.
i) c == b
이 경우, 별도의 숫자가 필요하지 않다.
ii) (c ^ b) == a
이 경우, MEX값을 유지하기 위해 a값을 사용할 수 없다. 따라서 추가적으로 2개의 숫자가 더 필요하다.
iii) 이 외 경우
이 경우, c ^ b 값을 배열에 추가하면 된다. 추가적으로 1개의 숫자가 더 필요하다.
코드
void B() {
vector<int> xlist(300001);
int c = 0;
for (int i = 1; i <= 300000; i++) {
c ^= i;
xlist[i] = c;
}
int tc; cin >> tc;
while (tc--) {
int a, b; cin >> a >> b;
int c = xlist[a - 1];
if (c == b) cout << a << "\n";
else if ((c ^ b) == a) cout << a + 2 << "\n";
else cout << a + 1 << "\n";
}
}
C. Carrying Conundrum
문제 의역
엘리스는 방금 덧셈을 배웠다. 하지만 아직 '자리올림'에 대해서는 완전하게 이해하지 못했다. 그래서 발생한 자리올림을 다음 자리가 아닌 다다음 자리에 더해 계산한다. 즉, 1의 자리에서 발생한 자리올림을 10의 자리가 아닌 100의 자리에 계산하는 것이다.
예를들어 통상적인 방법으로 2039 + 2976 을 계산하면 다음 과 같다.
하지만 엘리스는 이렇게 계산한다.
계산 과정을 순서대로 설명하면 다음과 같다.
1. 9 + 6 을 계산하여 15를 만든다. 자리올림 1이 발생하였으므로 2 자리 올려 0 + 9 를 계산할 때 포함하여 계산한다.
2. 3 + 7 을 계산하여 10을 만든다. 자리올림 1이 발생하였으므로 2 자리 올려 2 + 2 를 계산할 때 포함하여 계산한다.
3. 0 + 9 + 1을 계산하여 10을 만든다. 자리올림 1이 발생하였으므로 2 자리 올려 + 기호 위에 포함하여 계산한다.
4. 1 + 2 + 2를 계산하여 5를 만든다.
5. 1을 계산하여 1을 만든다.
이렇게 최종 계산 결과 15005로 오답이 나오게 된다.
엘리스는 밥에게 위의 방법대로 계산하여 결과로 n을 얻었다고 말했다. 밥은 그녀가 자신만의 방식으로 덧셈을 한다는 사실을 알고 있다. 밥을 도와서 해당 결과가 나올 수 있는 숫자 쌍의 개수를 찾아보자. 숫자 쌍을 셀 때, 순서가 다른 쌍은 서로 다른 쌍으로 취급한다. ( (a, b) != (b, a) )
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 첫 줄에 테스트 케이스의 수 t (1 <= t <= 1000) 이 주어진다. 각각의 테스트 케이스에 대한 설명은 다음과 같다.
각 줄마다 엘리스가 밥에게 보여준 숫자 n ( 2 <= ㅜ <= 1000000000 ) 이 주어진다.
출력
각 테스트 케이스마다 하나의 정수를 출력한다. 엘리스의 방식대로 더했을 때 n이 되는 양수 숫자쌍의 갯수를 출력한다.
입출력 예시
| input |
| 5 100 12 8 2021 10000 |
| output |
| 9 4 7 44 99 |
풀이
엘리스의 방식대로 숫자를 더할 때 얼핏 보면 하나의 수를 더하는 것 같지만
짝수 번 째 자리와 홀수 번 째 자리가 서로 전혀 영향이 없다.
즉 일반적인 수 2개를 자리를 번갈아 만들어 놓은 숫자라는 것이다.
예를 들면 15005를 봤을 때 105와 50으로 나누어서 보면 된다.
예제에서 주어진 숫자 2039와 2976도 마찬가지로 나누면 각각 ( 9, 23 ) 와 ( 96, 27 ) 이 되고
이를 각각 더하면 50과 105가 나온다.
각각의 수를 a와 b라고 했을 때 a를 만들 수 있는 수의 쌍은 0~a까지 총 a + 1개이고
b 또한 마찬가지로 총 b + 1개다. 이 둘을 곱하면 총 (a + 1)(b + 1) 개의 가짓수가 나온다.
이것은 (0, a + b), (a + b, 0) 까지 합친 결과이므로 총 가짓수에서 2를 빼면 답이 나온다.
코드
void C() {
int tc; cin >> tc;
while (tc--) {
int n; cin >> n;
int j = n;
vector<short> t, o;
bool iso = true;
while (j > 0) {
if (iso) {
o.push_back(j % 10);
}
else {
t.push_back(j % 10);
}
iso = !iso;
j /= 10;
}
int so = 0;
int st = 0;
int combi = 1;
for (auto v : o) {
so += v * combi;
combi *= 10;
}
combi = 1;
for (auto v : t) {
st += v * combi;
combi *= 10;
}
cout << (so + 1) * (st + 1) - 2 << "\n";
}
}
D. Expression Evaluation Error
문제 의역
밥은 칠판에 합이 s인 n개의 양의 정수들을 10진수로 썼다. 엘리스가 그걸 보고 실수로 그 수들을 11진수라고 생각하고 그 수들을 11 진수 방식으로 더했다. 밥이 칠판에 어떤 수들을 써야 엘리스가 가장 큰 합을 얻을까?
입력
입력은 여러개의 테스트 케이스로 이루어져 있다. 첫 줄에 테스트 케이스의 개수 tc가 주어진다. 각각의 테스트 케이스에 대한 설명은 다음과 같다.
각 줄마다 수들의 10진수 합 s ( 1 <= s <= 1000000000 ) 와 칠판에 적은 수 개수 n ( 1 <= n <= min(100, s) ) 이 주어진다.
출력
각각의 케이스에 대해 엘리스가 구한 합이 최대가 되는 n개의 양의 정수들을 출력한다. 답이 여러가지일 경우, 그 중 아무거나 출력한다.
입출력 예시
| input |
| 6 97 2 17 1 111 4 100 2 10 9 999999 3 |
| output |
| 70 27 17 3 4 100 4 10 90 1 1 2 1 1 1 1 1 1 999900 90 9 |
풀이
10진수를 11진수로 취급해 더할 때 차이가 발생하는 부분은 자리올림이다.
자리올림이 발생할 때 마다, 전체 합이 자리올림이 발생한 자릿수 만큼 줄어든다.
따라서 우리는 수를 적을 때 자리올림이 최소가 되도록 수 n을 분할할 필요가 있다.
즉 각 자리 숫자의 합만큼은 자리올림이 전혀 발생하지 않도록 할 수 있다.
그 이상 분할할 때는 처음 말한 내용을 고려해야 한다.
자리 올림이 10의 자리에서 발생할 때 합은 총 10이 줄어들지만 100의 자리에서 발생할 때는 100이 줄어든다.
110을 3개로 나눌 때, 100 + 9 + 1 로 나누면 11진수로 10A가 되지만 10 + 10 + 90 으로 나누면 11진수로 AA가 된다.
즉, 이미 분할된 수들 중 작은것 부터 먼저 분할하는 것이 이득이다.
수들을 분할하여 우선순위 큐에 삽입하고 다시 가장 작은 원소를 출력해 분할하는 방식으로 코딩했다.
코드
void D() {
int tc; cin >> tc;
while (tc--) {
int s, n; cin >> s >> n;
priority_queue<int, vector<int>, cmp> q;
q.push(s);
for (int i = 1; i < n; i++) {
auto cur = q.top(); q.pop();
if (cur == 1) {
n++;
cout << 1 << " ";
continue;
}
int v = getmin10(cur);
q.push(cur - v);
q.push(v);
}
while (!q.empty()) {
cout << q.top() << " ";
q.pop();
}
cout << "\n";
}
}
D. Non-Decreasing Dilemma
문제의역
엘리스는 최근 생일선물로 n개의 정수 배열 a를 선물로 받았다. 그녀는 자신이 받은 정수 배열이 매우 자랑스러워서 그녀의 친구인 밥에게 배열을 보여줬고 밥도 그녀의 선물을 보고 함께 좋아해줬다. 하지만 곧 밥은 정상인이라면 당연히 가질만한 의문이 생겼고, 엘리스에게 2 종류의 q개의 쿼리들을 그녀의 배열에 실행해 볼 것을 권유했다.
1. 1 x y : x번째 인덱스에 있는 정수를 y로 업데이트한다.
2. 2 l r : 인덱스 l과 r사이의 감소하지 않는 부분수열의 개수를 구한다. 더 정확하게 말하자면,
l <= p <= q <= r 이며 a[p] <= a[p + 1] <= ... <= a[q - 1] <= a[q - 1]을 만족하는 쌍 (p, q)의 개수를 구한다.
엘리스를 도와 밥의 쿼리에 대한 답을 구해보자!
( 문제 지문 의미 자체가 이상해서 의역해도 이래 나옴 )
입력
첫 줄에 배열의 크기 n 과 쿼리 개수 q가 주어진다. ( 1 <= n, q <= 200,000 )
두 번째 줄에 배열 a에 해당하는 정수들이 주어진다. 각 요소들은 1000,000,000 보다 작거나 같다.
다음 q 개의 줄에는 각각 3개의 정수들이 주어진다.
첫 번째 정수 t는 쿼리의 종류를 의미한다. 1 또는 2만 주어진다.
t가 1인 경우 : 두 번째와 세 번째 주어지는 정수 x와 y로 다음 연산을 실행한다 : a 배열의 x번째 인덱스에 있는 정수를 y로 업데이트한다.
t가 2인 경우 : 두 번째와 세번쨰 주어지는 정수 x와 y로 다음 연산을 실행한다 : 인덱스 l과 r사이의 감소하지 않는 부분수열의 개수를 구한다. 더 정확하게 말하자면, l <= p <= q <= r 이며 a[p] <= a[p + 1] <= ... <= a[q - 1] <= a[q - 1]을 만족하는 쌍 (p, q)의 개수를 구한다.
2번 연산이 최소 하나 이상 있음이 보장된다.
출력
주어진 모든 2번 연산의 정답을 출력한다.
입출력 예제
| input |
| 5 6 3 1 4 1 5 2 2 5 2 1 3 1 4 4 2 2 5 1 2 6 2 2 5 |
| output |
| 6 4 10 7 |
풀이
세그먼트 트리를 사용해서 풀이하면 된다.
각 구간마다 다음 항목들을 저장한다.
1. 구간의 왼쪽, 오른쪽 수 : l, r
2. 각각 왼쪽, 오른쪽부터 봤을 때 감소하지 않는 배열의 길이 ( 예: 1 3 4 2 6 의 경우, 왼쪽부터 1 3 4 까지 감소하지 않는 배열에 해당하므로 3 저장, 오른쪽부터 2 6까지 감소하지 않는 배열에 해당하므로 2 저장 ) : llen, rlen
3. 구간 길이 : tlen
4. 구간에 있는 모든 감소하지 않는 배열의 갯수의 합 : cnt
세그먼트 트리의 기본적인 부분들은 차치하고 업데이트하는 부분과 두 구간을 합치는 부분만 살펴보겠다.
연속하는 두 구간 p1 , p2에 대해
1. 합친 구간에 있는 모든 감소하지 않는 배열의 개수는 기본적으로 두 구간의 합인 p1.cnt + p2.cnt 이며
p1.r <= p2.l인 경우 두 구간의 중간 수열이 합쳐져 (p1.rlen * p2.llen)개의 감소하지 않는 수열이 추가로 생긴다.
2. 합칠 때 llen과 rlen을 갱신하는 경우 다음과 같은 경우들을 고려한다.
i) p1.r <= p2.l && p1.tlen == p1.rlen
왼쪽 구간 p1이 전부 감소하지 않는 수열인 경우, 합친 수열의 llen은 p1.tlen + p2.llen이다.
ii) p1.r <= p2.l && p2.tlen == p2.llen
마찬가지로 p2이 전부 감소하지 않는 수열인 경우, 합친 수열의 rlen은 p2.tlen + p1.rlen이다.
ii) 그 외의 경우에는 p1.llen 과 p2.rlen 의 값은 합친 구간에서도 그대로 유지한다.
3. 합친 구간의 l과 r 은 p1.l과 p2.r이다. 자명하다.
코드
struct node {
int l, r, llen, rlen, tlen;//왼쪽 숫자, 오른쪽 숫자, 왼쪽 시작 증가 수열 길이, 오른쪽 시작 증가 수열 길이
long long cnt;//해당 노드에 포함된 총합 갯수
};
node init(vector<int>& a, vector<node>& tree, int n, int s, int e) {
if (s == e) {
return tree[n] = { a[s], a[s], 1, 1, 1, 1 };
}
else {
int mid = (s + e) / 2;
auto ln = init(a, tree, n * 2, s, mid);
auto rn = init(a, tree, n * 2 + 1, mid + 1, e);
long long dap = ln.cnt + rn.cnt;
int llen = ln.llen;
int rlen = rn.rlen;
if (ln.r <= rn.l) {
dap += (long long)rn.llen * (long long)ln.rlen;
if (ln.llen == ln.tlen) {
llen += rn.llen;
}
if (rn.rlen == rn.tlen) {
rlen += ln.rlen;
}
}
return tree[n] = { ln.l, rn.r, llen, rlen, ln.tlen + rn.tlen, dap };
}
}
node update(vector<node>& tree, int n, int s, int e, int index, int val) {
if (index < s || index > e) return tree[n];// update 작업에서 범위를 벗어난 인덱스가 들어올 경우, 업데이트 된 부분과 병합을 진행해야함
if (s != e) {
int mid = (s + e) / 2;
node ln = update(tree, n * 2, s, mid, index, val);
node rn = update(tree, n * 2 + 1, mid + 1, e, index, val);
long long dap = ln.cnt + rn.cnt;
int llen = ln.llen;
int rlen = rn.rlen;
if (ln.r <= rn.l) {
dap += (long long)rn.llen * (long long)ln.rlen;
if (ln.llen == ln.tlen) {
llen += rn.llen;
}
if (rn.rlen == rn.tlen) {
rlen += ln.rlen;
}
}
return tree[n] = { ln.l, rn.r, llen, rlen, ln.tlen + rn.tlen, dap };
}
else return tree[n] = { val, val, 1, 1, 1, 1 };
}
node calc(vector<node>& tree, int n, int s, int e, int l, int r) {
if (l > e || r < s) return { 0, 0, 0, 0, 0, 0 };
if (l <= s && e <= r) return tree[n];
int mid = (s + e) / 2;
node ln = calc(tree, n * 2, s, mid, l, r);
node rn = calc(tree, n * 2 + 1, mid + 1, e, l, r);
if (ln.tlen == 0) {
return rn;
}
if (rn.tlen == 0) {
return ln;
}
long long dap = ln.cnt + rn.cnt;
int llen = ln.llen;
int rlen = rn.rlen;
if (ln.r <= rn.l) {
dap += (long long)rn.llen * (long long)ln.rlen;
if (ln.llen == ln.tlen) {
llen += rn.llen;
}
if (rn.rlen == rn.tlen) {
rlen += ln.rlen;
}
}
return { ln.l, rn.r, llen, rlen, ln.tlen + rn.tlen, dap };
}
void E() {
int n, qcnt; cin >> n >> qcnt;
vector<int> arr(n + 1);
int h = ceil(log2(n)) + 1;
vector<node> sgtree((1 << h) + 1);
for (int i = 1; i <= n; i++) { scanf("%d", &arr[i]); }
init(arr, sgtree, 1, 1, n);
while (qcnt--) {
int type, a, b; cin >> type >> a >> b;
switch (type) {
case 1:
update(sgtree, 1, 1, n, a, b);
break;
case 2:
printf("%lld\n", calc(sgtree, 1, 1, n, a, b).cnt);
break;
}
}
}'Algorithm > CodeForce Round Write-Up' 카테고리의 다른 글
| CodeForces #899 (Div. 2) Write-Up (A ~ D) 작성중. (0) | 2023.10.08 |
|---|---|
| CodeForces #738 (Div. 2) Write-Up (A ~ D1) (0) | 2021.10.13 |