Codeforces Round #688 A~D
간만에 생각이 들어서 앞으로는 주기적으로 코드포스 셋 하나씩을 풀고 풀이를 쓰려고 한다. 이번에 푼 셋은 우리나라 ps계의 초대형 네임드 중 하나인 djm03178님의 셋이다. 나는 실제 대회에서 한문제밖에 못풀었기에 그다지 좋지는 않았다..ㅋㅋ
A. Cancel the Trains
100x100 격자로 된 철로에서 왼쪽에서 출발해서 오른쪽으로 가는 기차가 있고, 아래쪽에서 출발해서 위쪽으로 가는 기차가 있다. 이때 기차는 모두 같은 속력으로 달린다. 그런데 두 기차가 같은 시간에 한 위치를 지나게 되면 충돌이 발생하므로 이를 막아야 한다. 모든 충돌을 막기 위해서 취소해야 하는 기차 스케쥴의 최소 수를 구하는 문제다.
아래쪽에서 출발하는 기차의 선로번호와 왼쪽에서 출발하는 기차의 선로번호가 주어진다.
풀이는 간단한데, 아래쪽에서 출발하는 기차와 왼쪽에서 출발하는 기차의 선로번호가 겹치는 것의 개수를 구해주면 된다. set이나 해시테이블을 쓰면 아주 낮은 시간복잡도로 풀 수 있겠지만 n,m 제한이 100으로 매우 작아서 그냥 O(nm)으로 풀이했다.
#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, m, a[105], b[105], ans=0;
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < m; i++) {
cin >> b[i];
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (a[i] == b[j]) { ans++; }
}
}
cout << ans << "\n";
}
return 0;
}
B. Suffix Operations
n개의 원소로 이루어진 배열이 주어진다. 이 배열을 모두 같은 숫자로 바꾸고 싶다고 한다. 그러기 위해서 허락된 연산은 2가지다. 배열의 suffix(임의의 뒷부분 즉 arr[i]에서 arr[n-1] 까지로 이루어진 부분배열)전체를 1증가시키는 것, 혹은 1 감소시키는 것이다.
이 두 가지 연산을 최소한으로 써서 배열의 모든 숫자를 같게 만들어야 한다. 그러면 당연하게도, 필요한 최소한의 연산 횟수는 배열의 인접 원소들간의 차이의 합이 될 것이다.
만약 그것만 구하는 문제였으면 정말 쉬웠겠지만...연산 횟수를 더 줄이기 위해 우리에게 하나의 사전 처리를 할 기회가 주어진다. 배열의 원소 중 하나를 골라서 임의의 숫자로 바꿀 수 있는 것이다.
그럼 우리가 따져봐야 할 건 배열의 어느 숫자를 몇으로 바꿔야 최대한 연산횟수를 줄일 수 있느냐는 것이다. 이때 연산의 총 횟수를 구하는 원리(인접한 원소들간의 차이의 합)를 생각해 보면, 어떤 배열의 숫자를 다른 숫자로 바꿔서 연산을 얼마나 줄일 수 있는지는 그 원소에 인접한 원소들과의 차이에 따라 달라진다. 가령 1 2 999 4 이라는 수열이 있다면, 당연히 999를 3으로 바꾸는 게 이득일 것이다. 그게 인접한 원소들과의 차이가 가장 크기 때문에 그 차이를 줄여야 하기 때문이다.
만약 첫번째 원소를 바꾼다면 두 번째 원소와 똑같이 바꾸는 게 가장 이득일 것아고, 마지막 원소를 바꾼다면 마지막 바로 전 원소와 똑같이 바꾸는 게 가장 이득일 것이다. 그 외의 위치의 원소를 바꾼다면 인접한 두 원소의 사이 값을 취하는 게 가장 이득이다.
#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++)
{
ll n, arr[200005];
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
if (n == 2) {
cout << "0\n";
}
else {
ll ans = 0, dec = max(abs(arr[1] - arr[0]), abs(arr[n - 1] - arr[n - 2]));
for (int i = 1; i < n; i++) {
ans += abs(arr[i - 1] - arr[i]);
}
for (int i = 1; i < n - 1; i++) {
dec = max(dec, abs(arr[i] - arr[i - 1]) + abs(arr[i + 1] - arr[i]) - abs(arr[i + 1] - arr[i - 1]));
}
//이만큼 연산을 줄일 수 있다
cout << ans - dec << "\n";
}
}
return 0;
}
C. Triangles
0에서 9까지의 숫자로 이루어진 nxn 지도가 주어지고, 거기서 각각의 숫자를 꼭짓점으로 갖는 삼각형들의 최대 넓이를 0~9 각각에 대해 구하는 문제이다. 가령0에 대해서는 0이 쓰여진 점 3개를 꼭짓점으로 갖는 삼각형들 중 최대 넓이를 구하는 것이다. 단 조건이 있는데 그 삼각형의 최소 한 변은 지도의 모서리에 평행해야 한다는 것이다.
또 문제에서는 한 가지의 사전 처리를 허용하는데, 삼각형 넓이를 하나씩 구할 때마다 지도 위 임의의 한 점을 임의의 숫자로 바꿀 수 있다는 것이다. 예를 들어
000
100
001
과 같은 지도가 있다면 첫 번째 행의 마지막 숫자를 1로 바꿔서 다음과 같은 보드를 만들 수 있다.
001
100
001
1로 이루어진 삼각형의 넓이를 구하면 그것이 1로 이루어진 삼각형 중 최대 넓이가 된다는 것이다. 또 최대의 삼각형 넓이를 구하고 나서는 숫자를 원상복귀시킨다.
이런 식으로 우리는 기존 지도에 있는 것보다 더 큰 최대 삼각형 넓이를 구할 수 있다. 또한 두 점만 있으면 나머지 한 점은 임의의 위치의 점을 바꿔서 만들어 줄 수 있으므로, 삼각형의 최소 한 변은 지도의 모서리와 평행해야 한다는 조건도 무조건 만족시켜줄 수 있다. 우리는 안심하고 조건에 맞는 최대 삼각형의 넓이만 구해주면 된다.
이걸 구하는 방식은 간단한데 그냥 숫자마다 상하좌우의 가장 끝에 있는 점들을 하나씩 저장해 놓고, 모든 점들에 대해 돌려보면 된다. 점이 최대 4백만개이고, 10개의 숫자들마다 점들을 한번씩 쭉 훑으니까 4천만 정도의 연산량이 나온다. 따라서 제한시간 안에 충분히 돈다.
#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;
char arr[2005][2005];
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
for (char digit = '0'; digit <= '9'; digit++) {
int cnt = 0;
list<pair<int, int>> pos;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (arr[i][j] == digit) {
cnt++;
pos.push_back({ i,j }); //그 숫자가 나온 위치를 저장
}
}
}
if (cnt == 0 || cnt == 1) { //숫자가 없거나 한개뿐이면 아무것도 못한다
cout << "0 ";
continue;
}
pair<int, int> upmost = { n,n }, downmost = { -1,-1 }, leftmost = { n,n }, rightmost = { -1,-1 };
for (pair<int, int> p : pos) {
if (p.first < upmost.first) { upmost = p; } //가장 위쪽 점, 가장 왼쪽 점 찾기
if (p.second < leftmost.second) { leftmost = p; }
if (p.first > downmost.first) { downmost = p; }
if (p.second > rightmost.second) { rightmost = p; }
}
int ans = 0;
int minr = upmost.first, maxr = downmost.first;
int minc = leftmost.second, maxc = rightmost.second;
//모든 점들에 대해 삼각형 넓이를 구해본다
for (pair<int, int> spot : pos) {
int r = spot.first, c = spot.second;
int tmp1 = max(r, n - 1 - r) * max(c - minc, maxc - c);
int tmp2 = max(c, n - 1 - c) * max(r - minr, maxr - r);
ans = max(ans, max(tmp1, tmp2));
}
cout << ans << " ";
}
cout << "\n";
}
return 0;
}
D. Checkpoints
n개의 스테이지로 이루어진 게임을 한다. 각 스테이지를 돌파할 확률은 1/2이다. 그런데 스테이지마다 체크포인트 같은 게 있을 수도 있고 없을 수도 있다. 체크포인트가 있는 스테이지에서 실패하면 그 스테이지에서 다시 도전할 수 있고, 체크포인트가 없는 스테이지에서 실패하면 가장 최근에 돌파한, 체크포인트가 있는 스테이지로 돌아가서 다시 도전해야 한다. 마지막 스테이지를 돌파하면 게임 클리어다.
이때 n개의 스테이지로 이루어진 게임에 대해서는 그 게임을 끝까지 깨기 위해 필요한 도전 횟수의 기댓값을 구할 수 있을 것이다. 1을 체크포인트가 있는 스테이지, 0을 체크포인트가 없는 스테이지라고 할 때,
1 1
이런 게임이 있다면 각 스테이지마다 평균적으로 2번의 도전이 필요하므로(각 스테이지에서 실패해도 체크포인트가 있으니 실패한 스테이지에서 바로 재도전 가능하다)게임 클리어까지 총 도전횟수의 기댓값은 4이다.
이때 어떤 k값이 주어지면, 그 k값을 총 도전 횟수의 기댓값으로 갖는 게임을 만들어낼 수 있는지에 대한 문제이다. 단, 2000스테이지까지만 만들 수 있다.
만약 1, 즉 체크포인트가 있는 스테이지로만 게임을 만든다면 각 스테이지의 도전 횟수 기댓값은 2씩이므로, 2000스테이지까지 만들면 총 4000까지의 도전 횟수 기댓값을 만들 수 있다. 또한 도전횟수 기댓값의 최소 단위가 2이므로, 홀수 k가 주어지면 게임 구성이 불가능하다는 점을 알 수 있다. 그런데 k의 범위는 1018이므로, 1만 쓰는 것 외에 무언가 다른 발상이 필요하다.
우리는 체크포인트가 없는 스테이지를 이용할 필요가 있다. 그런데 체크포인트가 없는 스테이지로 이루어진 게임의 도전횟수 기댓값은 얼마일까? 가령
1 0 0
으로 이루어진 게임이 있다고 하자. 첫 스테이지를 깨기 위한 도전횟수 기댓값은 당연히 2이다. 그리고 2번째 스테이지에서는 실패하면 다시 첫번째 스테이지로 돌아가서 처음부터 도전해야 하므로, 두 개의 스테이지를 한번에 돌파하는 확률을 뚫어야 한다. 따라서 4의 도전 횟수가 기댓값이다. 세번째 스테이지도 마찬가지로, 실패하면 첫번째 스테이지로 돌아가야 한다. 즉 세번째 스테이지를 돌파하는 건 첫번째~세번째 스테이지를 한번에 돌파하는 확률과 같다. 세번째 스테이지 돌파를 위한 도전 횟수 기댓값은 8이다.
결론적으로 위와 같은 게임 전체의 도전 횟수 기댓값은 2+4+8이다. 뭔가 규칙이 보이지 않는가? 이를 일반화시키면 1 0 ..0(0이 i개) 스테이지들을 돌파하는 데 필요한 도전 횟수 기댓값은 2+4+8+...2(i+1) 즉 2(i+2)-2 이다. 이걸 생각하면 2000스테이지 안에 1018 이라는 도전 횟수 기댓값을 당연히 만들 수 있다.
여기까지 도달했다면 다음은 간단하다. k가 0이 될 때까지 적절히 2i-2 를 빼주면서 게임을 구성해 주면 된다.
#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++)
{
ll k, cnt = 0, zeros = 0;
vector<ll> ans;
cin >> k;
if (k % 2 != 0) { cout << "-1\n"; continue; }
//홀수는 나타낼 수 없다
while (k > 0) {
for (ll i = 62; i >= 0; i--) {
if (k >= (1LL << (i + 1)) - 2) {
zeros = i - 1;
k -= (1LL << (i + 1)) - 2;
break;
}
}
//cout << zeros << "\n";
ans.push_back(1);
for (ll i = 0; i < zeros; i++) {
ans.push_back(0);
}
}
cout << ans.size() << "\n";
for (ll num : ans) {
cout << num << " ";
}
cout << "\n";
}
return 0;
}