-
[BOJ] 2492: 보석
2492: 보석 풀이 이 풀이를 참고하자. 복붙 날먹 꺼-억 아 이 문제는 사각형이 격자를 벗어나면 안 되니까 주의하자. 코드 #include <bits/stdc++.h> using namespace std; int n, m, t, k; int dap, dap_x, dap_y; struct abc { int x, y; } a[111]; void go(int x, int y) { int cnt = 0; for (int i = 1; i <= t; i++) { if (x <= a[i].x && a[i].x <= x+k && y <= a[i].y && a[i].y...
-
[BOJ] 2496: 금강석
2496: 금강석 풀이 (x, y)의 좌표계를 변환하자. (x, y) => (x+y, x-y)로 좌표를 변환시키면 좌표계가 45도 기울어지고, 점 사이의 간격이 root(2)배만큼 늘어난다. 좌표계를 돌리고 나면 마름모가 정사각형이 되므로, 문제를 풀기 한결 수월해진다. T가 100밖에 안 된다는 점을 주목하자. 정답에 포함되는 어떤 금강석들의 집합이 있다고 하자. 이 금강석들을 포함하는 사각형은, 얘네들을 모두 포함하는 선에서 이리저리 잘 옮길 수 있을 것이다. 정답을 벗어나지 않는 선에서, 사각형을 최대한 오른쪽 아래로 땡겨보자. 항상 두 개의 금강석이 왼쪽과 위쪽 변에...
-
[잡담] 최근에 재밌게 푼 유형
최근에 접한 문제들 중에서 재밌게 풀었던 것들을 몇 개 적습니다. set에 다항식 넣기 17196: Cow Steeplechase II 선분이 N개 주어집니다. 단 하나의 선분을 제거하면, 어떤 선분쌍도 교차하지 않음이 보장됩니다. 제거해야 하는 선분은? x축 정렬하고 스위핑 합니다. 선분의 시작점을 만나면 set에 넣고, 끝점을 만나면 set에서 뺍니다. i번째 선분을 a[i] = { sx,sy, ex,ey }라고 합시다. 선분의 시작점을 만나면: (a[i], a[i].sy에서 위로 가장 가까운 선분), (a[i], a[i].sy에서 아래로 가장 가까운 선분) 두 쌍을 교차판정 합니다. 선분의 끝점을...
-
[BOJ] 10759: 팰린드롬 경로3
10759: 팰린드롬 경로3 풀이 d[i][j] = 문자열의 길이가 k이고, i행에서 시작해서 j행으로 끝나고, 그 문자열의 중심이 배열의 대각선(왼쪽 아래~오른쪽 위)에 있을 때, 그 문자열이 팰린드롬인 경우의 수 d[k][i][j] = d[k-2][i][j]+d[k-2][i+1][j]+d[k-2][i][j-1]+d[k-2][i+1][j-1] 식은 위와 같고, 배열은 k를 토글링 해서 n^2개만 사용할 것이다. (1,1)~(n,n)의 문자열은 길이가 항상 홀수이다. 중앙의 diagonal 대각선을 기준으로, 팰린드롬의 길이를 앞뒤로 2씩 확장해 나갈 수 있다. (a,b)~(c,d)의 중심이 대각선에 겹치려면, (a-1)+(b-1) = |(c-n)+(b-n)|을 만족해야 한다. (두 점이 각 끝점으로부터 떨어진 거리가 같아야 한다.) a와...
-
[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: 사실 생각 안 해 봤습니다....