제 5회(2019) SCPC 라운드2는 7월 6일 오전 9시에서 부터 오후 9시까지 12시간 동안 온라인에서 진행되었다. 벌써 3달 가까이 지났지만, 늦게나마 후기를 남기려고 한다.
1. 소수 수열
제출자: 639
만점자: 587
평균점수/만점: 92/100
내 점수: 100
수학과 프로그래밍을 좋아하는 $A$와 $B$가 $0$이 포함되지 않은 $30,000$ 미만의 자연수를 각각 제시한다. 각 수에 대해 다음의 과정을 통해 점수를 얻는다.
- 주어진 수에서 한 자리를 골라 해당 자리의 숫자를 제거한다.
- 제거한 뒤 숫자가 소수이면 첫 번째 과정을 수행한다.
- 제거한 뒤 숫자가 합성수이면 과정을 종료한다.
위 과정을 최대한 반복한 횟수가 해당 숫자의 점수가 된다.
$A$, $B$ 둘 중 누가 이기는지 또는 비기는지 판단하는 프로그램을 작성해야 한다.
풀이
주어지는 숫자는 최대 5자리로 작다. 따라서 에라토스테네스의 체를 이용하여 30,000미만의 소수를 모두 구해 놓고, 주어진 숫자에 대해 전체탐색을 하며 소수가 아닐 경우 가지치기를 하면 해결할 수 있다.
#include <iostream>
#include <string>
#include <algorithm>
#define MAXN 30000
using namespace std;
int T;
string A, B;
bool P[MAXN + 1];
void get_primes(){
P[0] = true;
P[1] = true;
for(int j = 2; j <= MAXN; j++){
if(P[j])
continue;
for(int i = 2; j * i <= MAXN; i++)
P[j * i] = true;
}
}
int dfs(string num, bool sel[5]){
int n = 0;
for(int j = 0; j < num.size(); j++){
if(sel[j]) continue;
n = n * 10 + num[j] - '0';
}
if(P[n])
return 0;
int ret = 0;
for(int j = 0; j < num.size(); j++){
if(sel[j]) continue;
sel[j] = true;
ret = max(ret, dfs(num, sel));
sel[j] = false;
}
return ret + 1;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
get_primes();
cin >> T;
for(int tt = 1; tt <= T; tt++){
cin >> A >> B;
cout << "Case #" << tt << "\n";
bool sel[2][5];
for(int j = 0; j < 2; j++)
for(int i = 0; i < 5; i++)
sel[j][i] = false;
int a = dfs(A, sel[0]);
int b = dfs(B, sel[1]);
if(a > b)
cout << "1\n";
else if(a < b)
cout << "2\n";
else
cout << "3\n";
}
return 0;
}
2. 유사도
제출자: 561
만점자: 377
평균점수/만점: 110/150
내 점수: 150
$n$개의 $10^6$이하의 자연수로 이루어진 두 수열 $a$, $b$가 주어진다. $n$은 $1 \le n \le 5,000$을 만족한다. 이때 두 수열의 유사도 $sim(a, b)$는 다음과 같다.
\[f(x) = \left\{\begin{matrix} 1 & \text{if } a_x = b_x \\ 0 & \text{if } a_x \ne b_x \end{matrix}\right.\] \[sim(a, b) = \sum_{i}f(i)\]즉, 같은 자리에 있는 숫자가 같은 개수가 두 배열의 유사도가 된다. 이때, 수열 $b$에 대해서만 다음과 같은 회전 연산을 할 수 있다.
- $[i, j]$ $(i \le j)$에 대한 회전 연산이 주어지면 기존의 수열 $b_i b_{i+1} \dots b_j$를 $b_j b_{j-1} \dots b_i$로 순서를 서로 맞 바꾼다.
단 한번 회전 연산을 할 때, 유사도의 최댓값을 구하는 문제다.
풀이
모든 구간에 대해 회전 연산을 하여 전체탐색으로 최댓값을 구하면 $O(n^3)$으로 $n$의 최댓값이 5,000이므로 TLE가 난다.
따라서 회전 연산의 특징을 고려하여 필요 없는 연산을 줄어야 한다. 다음과 같은 경우를 생각해 보자.
-
초기상태: $b_1 b_2 b_3 b_4 b_5$
-
$[3, 4]$ 회전: $b_1 b_2 (b_4 b_3) b_5$
-
$[2, 5]$ 회전: $b_1 (b_5 (b_4 b_3) b_2)$
$[3, 4]$를 회전했을 때의 상태가 $[2, 5]$를 회전했을 때도 유지됨을 확인할 수 있다. 이를 이용하면 주어진 회전 연산에 대해 새로운 상태로 갱신되는 부분에 대해서만 유사도의 변화량을 계산하여 $O(n^2)$으로 시간 복잡도를 낮출 수 있을 것이다.
회전 연산 구간의 길이를 1부터 늘려가면서 다음의 dp테이블을 채워 나가면 문제를 해결할 수 있다.
dp[i][j] := 구간 [i, j]를 회전했을 때의 유사도의 변화량
즉, 회전을 하지 않은 초기상태의 유사도를 $sim$이라 하면 구간 $[i, j]$를 회전했을 때의 유사도는 $dp[i][j]+sim$이다.
#include <iostream>
#include <algorithm>
#define MAXN 5000
using namespace std;
int T, N, A[MAXN], B[MAXN], dp[MAXN][MAXN], ans;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> T;
for(int tt = 1; tt <= T; tt++){
cout << "Case #" << tt << "\n";
cin >> N;
for(int j = 0; j < N; j++)
cin >> A[j];
for(int j = 0; j < N; j++)
cin >> B[j];
int sim = 0;
for(int j = 0; j < N; j++)
if(A[j] == B[j])
sim++;
ans = sim;
for(int j = 1; j < N; j++){
for(int i = 0; i + j < N; i++){
int diff = 0;
if(A[i] == B[i] && A[i] != B[i + j])
diff--;
if(A[i + j] == B[i + j] && A[i + j] != B[i])
diff--;
if(A[i] != B[i] && A[i] == B[i + j])
diff++;
if(A[i + j] != B[i + j] && A[i + j] == B[i])
diff++;
diff += dp[i + 1][i + j - 1];
dp[i][i + j] = diff;
ans = max(ans, sim + diff);
}
}
cout << ans << "\n";
}
return 0;
}
3. 드론 탐험
제출자: 224
만점자: 143
평균점수/만점: 130/200
내 점수: 200
2차원 평면의 영역으로 이루어진 동굴이 주어진다. 동굴은 천장과 바닥으로 이루어져 있는데, 각각 수직인 선분과 수평인 선분들로만 이루어져 있다.
이러한 동굴에 드론을 가장 왼쪽에 존재하는 출발 지점에서 부터 동굴의 가장 오른쪽에 존재하는 도착 지점까지 이동시킨다. 드론은 다음과 같은 방법으로 이동할 수 있다.
- 드론은 수평으로 오른쪽으로 움직일 수 있다.
- 드론은 수직으로 아래나 위로 움직일 수 있다.
- 드론은 위 두가지 방법을 사용하여 가능한 최단 경로로 움직인다.
이와 같이 움직일 수 있는 드론의 경로는 여러가지가 있을 수 있다. 따라서 드론이 동굴을 탐험하는 것을 무한히 반복해서 모든 가능한 경로로 움직인 궤적을 모두 그리면 영역이 나온다. 이 영역의 면적을 계산하는 프로그램을 작성해야 한다.
동굴의 길이는 최대 $10^9$인 자연수이고, 수평선의 개수는 최대 $100,000$인 자연수이다.
풀이
드론은 위, 아래, 오른쪽으로만 움직이기 때문에 드론의 최단 이동 거리는 유클리드 거리가 아닌 맨해튼 거리로 계산된다.
이 문제의 핵심은 면적이 되는 경계선을 어떻게 구하는가 이다. 출발 지점 부터 오른쪽으로 벽을 만날 때까지 최대한 움직이는 전략을 이용하여 경로를 그려보자. 그러면 항상 위, 아래 경계선 중 한 부분을 그리게 된다. 그렇다면 남은 경계선은 도착점에서 부터 출발하여 그릴 수 있지 않을까? 직접 그려보면 해당 경로가 나머지 경계선을 그림을 알 수 있다.
대강 원리를 생각 하자면, 한 방향으로 나아갔을 때, 벽을 만나면 벽을 피할 수 있는 위치로 이동한다. 하지만 반대 방향으로 나아갈 경우, 벽을 피하는 경우를 제외하고 해당 위치에서 동일한 경로를 가질 일은 발생하지 않는다. 따라서 해당 경우가 발생하는 경우는 반대 방향으로 나아갔을 경우에도 벽이 있는 경우 밖에 없고, 이런 경우는 동굴이 중간에 막힌 경우이며, 이런 경우 출발점에서 도착점으로 이동할 수 없는 경우이므로 존재할 수 없다. 또한 각각의 경로는 맨해튼 거리에 따른 최단경로이므로 면적의 경계선에 위치하게 될 것이다.
이 전략을 이용하여 경계선을 구한 뒤, 면적을 계산하면 된다. 구현이 좀 어려웠던 것으로 기억한다. 구현만 잘 해낸다면 해결할 수 있을 것이다.
#include <iostream>
#include <queue>
#include <stack>
#include <deque>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int lli;
struct strt{
lli x, h;
bool ceil;
bool operator<(const strt& s)const{
return x < s.x;
}
bool operator>(const strt& s)const{
return x > s.x;
}
};
lli T, L, S, E, A, B;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> T;
for(lli tt = 1; tt <= T; tt++){
cout << "Case #" << tt << "\n";
cin >> L >> S >> E >> A;
priority_queue<strt, vector<strt>, greater<strt>> pq1;
priority_queue<strt, vector<strt>, less<strt>> pq2;
lli ceil_h1, floor_h1;
lli ceil_h2, floor_h2;
for(int j = 0, x = 0; j < A; j++){
lli l, h; cin >> l >> h;
if(j > 0)
pq1.push({x, h, true});
else
ceil_h1 = h;
if(j < A - 1)
pq2.push({x + l, h, true});
else
ceil_h2 = h;
x += l;
}
cin >> B;
for(int j = 0, x = 0; j < B; j++){
lli l, h; cin >> l >> h;
if(j > 0)
pq1.push({x, h, false});
else
floor_h1 = h;
if(j < B - 1)
pq2.push({x + l, h, false});
else
floor_h2 = h;
x += l;
}
lli nh = S;
vector<strt> LL;
LL.push_back({0, nh, 0});
while(!pq1.empty()){
strt t = pq1.top(); pq1.pop();
if(t.ceil){
if(min(ceil_h1, t.h) <= nh && nh <= max(ceil_h1, t.h) && (ceil_h1 != nh || (ceil_h1 == nh && ceil_h1 > t.h))){
nh = t.h;
LL.push_back({t.x, nh, 0});
}
ceil_h1 = t.h;
}else{
if(min(floor_h1, t.h) <= nh && nh <= max(floor_h1, t.h) && (floor_h1 != nh || (floor_h1 == nh && floor_h1 < t.h))){
nh = t.h;
LL.push_back({t.x, nh, 0});
}
floor_h1 = t.h;
}
}
nh = E;
vector<strt> RL;
RL.push_back({L, E, 0});
while(!pq2.empty()){
strt t = pq2.top(); pq2.pop();
if(t.ceil){
if(min(ceil_h2, t.h) <= nh && nh <= max(ceil_h2, t.h) && (ceil_h2 != nh || (ceil_h2 == nh && ceil_h2 > t.h))){
nh = t.h;
RL.push_back({t.x, nh, 0});
}
ceil_h2 = t.h;
}else{
if(min(floor_h2, t.h) <= nh && nh <= max(floor_h2, t.h) && (floor_h2 != nh || (floor_h2 == nh && floor_h2 < t.h))){
nh = t.h;
RL.push_back({t.x, nh, 0});
}
floor_h2 = t.h;
}
}
lli maxh = max(LL[0].h, RL.back().h);
lli minh = min(LL[0].h, RL.back().h);
lli prex = 0;
lli ans = 0;
for(int a = 1, b = RL.size() - 1; a < LL.size() || b >= 0; ){
maxh = max(LL[a - 1].h, RL[b < 0 ? 0 : b].h);
minh = min(LL[a - 1].h, RL[b < 0 ? 0 : b].h);
if(a < LL.size() && b >= 0){
if(LL[a].x < RL[b].x){
ans += (LL[a].x - prex) * (maxh - minh);
prex = LL[a].x;
a++;
}else{
ans += (RL[b].x - prex) * (maxh - minh);
prex = RL[b].x;
b--;
}
}else if(a < LL.size()){
ans += (LL[a].x - prex) * (maxh - minh);
prex = LL[a].x;
a++;
}else{
ans += (RL[b].x - prex) * (maxh - minh);
prex = RL[b].x;
b--;
}
}
cout << ans << "\n";
}
return 0;
}
4. 폭격
제출자: 339
만점자: 112
평균점수/만점: 132/250
내 점수: 250
$M$행 $N$열의 격자칸으로 이루어진 적국이 존재한다. 각 칸에는 공장이 없거나 있을 수 있다. 폭탄 하나는 3행 3열에 있는 공장을 모두 파괴하는데, 적국에 존재하는 모든 공장을 파괴하기 위한 폭탄의 개수를 최소화 하라는 문제다.
정답 개수에 대해 $1.2$배 내의 답을 출력한 경우 부분점수를 받는 휴리스틱 문제다.
풀이
각 칸에 폭탄을 터트렸을 때 공장을 최대 몇개 터트릴 수 있는지 계산한다. 그 뒤, 그리디 전략을 사용하는데 문제는 폭탄을 한 번 터트리면 최대 값이 변화하게 된다는 것이다.
이는 폭탄 하나가 터졌을 때, 변화하게 되는 칸의 수는 적다는 것을 이용하여 변화될 수 있는 칸만 갱신해 주도록 하여 연산을 최소화 한다. 이 방식을 사용해도 만점이 나오지 않는다.
만점이 나오지 않는 이유는 최댓값을 가진 위치가 2곳 이상이 될 때, 더이상 비교할 가중치가 존재하지 않는다는 것이다.
따라서 동일한 최댓값이 등장하면, 각 위치를 다른 지점에서 파괴 했을 경우의 파괴 가능한 공장의 개수가 최소인 지점을 선택하도록 했다.
이와같이 동일한 가중치가 여러개 등장하는 경우를 처리해 주면 만점을 받을 수 있다.
#include <iostream>
#include <string>
#include <queue>
#include <set>
#include <vector>
#define MAXN 500
#define MAXM 50
using namespace std;
struct strt{
int x, y, cnt, w;
bool operator<(const strt& s)const{
if(cnt == s.cnt)
return w > s.w;
return cnt < s.cnt;
}
bool operator>(const strt& s)const{
if(cnt == s.cnt)
return w < s.w;
return cnt > s.cnt;
}
};
struct point{
int x, y;
bool operator<(const point& p)const{
if(x == p.x)
return y < p.y;
return x < p.x;
}
bool operator>(const point& p)const{
if(x == p.x)
return y > p.y;
return x > p.x;
}
};
int T, M, N, C[MAXM][MAXN];
bool P[MAXM][MAXN];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> T;
for(int tt = 1; tt <= T; tt++){
cout << "Case #" << tt << "\n";
cin >> M >> N;
for(int y = 0; y < M; y++){
string str; cin >> str;
for(int x = 0; x < N; x++)
P[y][x] = str[x] - '0';
}
priority_queue<strt> pq;
set<point> update;
for(int y = 0; y < M; y++)
for(int x = 0; x < N; x++)
C[y][x] = 0;
for(int y = 0; y < M; y++){
for(int x = 0; x < N; x++){
if(y >= M - 2 || x >= N - 2)
continue;
for(int dx = 0; dx <= 2; dx++)
for(int dy = 0; dy <= 2; dy++)
if(P[y + dy][x + dx])
C[y + dy][x + dx]++;
}
}
for(int y = 0; y < M; y++){
for(int x = 0; x < N; x++){
int cnt = 0, w = 0;
if(y >= M - 2 || x >= N - 2)
continue;
for(int dx = 0; dx <= 2; dx++)
for(int dy = 0; dy <= 2; dy++){
cnt += P[y + dy][x + dx];
w += C[y + dy][x + dx];
}
if(cnt)
pq.push({x, y, cnt, w});
}
}
vector<point> ans;
while(!pq.empty()){
strt t = pq.top();
pq.pop();
if(update.find({t.x, t.y}) != update.end()){
update.erase({t.x, t.y});
int cnt = 0;
for(int dx = 0; dx <= 2; dx++)
for(int dy = 0; dy <= 2; dy++)
cnt += P[t.y + dy][t.x + dx];
if(cnt != t.cnt){
if(cnt)
pq.push({t.x, t.y, cnt, t.w});
continue;
}
}
ans.push_back({t.x + 1, t.y + 1});
for(int dx = 0; dx <= 2; dx++)
for(int dy = 0; dy <= 2; dy++){
if(P[t.y + dy][t.x + dx]){
P[t.y + dy][t.x + dx] = false;
for(int dx2 = -2; dx2 <= 0; dx2++)
for(int dy2 = -2; dy2 <= 0; dy2++){
int x_ = t.x + dx + dx2;
int y_ = t.y + dy + dy2;
if(x_ < 0 || y_ < 0 || x_ >= N || y_ >= M || (x_ == t.x && y_ == t.y))
continue;
update.insert({x_, y_});
}
}
}
}
cout << ans.size() << "\n";
for(int j = 0; j < ans.size(); j++){
cout << ans[j].y << " " << ans[j].x << "\n";
}
}
return 0;
}
5. 존의 정사각형
제출자: 283
만점자: 54
평균점수/만점: 85/300
내 점수: 0
해당 문제는 유일하게 풀지 못했다.
문제를 보고 우선 28점을 휙득한 뒤에 고민해 보자 했는데, 28점 휙득 마저 도저히 이해할 수 없는 TLE에 걸렸고 무려 7번을 시도하다 그냥 풀지 않았다. (어차피 본선은 확정인 상황이었기 때문에..)
다음은 문제의 코드이다. ($N \le 2,000$에 대한 솔루션)
#include <iostream>
#include <algorithm>
#define ABS(X) ((X) > 0 ? (X) : -(X))
#define MAXN 500000
using namespace std;
/// N <= 2000 solution
typedef long long int lli;
struct point{
lli x, y;
bool operator<(const point& p){
if(y == p.y)
return x < p.x;
return y < p.y;
}
bool operator>(const point& p){
if(y == p.y)
return x > p.x;
return y > p.y;
}
};
lli T, M, N;
point P[MAXN];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> T;
for(int tt = 1; tt <= T; tt++){
cout << "Case #" << tt << "\n";
cin >> M >> N;
for(int j = 0; j < N; j++)
cin >> P[j].x >> P[j].y;
lli ans = 0;
for(int j = 0; j < N; j++){
lli l = min(M - P[j].x, M - P[j].y);
for(int i = 0; i < N; i++)
if(j != i && P[j].x < P[i].x && P[j].y < P[i].y)
l = min(l, max(P[i].x - P[j].x, P[i].y - P[j].y));
ans += l;
}
cout << ans << "\n";
}
return 0;
}
놀라운 발견
이 문서를 작성하면서 다음의 코드를 제출했더니 부분점수를 받았다….
#include <iostream>
#include <algorithm>
#define ABS(X) ((X) > 0 ? (X) : -(X))
#define MAXN 500000
using namespace std;
/// N <= 2000 solution
typedef long long int lli;
struct point{
lli x, y;
bool operator<(const point& p){
if(y == p.y)
return x < p.x;
return y < p.y;
}
bool operator>(const point& p){
if(y == p.y)
return x > p.x;
return y > p.y;
}
};
lli T, M, N;
point P[MAXN];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> T;
for(int tt = 1; tt <= T; tt++){
cout << "Case #" << tt << "\n";
cin >> M >> N;
for(int j = 0; j < N; j++)
cin >> P[j].x >> P[j].y;
if(N > 2000){
cout << "0\n";
continue;
}
lli ans = 0;
for(int j = 0; j < N; j++){
lli l = min(M - P[j].x, M - P[j].y);
for(int i = 0; i < N; i++)
if(j != i && P[j].x < P[i].x && P[j].y < P[i].y)
l = min(l, max(P[i].x - P[j].x, P[i].y - P[j].y));
ans += l;
}
cout << ans << "\n";
}
return 0;
}
그렇다. 모든 코드는 동일하고 다음 코드만 추가된 것이다.
if(N > 2000){
cout << "0\n";
continue;
}
더욱 놀라운 점은, 혹시나 해서 대회 당시 위와 같은 코드를 추가하여 제출했는데도 부분점수가 아닌 TLE가 났었다는 것이다.
도저히 이해할 수 없는 채점 시스템이다.