-
[BOJ] 11745: King’s Inspection
11745: King’s Inspection 풀이 M <= N+20이므로, 주어지는 그래프는 최대 20개의 간선만 제거하면 트리가 된다. 즉, 트리와 아주 유사하게 생겼다는 뜻이고, 이는 대부분 노드의 in/out degree가 1이라는 뜻이다. indegree 또는 outdegree가 2 이상인 노드를 special node로 두자. special node에서 다른 speical node까지의 경로를 압축하자. in/out degree가 1인 노드들을 모두 압축해서 하나의 간선으로 치는 것이다. 그러면 노드가 많아야 40개인 그래프가 나온다. 이 그래프에서 TSP를 하면 된다. 코드 #include <bits/stdc++.h> using namespace std; typedef long long ll;...
-
[BOJ] 10167: 금광
10167: 금광 풀이 이 문제와 비슷하게 분할정복으로 접근한다. x축을 기준으로 정렬해서, 모든 [l, r] 구간에서 최댓값을 하나씩 찾을 것이다. 시작점을 하나 정해놓고, 끝점까지 스위핑 하면서 최댓값을 찾아 주자. 스위핑이 하나 전진할 때마다 분할정복 트리를 업데이트 해 주면 된다. 이러한 구간이 많아야 3000^2개이므로 여기에 로그 붙여도 충분하다. 세그트리 업데이트 하는 느낌으로 분할정복을 하면 된다. 나는 멍청하게 구간합 업데이트를 펜윅트리 써서 했는데 여러분들은 그러지 말자. ㅋㅋㅋㅋ 까다로운 반례가 있으므로 주의하자. 코드 #include <cstdio> #include <algorithm> #include <vector>...
-
[BOJ] 16993 : 연속합과 쿼리
16993: 연속합과 쿼리 풀이 분할정복 하는 느낌, 혹은 세그트리 짜는 느낌으로 접근하면 된다. 노드 하나에 3개의 값이 들어가는데, mmax(s, e) = 가운데를 지나는 구간의 최대 합 lmax(s, e) = s를 포함하는 구간의 최대 합 rmax(s, e) = e를 포함하는 구간의 최대 합 위의 것들을 분할정복 하듯이 전처리해서 들고 있는다. 그리고 재귀 세그트리 짜듯이 쿼리를 날리면 쿼리 당 O(log N)에 답을 계산할 수 있다. 코드 #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll...
-
[잡담] 내가 문제를 내는 방법
이전 글의 연장선으로 작성하는 글입니다. 적다가 귀찮아서 때려칠 수도 있어요… 이 글의 전제는 대회를 위한 문제 세트를 만드는 과정입니다. 저는 지금까지 36문제 정도를 출제했고, 검수한 문제까지 합치면 이거보다 좀 더 많겠네요. (욱제가 낸 문제 목록) 초창기에 낸 문제들은 진짜 개구데기같은 지워버리고 싶은 문제들밖에 없는데 요즘 내는 문제들은 그래도 어디 가서 쌍욕은 안 먹을 정도로 내는 것 같습니다. (아닌가? ㅎㅎ) 문제를 내기 전에 참가자의 실력 출제진의 실력 검수진의 실력 희망하는 대회 퀄리티 를 파악해야 한다고 이전...
-
[잡담] 내가 대회를 여는 방법
이거 쓰기 전에 소개 페이지 업데이트 하고 왔는데 충격적이네요 (;;) 2019 선린 정보 알고리즘경시대회 출제 (19.08) 2019 숭고한 연합 Algorithm Camp Contest 출제 (19.08) 제3회 천하제일 코딩대회 본선 출제 (19.07) 제3회 천하제일 코딩대회 예선 출제 (19.06) 2019 SCON 개최 (19.05) 2019 SCCC 벚꽃맞이 컨테스트 개최 (19.04) 제2회 천하제일 코딩대회 본선 출제 (18.07) 제2회 천하제일 코딩대회 예선 출제 (18.07) 제1회 천하제일 코딩대회 본선 개최 (17.07) 제1회 천하제일 코딩대회 예선 개최 (17.07) 2017 선린 봄맞이 교내대회 개최...
-
2019 선린 정보 알고리즘경시대회 풀이
대회 정보: https://www.acmicpc.net/contest/view/457 문제 목록: 추가 예정 출제 및 검수 : edenooo, jh05013, tonyjjw, wookje 문제 A B C D E 출제자 wookje tonyjjw tonyjjw wookje wookje A. 비트가 넘쳐흘러 풀이 17419: 비트가 넘쳐흘러 서브태스크1: 주어진 이진수를 입력 받아서 시키는대로 짜면 됩니다. 서브태스크2: 주어진 연산은 fenwick tree 구현에 대표적으로 사용되는 연산입니다. 주어진 문자열에서 1의 개수를 세면 됩니다. 코드 # python3 input() print(input().count('1')) B. 깊콘이 넘쳐흘러 풀이 17420: 깊콘이 넘쳐흘러 서브태스크1: 사실 생각 안 해 봤습니다....
-
2019 제2회 숭고한 운영 후기
고등학교 때부터 뭔가 일이 끝나면 후기를 남기는 걸 참 좋아했었는데, 요즘에는 왠지 모르게 후기를 남기고 싶지가 않더라구요. 사실 숭고한도 후기를 남길 생각은 없었는데 여러가지로 마음이 바뀌었습니다. 항상 해오던 그런 비슷한 일인데, 왜 이번에는 끝이 아쉽고 공허한지 모르겠어요. 짧다면 짧고 길다면 긴 시간에 함께 고생한 운영진들도 이제 자주 볼 일이 없다고 생각하니 섭섭하고 마음이 별로 좋지 않네요. 그래서 지금 이 마음이 흩어지기 전에 글로나마 몇 자 남기려고 합니다. 숭고한이 무엇인가 세 학교의 네 알고리즘 동아리(숭실대 SCCC,...
-
[잡담] 제3회 천하제일 코딩대회 예선 문제 풀이
대회 정보: https://www.acmicpc.net/contest/view/303 문제 목록: 추가 예정 출제 및 검수 : jh05013, junie, messi, wookje 문제 A B C D E 출제자 wookje junie jh05013 jh05013 wookje A. 엔드게임 스포일러 풀이 0000 : 엔드게임 스포일러 문제 지문 내에 정답의 영문 표기가 적혀 있으므로 출력하면 된다. 코드 #include <cstdio> int main(){ puts("Avengers: Endgame"); return 0; } B. 귀여운 수~ε٩(๑> ₃ <)۶з 풀이 0000 : 귀여운 수~ε٩(๑> ₃ <)۶з 주어진 정수의 각 자릿수가 등차수열을 이루는지 판별하면 된다....
-
[BOJ] 9240 : 로버트 후드
9240 : 로버트 후드 풀이 로테이팅 캘리퍼스 코드 #include<cstdio> #include<algorithm> #include<tuple> #include<vector> #include<cmath> using namespace std; typedef long long ll; typedef pair<int,int> pii; struct POINT{ int x, y; bool operator <(POINT a)const { return x == a.x ? y < a.y : x < a.x; } POINT operator -(POINT a)const { return { x-a.x,y-a.y }; } }; int N; ll sq(int x){ return (ll)x*x; } ll dst(POINT A, POINT B) { return sq(A.x-B.x)+sq(A.y-B.y); } int...
-
[BOJ] 1062 : 가르침
1062 : 가르침 풀이 그냥 완전탐색하면 된다 근데 그냥 하면 시간 초과가 난다 앞뒤에 anta tica를 제거하고 잘 돌려야 한다 코드 #include <bits/stdc++.h> using namespace std; int n, k, dap, a[55]; char s[55]; int main() { scanf("%d %d", &n, &k); for (int i = 0; i < n; i++) { scanf("%s", s); for (int j = 0; s[j]; j++) a[i] |= (1<<(s[j]-'a')); } int x = (1<<0)|(1<<2)|(1<<8)|(1<<13)|(1<<19); for (int i = x; i < (1<<26);...