반응형

이번 18년도 쉐이크가 열린다는 소식에 참가하여 쉐이크를 18.05.27 일요일에 2시~6시까지 진행하게 되었다.


쉐이크 사이트

http://shake.codes/ 


오늘은 예선으로 총 7문제가 나왔는데 나는 4문제를 풀고 1문제를 긁어서 


교내에서는 1등을 했지만, 다른 학교와 비교했을때는 종합순위 5위를 하였다.


우선 쉐이크 문제에 대해 한번 이야기 해보고자 한다.



(krar003이 내 ID이다.)


A번 문제는 단순한 구현 문제였고




B번 문제는 디스크립션이 어렵게 생겼었지만 그냥 각 도형의 끝점을 벡터에 넣어 정렬 후 출력하면 되는 문제였다.




C번 문제에서 조금 막히기 시작했는데 처음에는 투포인터로 생각했다가 그렇게 하면 안된다는걸 한 30분 정도 생각한 이후 깨달았고 dp로 해결하기 시작했다.


점화식은 DP[i][j] = min(DP[i-1][j], DP[i][j-1], DP[i-1][j-1]) + arr[i][j] 였다.




D번 문제는 이분탐색 문제였고 정답을 기준으로 이분탐색을 하면 문제를 쉽게 해결 할 수 있었다.


이때 visit라는 배열이 필요했는데 처음에는 bool로 선언 후 memset을 하니 TLE가 나서 int형으로 바꾼 후 visitCnt를 이용하였다.


http://www.crocus.co.kr/744




E번 문제는 뭔가 수학적인 지식이 필요해 보였는데 규칙을 찾지 못해 풀지 못했다.




F번 문제는 이분탐색을 두번쓰면 정답이 나올 것 같아서 계속진행했지만 결국 풀지 못했고, small만 긁어서 제출했다.


왜 안되는지, 정해가 무엇인지 풀이가 나오면 좀 알고싶다.



G번은 따로 보지 못했다.




이번 쉐이크에서 아쉬운 점은 서버가 터져버려서 채점이 1시간 기다려도 되지 않는 현상때문에 그다음 문제를 보긴했으나 현재 문제가 맞는지 틀린지 알 수 없어 답답하였다.


본선에서는 그러지 않겠지만, 좀 더 좋은 관리가 있었으면 어땠을까 한다.


하지만 문제 내용자체는 정말 괜찮았던 것 같다.







소스 코드 : 


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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
//A번
#include <iostream>
#include <cstdio>
#include <string>
 
using namespace std;
 
typedef long long ll;
 
int main() {
    int s1, s2;
    scanf("%d %d", &s1, &s2);
 
    for (int i = 0; i < s1; i++)
    {
        ll a, b;
        scanf("%lld %lld", &a, &b);
 
        if (a != b)
            return !printf("Wrong Answer\n");
    }
    for (int i = 0; i < s2; i++)
    {
        ll a, b;
        scanf("%lld %lld", &a, &b);
 
        if (a != b)
            return !printf("Why Wrong!!!\n");
    }
    printf("Accepted\n");
 
 
    return 0;
}
 
//B번
#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
 
using namespace std;
 
typedef long long ll;
 
double getDist(double x, double y) {
    return (x*x + y*y);
}
int main() {
    int n, k;
    scanf("%d %d", &n, &k);
 
    vector<double> vc;
    for (int i = 0; i < n; i++) {
        int m;
        scanf("%d", &m);
 
        double minVal = 0.0;
        for (int j = 0; j < m; j++)
        {
            double x, y;
            scanf("%lf %lf", &x, &y);
 
            double ret = getDist(x, y);
 
            //printf("ret :: %.lf\n", ret);
            minVal = max(ret, minVal);
        }
        //printf("inval :: %.lf\n", minVal);
 
        vc.push_back(minVal);
    }
 
    sort(vc.begin(), vc.end());
 
    printf("%.2lf\n", vc[k - 1]);
 
    return 0;
}
 
//C번
#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
 
using namespace std;
 
typedef long long ll;
 
int a[2002], b[2002];
ll dp[2002][2002];
 
int getDist(int x, int y)
{
    return (a[x] - b[y]) * (a[x] - b[y]);
}
int main() {
    int n;
    scanf("%d", &n);
 
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++)
        scanf("%d", &b[i]);
 
    int x = 0, y = 0;
    ll ans = 0;
 
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n; j++)
            dp[i][j] = 1e16;
 
    dp[0][0] = 0;
 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            dp[i][j] = min({ dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1] }) + getDist(i, j);
 
    printf("%lld", dp[n][n]);
    return 0;
}
 
 
//D번
 
#include <iostream>
#include <cstdio>
#include <deque>
#include <algorithm>
#include <memory.h>
using namespace std;
 
int arr[100002];
int visit[500002];
int visitCnt = 1;
 
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
 
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);
 
    int start = 0, end = 10000000;
 
    int ans = 0;
    while (start <= end)
    {
        int mid = (start + end) / 2;
        int cnt = 0;
        int hit = 0;
        bool isFind = false;
 
        visitCnt++;
        for (int i = 0; i < n; i++)
        {
            if (visit[arr[i]] != visitCnt)
            {
                visit[arr[i]] = visitCnt;
                cnt++;
            }
            else
            {
                visitCnt++;
                int j = i;
                i--;
                while (1)
                {
                    if (arr[i] == arr[j])
                        break;
                    i--;
                }
                cnt = 0;
            }
 
            if (cnt == mid)
            {
                hit++;
                if (hit == m)
                {
                    isFind = true;
                    break;
                }
                visitCnt++;
                cnt = 0;
            }
        }
 
        if (isFind)
        {
            start = mid + 1;
            ans = max(ans, mid);
        }
        else
            end = mid - 1;
    }
 
    printf("%d", ans);
    return 0;
}
 
 
// F번
 
#include <iostream>
#include <cstdio>
#include <deque>
#include <algorithm>
 
using namespace std;
 
typedef long long ll;
 
int arr[20002];
 
ll ansTime = 1e18, ansBuff = 1e18;
int main() {
    int n;
    scanf("%d", &n);
 
    int maxBuff = 0;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
        maxBuff = max(maxBuff, arr[i]);
    }
 
    int t;
    scanf("%d", &t);
 
    for (ll mb = 1; mb <= maxBuff; mb++)
    {
        ll total = 0;
        for (int j = 0; j < n; j++)
        {
            int val = arr[j];
            while (val)
            {
                if (val < mb)
                {
                    total = total + (t + mb);
                    val = 0;
                }
                else
                {
                    int rem = val / mb;
                    total += rem*(t + mb);
 
                    val = val - (rem * mb);
                }
            }
        }
 
        if (total <= ansTime)
        {
            ansTime = total;
            ansBuff = (ll)mb;
        }
    }
    printf("%lld %lld", ansTime, ansBuff);
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus



반응형
저작자표시 비영리 변경금지

'Applied > Programming Contests' 카테고리의 다른 글

shake! 경인지역 6개대학 연합 프로그래밍 경시대회 본선 후기  (0) 2018.07.31
2018 Hdac HACKATHON 후기  (0) 2018.07.07
[Codeforces] Codeforces Round #468 (Div. 2, based on Technocup 2018 Final Round) 이야기  (0) 2018.03.11
[Codeforces] Educational Codeforces Round 38 (Rated for Div. 2) 이야기  (0) 2018.02.25
[Codeforces] Educational Codeforces Round 37 (Rated for Div. 2) 이야기  (0) 2018.02.13

티스토리툴바