A. Mocha and Math
문제 의역
모카는 고등학교를 다니는 소녀다. 그녀는 그녀의 선생님들에게 아주 흥미로운 지식을 배우는데, 그 중에서도 수학선생님이 가르쳐주는 지식이 가장 흥미롭다. 최근, 그녀는 이진법에 대해 배우고나서 이진 연산에 대해 깊은 흥미를 느꼈다.
오늘, 모카는 길이 n의 수열 a를 가지고 다음 작업을 원하는 만큼 수행할 것이다.
수열 a내의 임의의 구간 [l, r]을 설정 한 뒤, 구간안에 있는 모든 i에 대해 a[l + i]를 a[l + i] & a[r - i]로 대체한다.
&연산자는 AND 비트연산이다.
예를들어 길이 5 짜리 배열 [a1, a2, a3, a4, a5] 에 구간 [2, 5]를 선택한다면 연산의 결과는 다음과 같을 것이다.
[a1, a2 & a5, a3 & a4, a4 & a3, a5 & a2].
모카는 배열의 최댓값이 가장 작아지기를 바라고 있다. 그녀의 절친으로써 그녀가 답을 찾을 수 있도록 도와주자.
입력
각각의 테스트는 여러개의 테스트 케이스를 포함하고 있다.
첫 줄에는 테스트 케이스의 개수를 의미하는 t ( 1 <= t <= 100 ) 이 주어진다. 각각의 테스트 케이스마다 2 줄이 주어진다.
테스트 케이스의 첫 줄에는 정수 배열의 개수를 의미하는 n ( 1 <= n <= 100 ) 이 주어진다.
테스트 케이스의 두번 째 줄에는 a배열의 내용인 n개의 정수가 주어진다. 각각의 요소들은 1000000000 이하다.
출력
각각의 테스트 케이스마다 작업 후 나올 수 있는 가장 작은 최댓값을 출력한다.
풀이
배열의 모든 값을 AND한 값을 출력하면 된다.
배열 값을 비트로 나열했을 때 한 자리라도 0이라면 모든 배열 요소들의 해당 자리를 0으로 만들 수 있다.
작업 횟수에 제한도 없으므로 자명하다.
코드
void A() {
int tc; cin >> tc;
while (tc--) {
int n; cin >> n;
int c1; cin >> c1;
for (int i = 2; i <= n; i++) {
int c; cin >> c;
c1 &= c;
}
cout << c1 << "\n";
}
}
B. Mocha and Red and Blue
문제 의역
그들의 이야기가 풀려나자 시대를 초월한 전설이 다시 한번 전해진다...
모카의 친구인 시라하임은 최근 아르케아라는 리겜에 빠져사는데 거기서 나오는 흥미로운 퍼즐들을 모카와 공유해서 풀고 있다. 시라하임은 새로운 퍼즐을 모카에게 풀라고 가져다 주었다. 하지만 이 퍼즐들은 모카에겐 너무 쉬웠다.
그래서 그녀는 당신이 그녀 대신 시라하임에게 정답을 말해주길 바란다.
퍼즐은 다음과 같다.
n개의 사각형들이 횡으로 나열되어있고 빨간색 혹은 파란색으로 칠 할 수 있다.
이 사각형들 중, 이미 색칠되어 있는 것들도 있고 아직 색이 칠해지지 않은 것들도 있다. 아직 칠해지지 않은 사각형들의 색을 정해야 한다.
인접한 두 쌍의 사각형이 같은 색으로 칠해져있다면 이것을 불완전한 것으로 판정한다.
예를들면 BRRRBBR의 불완전 점수는 총 3이다. BB가 1번, RR이 2번 나왔기 때문이다.
우리는 이러한 불완전한 쌍들을 최대한 줄여야한다.
입력
각각의 테스트는 여러개의 테스트 케이스로 이루어져있다.
첫 줄에는 테스트 케이스의 개수를 의미하는 t ( 1 <= t <= 100 ) 가 주어진다.
각각의 테스트 케이스마다 2개 줄의 입력이 주어진다.
첫 줄에는 사각형들의 개수 n ( 1 <= n <= 100 ) 이 주어진다.
두번 째 줄에는 길이가 n인 문자열 s가 주어진다. 이 문자열은 'B', 'R', '?' 로만 이루어져있다.
B는 파랑을 의미하며 R은 빨강을, ?은 아직 칠해지지 않은 사각형을 의미한다.
출력
각각의 테스트 케이스에 대해서 불완전 점수가 최소인 'B'와 'R'로만 이루어진 문자열을 출력한다.
만약 이러한 문자열이 여러개 있다면 그 중 아무것이나 출력한다.
입출력 예제
| input |
| 5 7 ?R???BR 7 ???R??? 1 ? 1 B 10 ?R??RB??B? |
| output |
| BRRBRBR BRBRBRB B B BRRBRBBRBR |
풀이
어차피 어떻게 채우던 같은 색깔을 일부러 넣는 경우가 아니라면 불완전 점수는 일정하다.
인접한 블럭들을 보면서 ?칸들을 채우기만하면 된다.
코드
void B() {
int tc; cin >> tc;
while (tc--) {
int n; cin >> n; vector<int> arr(n + 1);
string s; cin >> s;
if (n == 1) {
if (s == "?") cout << 'B' << "\n";
else cout << s << "\n";
continue;
}
for (int i = 1; i <= n; i++) {
switch (s[i - 1]) {
case 'R':
arr[i] = 1;
break;
case 'B':
arr[i] = 2;
break;
case '?':
if (arr[i - 1] == 0) break;
arr[i] = 3 - arr[i - 1];
break;
}
}
int inci = 0;
for (int i = 1; i <= n; i++) {
if (arr[i] != 0) break;
inci = i;
}
if (inci == n) {
inci -= 1;
arr[n] = 2;
}
for (int i = inci; i >= 1; i--) {
arr[i] = 3 - arr[i + 1];
}
for (int i = 1; i <= n; i++) {
if (arr[i] == 1) cout << 'R';
else cout << 'B';
}
cout << "\n";
}
}
C. Mocha and Hiking
문제 의역
모카가 사는 도시는 지지양이라는 도시다. 지지양에는 n + 1개의 마을과 2n - 1개의 방향 도로들이 있다.
2가지 종류의 길들이 있다.
첫 번째 종류의 길들은 총 n - 1개가 있는데 모두 i ( 1 <= i <= n - 1 )번째 마을에서 i + 1번째 마을로 갈 수 있는 도로들이다.
두 번째 종류의 길들은 0과 1로 이루어진 수열 a에 대해 a[i]가 0인 경우, i 번째 마을에서 n + 1번 마을로 갈 수 있는 도로이고,
1인 경우에는 n + 1번 마을에서 i번 마을로 오는 도로 이다. ( 1 <= i <= n )
모카는 이번주 주말에 타키와 함께 등산을 가기로 했다. 둘은 여행이 지루해지는 것을 피하기 위해 모든 마을에 정확히 한번씩만 방문하기로 했다.
여해은 어느 마을에서든 시작하고 끝낼 수 있다. 그들을 도와 여행계획을 작성해주자.
입력
입력은 여러 개의 테스트 케이스로 이루어져있다.
첫 줄에 테스트 케이스의 개수 t ( 1 <= t <= 20 )이 주어진다. 각각의 테스트 케이스는 2 줄로 이루어져 있다.
테스트 케이스의 첫 줄에 마을의 개수 n ( 1 <= n <= 10000 )이 주어진다. 정확한 마을의 개수는 n + 1임에 유의
테스트 케이스의 두 번째 줄에는 도로의 종류를 의미하는 배열 a가 주어진다. a배열은 0과 1로만 이루어져 있다.
모든 테스트 케이스의 n의 합이 10000을 넘지 않음이 보장된다.
출력
각각의 테스트 케이스에 대해 모카와 타키가 방문하는 마을들을 순서대로 출력한다.
만약 정답이 없을 경우 -1을 출력한다.
정답이 여러개 있을 경우, 그 중 아무거나 출력한다.
풀이
처음보고 TSP인데 정점이 10000개인 줄 알았다.
도로가 1번 - n번까지는 항상 일방통행이 가능하므로 개념적인 정점은 3개다. ( 1~k정점, k~n정점, n + 1정점 )
1. 1번 마을 -> n + 1번 마을까지 순환이 가능한 경우
2. 1번 마을 -> k번 마을 -> n + 1번 마을 -> k + 1번 마을 -> n번 마을
3. n + 1번마을 -> 1번마을 -> n번 마을까지 순환
각각의 경우마다 a정점을 순환하며 가능 여부를 검사 할 수 있다.
조건은 다음과 같다.
1. a[n] == 0
2. a[k - 1] == 0 && a[k] == 1 ( 단, k > 1 )
3. a[1] == 1
코드
void C() {
int tc; cin >> tc;
while (tc--) {
int n; cin >> n; vector<int> arr(n + 1);
for (int i = 1; i <= n; i++) {
cin >> arr[i];
}
bool sign = false;
for (int i = 1; i <= n; i++) {
int imsi = arr[i];
int prev = arr[i - 1];
if (prev == 0 && imsi == 1 && i != 1) {
for (int j = 1; j < i; j++) {
cout << j << " ";
}
cout << n + 1 << " ";
for (int j = i; j <= n; j++) {
cout << j << " ";
}
cout << "\n";
sign = true;
break;
}
if (i == n && imsi == 0) {
for (int i = 1; i <= n; i++) {
cout << i << " ";
}
cout << n + 1 << "\n";
sign = true;
}
if (i == 1 && imsi == 1) {
cout << n + 1 << " ";
for (int i = 1; i <= n; i++) {
cout << i << " ";
}
cout << "\n";
sign = true;
break;
}
}
if (sign) continue;
cout << -1 << "\n";
}
}
D1. Mocha and Diana (Easy Version)
문제의역
숲은 사이클이 없는 무방향 그래프다. ( 모든 정점이 연결되어 있을 필요는 없다. )
모카와 다이애나는 각자 정점이 n개인 자기만의 숲을 가지고 있다. 그들은 자기 숲에 다음 조건을 만족하는 간선을 추가하고 싶다.
1. 간선을 추가한 뒤에도 그래프가 숲의 특성을 유지해야 한다.
2. 둘은 같은 간선을 추가해야 한다. 예를들어 한명이 정점 (u, v) 사이에 간선을 추가했다면 다른 한명도 똑같이 (u, v)에 간선을 추가해야 한다.
모카와 다이애나는 그들이 추가할 수 있는 간선의 수의 최댓값과, 어떤 간선을 추가해야 하는지 알고싶다.
입력
첫 줄에는 숲의 정점수 n(1 <= n <= 1000)과 모카의 숲의 간선 수 m1(1 <= m1 < n) 다이애나의 숲의 간선 수 m2(1 <= m2 < n)이 주어진다.
다음 m1줄에는 모카의 숲에 있는 간선들을 나타내는 2개의 정수 u, v(1 <= u, v <= n, u != v)가 주어진다.
다음 m2줄에는 다이애나의 숲에 있는 간선들을 나타내는 2개의 정수 u, v(1 <= u, v <= n, u != v)가 주어진다.
출력
첫 줄에는 추가할 수 있는 간선 수의 최댓값 h을 출력한다.
다음 h줄에는 추가해야하는 정점 u, v를 순서대로 출력한다.
만약 답이 여러 개일 경우, 그 중 아무거나 출력한다.
풀이
Union-Find 문제다. 2개의 배열에 각각 모카와 다이애나의 정점 부모들을 저장하고
무작위로 2개의 정점을 골랐을 때 두 그래프에서 모두 부모가 다르다면 해당 간선을 추가한다.
정점들을 모두 검사하므로 O(n^2) 알고리즘이다. n의 최대가 1000이므로 충분히 시간안에 동작할 수 있다.
코드
int p1[100001];
int p2[100001];
struct p {
int n1, n2;
};
int findp1(int x) {
if (p1[x] == x) return x;
else return p1[x] = findp1(p1[x]);
}
int findp2(int x) {
if (p2[x] == x) return x;
else return p2[x] = findp2(p2[x]);
}
void Deasy() {
int n, m1, m2; cin >> n >> m1 >> m2;
for (int i = 1; i <= n; i++) {
p1[i] = i;
p2[i] = i;
}
for (int i = 1; i <= m1; i++) {
int s, e; cin >> s >> e;
int p11 = findp1(s);
int p12 = findp2(e);
p1[p11] = p12;
}
for (int i = 1; i <= m2; i++) {
int s, e; cin >> s >> e;
int p21 = findp2(s);
int p22 = findp2(e);
p2[p21] = p22;
}
vector<p> dap;
for (int i = 1; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
int p11 = findp1(i);
int p12 = findp1(j);
int p21 = findp2(i);
int p22 = findp2(j);
if (p11 != p12 && p21 != p22) {
dap.push_back({ i, j });
p1[p12] = p11;
p2[p22] = p21;
}
}
}
cout << dap.size() << "\n";
for (auto v : dap) {
cout << v.n1 << " " << v.n2 << "\n";
}
}
D2 / E는 너무 어려워서 포기
'Algorithm > CodeForce Round Write-Up' 카테고리의 다른 글
| CodeForces #899 (Div. 2) Write-Up (A ~ D) 작성중. (0) | 2023.10.08 |
|---|---|
| CodeForces #742 (Div. 2) Write-Up (A - E) (0) | 2021.10.05 |