E-Z한 1차예선은 뛰어넘고 2차예선의 날이 다가왔다.
작년에는 한문제도 풀지 못했는데, 이번에는 그런 일이 없길 바래야지!
Q1. 원 안의 점
풀이 보기
시도 횟수 : 1 / 10
점수 : Pass ( 100 / 100, 0.0929 )
풀이
제 1사분면의 점을 모두 셀 수 있으면 쉽게 풀어낼 수 있는 문제이다.
sqrt 함수 등을 이용하여 원의 방정식을 이용하는 것이 정석이다.
본인은 double형을 매우 싫어하므로 최대한 int형으로 풀 수 있도록 제곱수를 이용했다.
제 1사분면의 점을 모두 세었다면, $\times{4}$를 해주고 원점과 축의 점을 포함하면 답을 구할 수 있다.
소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdio.h>
int main() {
int testcase;
scanf("%d", &testcase);
for (int t = 1; t <= testcase; ++t) {
long long r, tr;
scanf("%lld", &r);
long long result = 0;
long long a = r - 1, b = 1;
tr = r * r;
for (; a > 0; --a) {
long long ta = a * a;
while (tr - ta > b * b) {
++b;
}
--b;
//printf("a : %lld %lld\n", a, b);
result += b;
}
result *= 4;
result += (4 * (r - 1));
++result;
printf("Case #%d\n%lld\n", t, result);
}
return 0;
}
Q2. 직8각형
풀이 보기
시도 횟수 : 7 / 10
점수 : Pass ( 200 / 200, 1.32048 )
풀이
난이도 상당하다! 같이 참여한 친구는 실패한 문제이다.
이 문제에서는 본인이 찾아내 사용한 개념이 몇가지 있다. 물론 이런거 사용하지 않고 씹어먹는 굇수분들에게는 필요 없겠지만..
우선 점은 모든 testcase에서 총 8개 주어진다. 각 점이 직8각형의 어떤 위치에 사용될까? 한번에 알아낼 방법은 떠오르지 않았다. 그래서 모든 경우를 세보자고 생각했다. $8!=40320$이므로 제한시간 내에 돈다는 것은 확인했다.
이후 만들어진 template에 점을 모두 갖다붙인다. 이때 template를 평행이동하여 중점을 잡고, 이후 모든 점들의 자리를 맞추는 데 필요한 이동횟수의 최솟값을 찾아내는 방법을 취했다.
그렇다면 중점을 어떻게 구할 수 있을까? 우선 거리는 맨해튼 거리를 사용하므로, x축과 y축은 따로 계산할 수 있다. 그럼 모든 점들은 수직선 위에 존재한다고 가정하고 문제를 바라볼 수 있다.
예시로 아래와 같은 경우가 있다고 생각해보자. 여기서 x는 현재 중점 ( 기본값 : $0$ ) 이라고 가정한다.
x–1—-2—–3——–4——5—-6—-7—-8—
이 경우 x를 어느 위치로 옮기는 것이 중점으로 옮기는 것일까? 정답부터 말하자면 4와 5 사이로 보내는 것이 정답이다. 증명은 간단하다. 현재 x위치부터 8이 있는 위치까지 한칸씩 옮긴다고 가정해보자. 그럼 모든 8개의 점에서는 “손해 또는 이익” 이 발생한다. 위 예시에서는 x위치에서 1칸 오른쪽으로 이동한다면, 8개 점 모든 부분에서 이익을 볼수 있다. 그럼 당연히 옮기는 것이 제일 나은 방법일 것이다. 그럼 손해를 보는 경우는 언제일까? 그것은 x가 현재보다 멀어지는 경우일 것이다.
그렇다면 중점은 x가 움직여도 이익과 손해가 없어지는 구간이 될 것이다. 그것이 바로 4와 5 사이, 혹은 그 점들이 된다. 궁금하면 직접 움직여보고 이해해보자. 한 점에서 이익을 보게 만들면 다른 곳에서 무조건 손해를 보는 구조가 만들어진다.
이렇게 중점을 옮겼다면 이후에 추가로 옮겨야하는 위치값만을 추려 더하면 답을 얻을 수 있다.
총 7번 시도했는데, 3번째 제출부터 부등호가 잘못 써져있었다는 것을 알게 되었다. 빠르게 풀고 넘어갈 수 있었을텐데..
소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <stdio.h>
typedef long long ll;
typedef struct Node {
ll x, y;
} ND;
#define M 8
#define FACT 40320
ND dots[M];
ND temp[M];
ND diff[M][M];
int allCase[FACT][M], l;
ll k;
#define min(a, b) (((a) > (b)) ? (b) : (a))
#define max(a, b) (((a) > (b)) ? (a) : (b))
#define abs(x) (((x) < 0) ? (-(x)) : (x))
void back(int x, int* arr) {
if (x == M) {
for (int i = 0; i < M; ++i) {
allCase[l][arr[i]] = i;
}
++l;
return;
}
for (int i = 0; i < M; ++i) {
if (arr[i] == -1) {
arr[i] = x;
back(x + 1, arr);
arr[i] = -1;
}
}
return;
}
void init() {
int arr[M];
for (int i = 0; i < M; ++i) {
arr[i] = -1;
}
back(0, arr);
return;
}
void make_template(ll x) {
temp[0] = (ND){0, 0};
temp[1] = (ND){0, k};
temp[2] = (ND){k, -k};
temp[3] = (ND){k, 2 * k};
temp[4] = (ND){2 * k, -k};
temp[5] = (ND){2 * k, 2 * k};
temp[6] = (ND){3 * k, 0};
temp[7] = (ND){3 * k, k};
}
int main() {
init();
int testcase;
scanf("%d", &testcase);
for (int t = 1; t <= testcase; ++t) {
scanf("%lld", &k);
make_template(k);
ll result = (ll)(1e18);
for (int i = 0; i < M; ++i) {
ll a, b;
scanf("%lld %lld", &a, &b);
dots[i] = (ND){a, b};
for (int j = 0; j < M; ++j) {
diff[i][j] = (ND){dots[i].x - temp[j].x, dots[i].y - temp[j].y};
}
}
ll tx, ty, ttx, tty;
for (int i = 0; i < FACT; ++i) {
ttx = 0, tty = 0;
while (1) {
int px = 0, mx = 0, zx = 0;
ll ptx = (ll)(1e18), mtx = (ll)(-1e18);
int py = 0, my = 0, zy = 0;
ll pty = (ll)(1e18), mty = (ll)(-1e18);
for (int a = 0; a < M; ++a) {
if (diff[a][allCase[i][a]].x + ttx > 0) {
++px, ptx = min(ptx, diff[a][allCase[i][a]].x + ttx);
} else if (diff[a][allCase[i][a]].x + ttx < 0) {
++mx, mtx = max(mtx, diff[a][allCase[i][a]].x + ttx);
} else {
++zx;
}
if (diff[a][allCase[i][a]].y + tty > 0) {
++py, pty = min(pty, diff[a][allCase[i][a]].y + tty);
} else if (diff[a][allCase[i][a]].y + tty < 0) {
++my, mty = max(mty, diff[a][allCase[i][a]].y + tty);
} else {
++zy;
}
}
if (px > 4 || py > 4 || mx > 4 || my > 4) {
if (px > 4) {
ttx -= ptx;
}
if (py > 4) {
tty -= pty;
}
if (mx > 4) {
ttx -= mtx;
}
if (my > 4) {
tty -= mty;
}
} else {
break;
}
}
tx = 0, ty = 0;
for (int a = 0; a < M; ++a) {
tx += abs(diff[a][allCase[i][a]].x + ttx), ty += abs(diff[a][allCase[i][a]].y + tty);
}
result = min(result, tx + ty);
}
printf("Case #%d\n%lld\n", t, result);
}
return 0;
}
Q3. 산탄총
풀이 보기
시도 횟수 : 3 / 10
점수 : TLE ( 47 / 300, 3.00027 )
풀이
아직도 정해, 심지어는 약식풀이 방법도 모르겠다. 찾아본 방법으로는 dp를 이용한다는데, 도대체 이게 어떻게 dp로 풀리는 것인지..
아래 서술된 코드는 브루트포스 방법으로 총을 쐈을 때 만들어지는 다이아몬드 모양을 구한 뒤, 가능한 모든 경우에 대해 총을 붙여 칸의 값들을 모두 계산한 방법이다. 알맹이는 하나도 없으니 설명은 생략한다.
소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <stdio.h>
typedef long long ll;
#define MAX_GRID 1800
#define START 600
ll grid[MAX_GRID][MAX_GRID];
ll tp[MAX_GRID][MAX_GRID];
int n, k;
#define max(a, b) (((a) > (b)) ? (a) : (b))
int main() {
setbuf(stdout, NULL); // part score
int testcase;
scanf("%d", &testcase);
for (int t = 1; t <= testcase; ++t) {
ll result = 0;
scanf("%d %d", &n, &k);
int DIV_GRID = 2 * k - 1;
for (int i = 0; i < k; ++i) {
int temp = i + 1;
for (int j = k - 1; j >= 0; --j) {
tp[i][j] = temp;
tp[i][DIV_GRID - j - 1] = temp;
tp[DIV_GRID - i - 1][j] = temp;
tp[DIV_GRID - i - 1][DIV_GRID - j - 1] = temp;
temp = max(temp - 1, 0);
}
}
for (int i = START; i < START + n; ++i) {
for (int j = START; j < START + n; ++j) {
scanf("%lld", &grid[i][j]);
}
}
for (int i = START - 2 * k + 2; i < START + n; ++i) {
for (int j = START - 2 * k + 2; j < START + n; ++j) {
ll c = 0;
for (int A = 0; A < DIV_GRID; ++A) {
for (int B = 0; B < DIV_GRID; ++B) {
c += (tp[A][B] * grid[i + A][j + B]);
}
}
result = max(result, c);
}
}
printf("Case #%d\n%lld\n", t, result);
}
return 0;
}
결과
확실히 작년보다는 준수한 결과를 얻었다. 3번문제 답을 봐도 이해 못하는 정도이니, 내 본분은 다 했다고 생각한다. 그런데도 본선 진출 가능성은 0에 수렴한다…
내년에는 본선 진출을 목표로 달려보자!