Codeforces Round #692 (Div. 2) A~D
오늘도 코드포스 버추얼을 치고 풀이를 쓴다. D번 하나 하루종일 업솔빙하다가 결국 Lawali님의 코드 그리고 Gravekper님의 풀이 영상을 보고 이해할 수 있었다.
A. In-Game Chat
그냥 문자열 끝에 있는 닫는 괄호의 개수를 세주고, 나머지 문자의 수와 비교해 주면 되는 문제다.
#include <iostream>
#include <vector>
#include <list>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <cmath>
typedef long long ll;
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int tc;
cin >> tc;
for (int z = 0; z < tc; z++) {
int n, cnt = 0;
char s[105];
cin >> n >> s;
for (int i = n - 1; s[i] == ')'; i--) {
cnt++;
}
if (cnt > n - cnt) { cout << "Yes\n"; }
else { cout << "No\n"; }
}
return 0;
}
B. Fair Numbers
어떤 숫자가 0을 제외한 그 자릿수들로 다 나누어떨어질 때 fair하다고 한다. 가령 288은 fair하다고 할 수 있다. 2와 8로 나누어떨어지기 때문이다. 마찬가지로 123도 fair하다. 1,2,3으로 각각 나누어떨어지기 때문이다. 반면 125는 fair하지 않은데, 2로 나누어떨어지지 않기 때문이다.
문제는 n이 주어지면 n보다 크거나 같은 수 중에서 가장 작은 fair number를 찾는 문제다. n의 제한도 10^18 이고, 언뜻 보기에 쉽지 않아 보인다. 하지만 사실은 1,2,3,4,5,6,7,8,9의 최소공배수가 2520이기 때문에, 무조건 2520개 간격으로 fair number가 나온다. 따라서 그냥 n에서 1씩 숫자를 늘려 나가면서 fair한지 체크하기만 해도 시간제한 내에 풀린다. 나는 쓸데없이 pow함수 같은 걸 구현해서 코드가 좀 더럽다.
#include <iostream>
#include <vector>
#include <list>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <cmath>
typedef long long ll;
using namespace std;
ll p(ll a, ll b) {
ll r = 1;
for (int i = 0; i < b; i++) {
r *= a;
}
return r;
}
ll check(ll num) {
ll tmp = num;
for (ll i = 18; i >= 0; i--) {
ll digit;
if (i == 0) { digit = tmp; }
else { digit = tmp / (p(10, i)); tmp %= p(10, i);}
//cout << digit << "\n";
if (digit != 0 && num % digit != 0) { return 0; }
}
return 1; //만약 fair하면 1 리턴
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int tc;
cin >> tc;
for (int z = 0; z < tc; z++) {
ll n;
cin >> n;
while (check(n) == 0) {
n++;
}
cout << n << "\n";
}
return 0;
}
C. Peaceful Rooks
가로세로 n인 체스판이 있고, 거기에 m(m<n)개의 룩들이 놓여 있다. 룩은 체스 규칙과 같이 상하좌우로 이동할 수 있다. 이때 체스판 위에 놓여 있는 룩들을 '최소한의 횟수만' 움직여서 모두 체스판의 main diagonal((1,1)에서 (n,n)칸을 잇는 대각선)위에 위치하도록 하면 된다. 단 조건이 있는데, 룩이 이동할 때 다른 룩에게 공격할 수 있는 기회를 주면 안 된다는 것이다. 또한 룩의 처음 배치는 서로 공격할 수 없는 위치로 되어 있다.
룩의 초기 위치는 서로 공격할 수 없도록 배치되어 있다고 했으므로 각각의 룩은 1번의 이동으로 대각선상으로 이동할 수 있다. 가령 (a,b)의 룩은 (a,a)으로 그냥 이동하면 되는 것이다. 문제는 그 (a,a)가 다른 룩에게 공격당할 수 있는 위치에 있으면 어떻게 할지가 문제이다. 가령 3x3 체스판에 룩이 다음과 같이 배치되어 있다 하자.
두 룩 모두 (1,1)이나 (2,2)로 이동할 수 있지만 그러면 다른 룩의 공격에 노출된다. 이런 경우 두 룩 중 하나를 3번째 행으로 보내는 등 잠깐 빈 공간으로 빼놓는 이동 1번이 더 필요해진다. 즉,
- 모든 룩은 초기 상태에서 1번의 이동으로 대각선상에 갈 수 있다.
- 그러나 이동하려는 행/열에 다른 룩이 있을 경우 1번의 이동이 더 필요해진다.
이는 체스판 위의 좌표들을 그래프로 해석해서 풀 수 있다. (a,b)에 위치한 룩을 a정점에서 b정점으로 가는 간선으로 해석하는 것이다. 그리고 잘 생각해 보면 정점들이 사이클을 이룰 때 교착 상태에 빠져서 1번의 이동이 더 필요해짐을 알 수 있다. 위 그림에서도 (1,2)와 (2,1)간선으로 이루어진 사이클이 있으므로 1번의 이동이 더 필요한 것이다.
그럼 기본적으로 모든 룩에 1번의 이동을 할당해 주고 룩들이 사이클을 이룰 때만 1번씩의 이동을 추가해 주면 된다. 사이클을 찾는 건 disjoint set으로 간단하게 가능하다.
#include <iostream>
#include <vector>
#include <list>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <cmath>
typedef long long ll;
using namespace std;
int p[100005];
int find(int n) { //root를 찾아줌
if (p[n] == -1) { p[n] = n; }
if (p[n] == n) { return n; } //이미 대각선에 위치함
p[n] = find(p[n]); //root를 찾는다
return p[n];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int tc;
cin >> tc;
for (int z = 0; z < tc; z++) {
fill(p, p + 100005, -1);
int n, m, ans = 0;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int r, c;
cin >> r >> c;
if (r == c) { continue; } //이미 대각선 위에 위치함
if (find(r) == find(c)) { ans++; } //만약 사이클을 이루는 그래프가 존재하면 사이클을 깨기 위해 1번의 이동이 더 필요
else { p[r] = c; }
ans++;
}
cout << ans << "\n";
}
return 0;
}
D. Grime Zoo
Lawali님의 코드와 Gravekper님의 풀이 영상을 참고하였다.
물음표를 채우지 않은 상태에서의 점수를 먼저 계산하고, 물음표를 하나씩 채워가면서 점수를 계산하고 그 중의 최솟값을 찾으면 된다. 주석을 많이 달아놓았다. 물음표를 채우는 숫자가 왜 1 1 1 ...0 0 이나 0 0...1 1 의 구조여야 하는지는, 물음표의 숫자를 하나씩 채울 때마다 '01'과 '10'이 몇 개씩 새로 생기는지를 생각해 보면 알 수 있다.
#include <iostream>
#include <vector>
#include <list>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <cmath>
typedef long long ll;
using namespace std;
int p[100005];
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
char s[100005];
ll cnt[100005][2] = { 0 }; //i-1번째까지 1과 0의 개수를 세 주는 배열
vector<ll> mark; //물음표가 있는 위치 표시
ll dp[100005][2] = { 0 };
ll x, y, ans = 0; //x는 01, y는 10에 대해
cin >> s;
cin >> x >> y;
ll len = strlen(s);
for (int i = 0; i < len; i++) { //물음표를 채우지 않은 상태에서의 매칭
cnt[i + 1][0] = cnt[i][0];
cnt[i + 1][1] = cnt[i][1];
if (s[i] == '?') { mark.push_back(i + 1); }
else if (s[i] == '1') {
cnt[i + 1][1]++;
ans += 1LL * cnt[i][0] * x; //01이 만들어지므로 그전까지의 0들과 매칭(개당x점)
}
else {
cnt[i + 1][0]++;
ans += 1LL * cnt[i][1] * y; //매칭해서 10들 만들기
}
}
for (ll i : mark) { //물음표 채우기
dp[i][0] = 1LL * cnt[i][1] * y + 1LL * (cnt[len][1] - cnt[i][1]) * x;
//i번 자리에 0이 들어가면 앞쪽에는 10이 생기고 뒤쪽에는 01이 생긴다
dp[i][1] = 1LL * cnt[i][0] * x + 1LL * (cnt[len][0] - cnt[i][0]) * y;
//i번 자리에 1이 들어가면 앞쪽에는 01이 생기고 뒤쪽에는 10이 생긴다
}//물음표가 채워지면서 새로 매칭되는 애들
for (int i = 1; i <= len; i++) {
dp[i][0] += dp[i - 1][0]; //구간합. 물음표들 사이에서 점수가 얼마나 올라가는지 빠르게 구하기 가능
dp[i][1] += dp[i - 1][1];
}
ll res = min(dp[len][0], dp[len][1]);
ll msize = mark.size();
for (int i = 1; i < msize; i++) {
res = min(res, 1LL * i * (msize - i) * x + dp[mark[i - 1]][0] + (dp[len][1] - dp[mark[i - 1]][1]));
//물음표들을 0 0 0 ... 0 1 1 1로 채울 경우. 물음표끼리의 매칭 + 물음표랑 기존 것들과의 매칭
res = min(res, 1LL * i * (msize - i) * y + dp[mark[i - 1]][1] + (dp[len][0] - dp[mark[i - 1]][0]));
//물음표들을 1 1 1 ... 1 0 0 0 으로 채울 경우
}
cout << ans + res << "\n";
return 0;
}