Little Piplup 5월 5일 팀연습
알고리즘 문제풀이/Team Little Piplup 2019. 5. 7. 03:59PS 늅늅으로 구성된 Little-Piplup 팀으로 앞으로 대회 등등을 위해 같이 공부하기로 헀다.
처음은 서로 어떤 느낌인지도 볼 겸 해서, Codeforces 에서 Div 1 + 2 Combined 인 라운드 하나 잡고 셋이 같이 돌았다.
팀원 : Coffeetea, Diordhd, Gratus907(나)
http://codeforces.com/contest/914
우리한테는 먼 고대의 라운드. 우리가 대학 들어와서 프로그래밍을 처음 시작했고(기억이 맞다면, diordhd는 안드로이드 쪽은 조금 경험이 있지만 PS는 셋다 대학와서 시작했다) , 그게 2018년임을 생각하면 2018년 1월은 Hello World도 출력 못했을 시점이다.
우리가 지금 시점에서 풀 수 있는 문제는 다 풀었다고 생각하지만, 사실 구현에서 좀 말린 느낌은 있다.
| 문제 번호 | A | B | C | D |
| 문제 레이팅 | 1100 | 1300 | 1800 | 1900 |
|
AC 시간 |
00:04 | 00:11 | 01:48 (+5) | 02:51(+2) |
일단 아무도 세그트리를 짜본적 없는 순수 뉴비팀인데, 어디선가 이것저것 주워들은건 조금씩 있어서 구현실력이 생각을 조금 심하게 못따라가는 편이다. 경험 부족인 탓도 있겠지만.
A. Perfect Squares
Solution, Code : Gratus907
내가 VSCode 컬러 설정한다고 (Pitch-Black 테마같은게 아니면 심각하게 불편하다. 다른 두명이 이런거에 크게 신경을 안써서 너무 다행이다. 나는 개인적으로 '검은 배경' 인 주제에 완벽하게 검지 않은 화면이 마음에 들지 않는다.) 컴퓨터 앞에 앉아서 시작했기 때문에, 그냥 내가 앉아서 아무렇게나 짰다. 어차피 1초라는 제한시간은 넘쳐흐르기 때문에 그냥 모든 경우를 확인해서 제곱수인지 찾았는데, 머리를 비운채 키보드를 치다 보니 그냥 sqrt 비교하는게 빨랐을 것 같다는 생각은 들었다. 아무튼 영어 해석이 오래 걸려서 4분에 AC를 받았다.
코드
|
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 <bits/stdc++.h>
#define ll long long
using namespace std;
int arr[1020];
int main()
{
int n;
int ans = INT_MIN;
scanf("%d",&n);
for (int i = 0; i<n; i++)
{
scanf("%d",arr+i);
bool flag = true;
for (int j = 0; j<=1000; j++)
{
if (j*j==arr[i])
{
flag = false;
break;
}
}
if (flag == true)
{
ans = arr[i]>ans? arr[i]:ans;
}
}
printf("%d",ans);
}
|
B. Conan and Agasa play a Card Game
Solution : diordhd, Coffeetea
Code : Coffeetea
A번 AC 확인하고 컴퓨터 앞에서 일어나서 "B번은 무슨 문제냐" 라고 물어본 시점에 이미 coffeetea가 코딩을 시작하고 있었다. 대충 diordhd한테 들어보니 맞는말인 것 같기도 하고, 이 두명이 Codeforces Div2 B번을 못풀었진 않았을 것이므로 그냥 diord랑 같이 C번을 보기로 했다.
숫자가 적힌 카드가 잔뜩 있고, 여기서 플레이어 Agasa 와 Conan 이 교대로 카드를 가져가되 (코난이 먼저 시작한다), 카드를 한 장 가져가면 그보다 작은 숫자가 쓰인 카드는 모두 사라진다. 누가 이길까?
뭐 이런 문제인데, 가장 큰 카드의 Parity 를 보고, 그 다음 카드의 Parity 를 보고, ... 그래서 중간에 한번이라도 홀수면 그보다 작은 카드를 볼 필요 없이 먼저 시작하는 사람이 이긴다. 후공이 이기는 방법은 모든 수가 짝수번 등장하는 경우뿐이다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int num[100005];
int main(){
int n;
scanf("%d", &n);
int temp;
while(n--) {
scanf("%d", &temp);
++num[temp];
}
for ( int i = 100000 ; i >= 1 ; --i ) {
if ( num[i] % 2 == 1 ) {
printf("Conan");
return 0;
}
}
printf("Agasa");
}
|
(세명 중 나만 for문 등을 쓸 때 여는 괄호를 아래 줄에 놓는다(이걸 BSD Style이라고 한다). 종이에 뽑기에는 BSD가 매우 불리하지만, 나는 블록의 종속관계가 훨씬 잘 보여서 선호한다. 프로그래밍을 작년 3월에 처음으로 시작했는데, 왠지 저렇게 쓰고 싶어서 그렇게 했는데 생각보다 많은 사람들이 저런 스타일을 쓴다고 해서 그냥 그러기로 했다.)
C. Traveling Salesman and Special Numbers
Solution : diordhd, Coffeetea, gratus907 (사실 나는 별로 이 문제에서 한 게 없다)
Code : Coffeetea
자연수 $x$에 대하여 $f(x)$ 을 다음과 같이 정의한다.
\[ f(x) = \text{number of bits on in signed int representation of } x \]
이때 $k$ 번 $f$ 함수를 반복 적용해서 1을 얻을 수 있는, $n$ 이하의 자연수를 구하는 문제.
($n \leq 2^{1000}$ 이라는 뭔가 엄청나 보이는 제약조건이 걸려있다)
어차피 한번 $f(n)$ 을 적용하면, 1000 이내로 들어온다는 사실을 이용하고, 적당히 이항계수를 이용하여 가능한 경우의 수를 세 주면 된다. 그런데 $_{1000}C_{500}$ 같은 수를 직접 구할 수 없으므로, $_nC_m % p$ 를 잘 이용해야 한다.
정말 딱 여기까지 얘기하고, "적당히 이항계수를 이용", "잘 센다" 는 정도 Notion만 가지고 coffeetea가 컴퓨터를 다시 잡았다. (평소에 coffeetea가 나보다는 구현이 꼼꼼하기 때문에 이런문제 구현에 나보다 나을 것 같았다.) 이 문제가 뭔가 이상한 코너케이스에 그렇게 많이 걸릴줄은 몰랐는데, 무려 5번을 틀리고 1시간 40분동안 디버깅을 해서 AC를 받았다.
다행히(?) 나랑 diord가 D에서 알고리즘 생각 이후에도 구현을 어떻게 할지에 대해서 충분히 말려 있었기 때문에 컴퓨터 병목이 난다거나 하지는 않았다만...
코드
|
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
|
#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define mod 1000000007
int c[1005][1005];
int way[1005];
int change(int k) {
int ret = 0;
while(k) {
if ( k % 2 == 1) ++ret;
k >>= 1;
}
return ret;
}
int getc (int a, int b){
if ( c[a][b] == -1 ) {
if ( a < b ) c[a][b] = 0;
else if ( b == 0 ) c[a][b] = 1;
else if ( b == 1 ) c[a][b] = a;
else if ( b > a/2 ) c[a][b] = getc(a, a-b);
else c[a][b] = (int) ( ( (long long int)getc(a-1, b) + getc(a-1, b-1) ) % mod );
}
return c[a][b];
}
char n[1005];
int length;
int k;
int smaller(int left, int numOfOne) {
if ( left < numOfOne) return 0;
if ( numOfOne == 0) return 1;
if ( left == 0 ) return 0;
int ret = getc(left - 1, numOfOne);
int p = left - 1;
for ( ; p >= 1 && n[length - p] == '0' ; --p ) {
}
ret = ( (long long int) ret + smaller(p, numOfOne - 1) ) % mod;
return ret;
}
int main(){
for ( int i = 0 ; i < 1005 ; ++i ) {
for ( int j = 0 ; j < 1005 ; ++j ) {
c[i][j] = -1;
}
}
for ( int i = 2 ; i <= 1000 ; ++i ) {
way[i] = way[ change(i) ] + 1;
}
scanf("%s", n);
length = strlen(n);
scanf("%d", &k);
long long int ret = 0;
if ( k == 0 ) {
printf("1");
return 0;
}
for (int li = 1 ; li <= length ; ++li ) {
if ( way[li] == k-1 ) {
if ( li == 1 ) {
ret = ( ret + smaller(length, li) - 1) % mod;
} else {
ret = ( ret + smaller(length, li) ) % mod;
}
}
}
printf("%d", (int)ret);
}
|
D. Bash and a Tough Math Puzzle
Solution : diordhd, gratus907
Code : gratus907
이번 연습에서 제일 "문제 푸는 과정" 처럼 풀었다. 이 모든 과정을 대략 2배속으로 가속하는 노력이 필요하다.
최대 50만개의 수가 들어 있는 배열에서 두 종류의 쿼리가 최대 합 40만번 주어지는데,
- 쿼리 1 : 어떤 수 $x$ 가 구간 $(l, r)$의 "거의 gcd" 인지 여부를 출력.
- 쿼리 2 : $i$ 번째 수를 $k$ 로 바꾼다.
여기서 "거의 gcd" 라 함은, 그냥 구간의 gcd이거나, 구간 내의 자연수 하나를 임의의 자연수로 바꾸었을 때 구간의 gcd이면 "거의 gcd" 라고 한다.
조금만 생각해보면, 쿼리 1은 길이가 $P$인 구간 $[l, l+P)$ 이 주어졌을 때, $P$ 개 중 적어도 $P-1$ 개의 수가 $x$ 를 약수로 갖는지와 동치이다. 약수로만 가진다면, 나눠지지 않는 수 하나를 $x$ 로 바꿔서 gcd를 $x$ 까지 줄일 수 있으니까.
그런데, 제한 시간상 50만개의 구간을 40만번 돌면서 나눠보는 것은 불가능하다. 게다가 업데이트도 있어서 전처리도 불가능하다. 대략 이 시점 쯤에서 둘 다 이 문제를 Segment Tree 로 풀 수 있다는 것과, Segtree를 짜본적이 없는 우리는 이 문제를 풀 수 없을 것이라는 생각을 했었다. 그리고 여전히 Segtree를 어떻게 쓸 것인지도 잘 모르고 있었고.
이게 라운드 시작 50분 쯤이었는데, 아직도 Coffeetea는 뭔지 모를 테캐랑 싸우고 있었다. (라운드가 끝나고 테캐를 까보니 이때 30분동안 고통받은 케이스는 "1 1" 이었다;;;)
아무튼, 그동안 열심히 머리를 굴려서 알고리즘을 얻었다.
- 세그먼트 트리에, 각 구간의 gcd를 저장하는 식으로 구성한다.
- 쿼리 1이 들어오면, 구간 $(l, r)$ 에 해당하는 노드들을 보면서, 이 노드들이 가진 value (어떤 구간의 gcd) 가 $x$ 로 나누어 떨어지는지 확인한다.
- 나누어 떨어지지 않는다면, 좌우 자식 노드를 본다. 만약 구간 밖에 있는 노드가 있다면 버린다.
- 어느 시점에라도 2개 이상의 구간내 노드가 나누어 떨어지지 않는 값을 갖는다면 거의 gcd가 아니다.
즉, "나누어 떨어지지 않는 노드 하나" 는, 그 노드에 해당하는 구간에 적어도 한개 이상이 $x$ 로 나누어 떨어지지 않음을 의미한다는 것을 이용하는 것이다.
이렇게 하면 쿼리 1은 $\mathcal{O}(\log{n})$ 시간에 답할 수 있고 (약간의 상수가 필요하지만), 쿼리 2는 gcd를 계산하면서 올라가야 하기 때문에 $\mathcal{O}(\log{n}\log{M})$ ($M$은 배열에 들어갈 숫자의 최댓값, 여기서는 $10^9$) 정도 시간이 걸린다. 어쨌든 둘 다 충분히 빠른다.
여기까지 생각한다음 어떻게 구현할지 한 30분 정도 헤매고 있으니 드디어 C번 AC를 받아왔다. (이시점이 110분이다. 이 라운드는 180분 짜리니까, 대략 70분 정도 남았다)
그리고 나는 세그먼트 트리에 대해 딱 다음 두 줄의 문장만 들어본 상태였다.
1. 세그먼트 트리는 구간 값을 저장해서 큰 구간 값을 구하는 자료구조이다.
2. 저장할 숫자 $n$의 몇 배 정도 되는 큰 배열에다가 업데이트를 해가면서 만들 수 있다.
팀원들이 '아마 안 되겠지만' E번을 생각하는 동안 내가 무려 65분이 걸려서 세그트리를 구현했고, 어차피 코너케이스가 있을 만한 문제는 아니라는 생각에 제출해서 맞았다 (중간에 2번 실수로 무한루프 돌았다). 팀원들이 테캐를 하나씩 만들어와서 넣어보고 맞았다고 확신하기도 했고. 겨우 9분 남은 시점에 간신히 맞았다.
코드
|
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
|
#include <bits/stdc++.h>
#define ll long long
#define mod 1000000007
#pragma GCC optimize("Ofast")
#define gcd(A,B) __gcd(A,B)
using namespace std;
int segtree[2002000];
int treesp = 1;
int ans = 0;
void query(int rt, int l, int r, int s, int e, int x)
{
if (ans>2)
return;
if (rt > treesp*2)
return;
if (e < s|| r < l || r < s || e < l)
return;
if ((l<=0) || (r >= treesp*2) || (r<l) )
return;
if (segtree[rt]%x == 0)
return;
if ((l <= s) && (e <= r))
{
while(rt < treesp)
{
if (segtree[rt*2]%x)
{
if (segtree[rt*2+1]%x)
{
ans+=10000;
return;
}
else
rt *= 2;
}
else if (segtree[rt*2+1]%x)
rt = rt*2+1;
}
ans++;
return;
}
int m = (s+e)/2;
query(rt*2,l,r,s,m,x);
if (ans>=2)
return;
else
query(rt*2+1,l,r,m+1,e,x);
}
void update(int pos, int val)
{
segtree[treesp+pos-1] = val;
int u = (treesp+pos-1)/2;
while(u >= 1)
{
segtree[u] = gcd(segtree[u*2],segtree[u*2+1]);
u/=2;
}
}
int main()
{
int n;
int q;
scanf("%d",&n);
while (treesp<n)
treesp*=2;
for (int i = 0; i<n; i++)
scanf("%d",segtree+(treesp+i));
for (int i = treesp-1; i>=1; i--)
segtree[i] = gcd(segtree[2*i],segtree[2*i+1]);
scanf("%d",&q);
for (int i = 0; i<q; i++)
{
ans = 0;
int t,l,r,x;
int pos,val;
scanf("%d",&t);
if (t==1)
{
scanf("%d %d %d",&l,&r,&x);
query(1,l,r,1,treesp,x);
if (ans >= 2)
printf("NO\n");
else
printf("YES\n");
}
else if (t==2)
{
scanf("%d%d",&pos,&val);
update(pos,val);
}
}
}
|
아직 실력도 많이 부족하고, 특히 구현에서 엄청 말리는 뉴비팀이지만 같이 셋 돌면서 꽤 많은 교훈을 얻었다.
일단, 팀원들 중 누군가가 거의 100% 이 문제를 빠르게 코딩할 수 있다거나 하는 상황이 아니라면, 가능한한 컴퓨터 앞에서 디버깅에 보내는 시간을 줄이고 충분히 의견을 교환한 후에 확실한 솔루션을 가지고 누군가 한명이 한번에 코딩을 빠르게 하는게 이득일 것이라는 점이다. C번에서 10~20분 정도만 생각하는 시간을 늘렸다면 구현 시간을 40분 이상 줄일 수 있었을 것 같은데, 누군가가 이미 거의 다 짠 코드를 디버깅하는건 셋이 같이 할 수 있는 작업이 아니었기 때문에 굉장히 시간 낭비가 심했다. 그리고 coffeetea 도 확실한 솔루션이 아닌 대략적인 감만 가지고 맞춰서 코딩을 시작해서인지 이상한 테캐에서 많이 말렸고, 그러면서 체력/정신력 소모도 굉장히 심했던 것 같다.
트리, 그래프 알고리즘에 대해 잘 모르는 상황이라, 그런부분들을 중점으로 공부해야 할 것 같다는 얘기도 나왔다. E번은 끝나고 다음날인 오늘 diord가 "Centroid Decomposition이라는걸 쓰는 문제고, 그게 뭔지 알면 사실 그렇게 어렵지 않은것 같더라" 라는 얘기를 했다. 내가 D번 구현하는동안 E번을 "어떤 기준을 잡아서 분할 정복한다. 그런데 그 기준점을 어떻게 잡아야 하냐?" 는 정도까지 얘기를 했었다는데, 그 알고리즘이 정확히 Centroid Decomposition 이었다.
학기중에는 쉽지 않지만, 가능하면 각자 코드포스 라운드 뛰고 다음날 리뷰하는 식이나, 풀어볼만한 문제 공유하면서 같이 연습 하기로 했다. 파이팅! :)
'알고리즘 문제풀이 > Team Little Piplup' 카테고리의 다른 글
| Little Piplup 6월 24일 팀연습 (0) | 2019.06.26 |
|---|---|
| Little Piplup 6월 21일 팀 연습 (1) | 2019.06.22 |
| Little Piplup 6월 2일 팀 연습 (0) | 2019.06.03 |
| Little Piplup 5월 19일 팀연습 (1) | 2019.05.22 |
| Road to Expert Round 4 (0) | 2019.05.13 |
