토론 전까지 풀지 못한 문제는 *로 표시, 후에도 풀지 못한 문제는 하나 더 붙임
1일차/ 순열과 조합
개인적으로 조합론에 매우 약해서 굉장히 힘들었던 날. 첫날이라 실습 시간이 얼마 안되어서 좀 편하긴 했다
1. comb
nCm의 마지막 0의 개수를 구하는 문제. 그냥 2와 5의 개수만 세주면 된다. 5의 개수만 세면 5C1 같은 경우에서 문제가 생김.
2. divide
정n각형을 삼각형/사각형으로 나누는 각각의 경우의 수를 구하는 문제. 삼각형은 카탈란이고, 사각형 같은 경우도 비슷한 논리로 $O(N^3)$ 짜리 DP를 짜주면 된다.
3. perm **
길이가 n인 수열이 주어졌을 때 a_i <= s_j가 되도록 수열 s를 만들 수 있는 경우의 수를 구하는 문제. 모종의 방법으로 DP를 하면 된다고 하는데 솔직히 이해를 못했다. 어... 음...
4. choose
A가 n개의 야식을 골라놓았는데 그 중 B가 m개, C가 m개 중 k개를 고르는 경우의 수를 구하는 문제이다. 그냥 3^n - 2^n이어서 5분만에 솔브.
5. coloring
N*N 격자의 모든 행과 열에 빨강, 파랑 타일이 하나씩 존재하도록 만드는 경우의 수. 너무 당연히 N! * !N이다.
6. card **
사람 A B C가 있고 각각 덱을 N, M, K장 가지고 있다. 각 카드에는 A, B, C가 써 있는데, A부터 시작해서 맨 위에서 카드 한장을 버리면 그 카드에 써 있었던 사람 차례로 이동하는 걸 반복한다. 이때 A가 가장 먼저 카드를 다 털게 해 주는 카드 배치의 수를 구하는 문제. 뭔가 이항계수의 성질을 잘 이용한다는데 난 잘 모르겠다
2일차/ 고오급 자료구조
어려운 문제가 한 문제도 없었는데 코딩에서 말리고 꼬여서 순위는 낮았다. 으엑
1. segtest
세그먼트 트리 연습문제. 뚝 딱
2. rating
2d penwick 연습문제.
3. navigation
https://www.acmicpc.net/problem/1761
"LCA 구할 때 세그먼트 트리 쓰는 흑우 없제?" 라는 말이 뒤에서 많이 들렸다. Sparse Table 쓰는게 실제로도 더 좋은듯
4. lights
https://www.acmicpc.net/problem/1395
레이지 프로파게이션 연습문제.
5. katana *
중복된 수가 없는 n개의 수가 있는데, 각 수의 점수는 수가 k일때 2^k임. 구간이 q개 주어졌을 때 q개 구간을 구간에 속하는 수들의 점수 합 순으로 정렬하기. 그냥 세그랑 정렬함수를 적당히 잘 비비면 된다. rectangle 디버깅 하느라 시간이 없어서 코딩을 못 끝내고 토론 후 30분 정도 후에 AC.
6. gcd
동적 세그먼트 트리 연습문제.
7. rectangle *
https://www.acmicpc.net/problem/3392
좌표만 늘린 버전. 좌표압축 해서 박아주면 되는데 세그 노드 종료조건을 잘못짜서... 흑흑
hyea 조교님이 스위핑을 쉽게 하는 법을 가르쳐주셨다. imeimei 조교님이 이런 유형에서 세그를 깔끔하게 관리하는 법을 가르쳐주셨다.
3일차/ 컴퓨터 과학의 최근 동향
랜덤따리 랜덤따
1. genome
기초 Sequence Allignment Problem
2. Network (100/110) **
탑코더 회사는 연결되지 않은 노드 중 하나를 잡아 연결시키는 방식으로 트리 생성. 앳코더는 완전한 랜덤 생성. 임의의 트리가 하나 주어졌을 때 어느 회사가 만든 트리인지 판별. N=64, 80% 이상 정답이면 100점, N=24, 85% 이상 정답이면 110점.
100점은 그냥 차수가 4나 5인지만 고려해서 찍으면 됨. 110점을 먹으려면 실제로 확률을 어느 정도 비트DP같은 걸로 계산해줘야 한다고 함. 100점만 긁고 빤스런했음
3. classify (99.4/100)
시점이 같은 두 반직선으로 두 종류의 점을 분리. 디스크립션이 무서워서 단 3명만 유효한 제출을 했는데, 사실 100점에 가까운 점수를 받으려면 생각을 꽤 많이 해야 하는 난도 있는 문제지만 몇십점만 긁기에는 개꿀문제였다. 그냥 숫자 4개만 찍어도 20점을 주고 랜덤 조금만 돌려도 50점을 주며, 컨벡스헐을 찾으면 70점을 주고 거기서 랜덤을 잘 돌리면 99점을 주는 (컨벡스헐을 안다면) 좋은 문제. 발표를 할 때 컨셉을 너무 뭐같이 잡고 쉬운데? 이러면서 발표했는데 고깝게 본 분들이 좀 있었나 보다. 앞으로는 그러지 말아야지.
4. distinguish (30~40점 내외) **
for(int I=0;i<N;++i) { X = rand(i – N-1); swap(a[i], a[X]); } (완전 랜덤)과
for(int I=0;i<N;++i) { X = rand(1 – N-1); swap(a[i], a[X]); } 중 한쪽을 구별하는 문제.
엔트로피 잡고 적절히 계산해 주면 낮은 점수를 긁을 수 있고, 높은 점수를 받으려면 매우 정밀한 계산을 해야 한다고 한다.
5. language (70점 내외) *
https://oj.uz/problem/view/IOI10_languages
처음 접근은 빈도수로 접근하는 거였는데, 2글자/3글자로 묶어서 하는게 압도적으로 좋은 점수를 받는다. 이유는 잘 모르겠음.
4일차/ 계산 기하
정확히 6문제를 조지고 더 이상 풀 수 있는 문제가 없어서 놀았음. 기하시러
1. area
단순다각형 넓이 연습문제
2. position
Point In Polygon 연습문제
3. convex
Convex Hull 연습문제
4. simplepolygon **
단순다각형 만드는 문제였는데, 맨 마지막 예외처리를 못해서 틀림.
5. overwatch **
n개의 점 중 4개 이하를 잡아 만들 수 있는 넓이 최대, 접근은 맞게 했으나 rotating calipers는 반례가 있고 삼분탐색이나 cht 비슷한 느낌으로 접근해야 $O(n^2 lg n) $이나 $O(n^2)$으로 풀 수 있었음. 흐규흐규
6. war
두 종류 점이 있는데 한 점이 다른 팀 세 점에게 둘러싸이면 항복함. 이때 항복하는 점들의 개수 세기. 그냥 Convex Hull 연습문제
7. dejavu
유클리드 거리 최대값. Rotating Calipers 연습문제
8. lines
n,p에 대해 np/100개의 점을 지나는 직선의 유무 판단. p가 20~100이라서 랜덤을 돌려도 매우 높은 확률로 AC를 받을 수 있음. 랜덤따리 랜덤따.
9. kiwi **
n개의 점으로 만들어진 다각형 안에 r=4인 원 2개를 넣을수 있는가? 있다면 좌표 출력.
(길이는 최소 30, 사잇각은 18 – 144도 / n <= 1e5)
굉장히 구현이 빡세 보이더라. 시도는 해봤는데 예외도 많고 실수오차 문제도 힘들어서 포기
10. hyperbeam **
길이만큼 가중치가 붙어있는 x축에 평행한 선분이 y개 있을 때 직선을 하나 쏴서 겹치는 선분들의 가중치 합을 최대화 하는 재밌는 문제였음. $O(n^3)$ 에서 자료구조를 덕지덕지 붙여 줄이는걸 생각했는데 생각해보니 인치웜도 되는거같음. 발표하신 분 풀이는 자료구조를 붙이는 풀이
5일차/ 그래프 이론의 응용 (플로우와 SCC)
항상 어려운 분야. 그래도 제일 재밌긴 했음
1. flow
https://www.acmicpc.net/problem/6086
2. rbtree
n개의 점이 있을 때 각 점은 R 아니면 B임. 각 학생이 3개의 예측을 할 때 적어도 그 중 2개는 맞게 점의 색깔을 배정할 수 있는가? 기초적인 투샛문제임.
3. hyperbeam2
https://www.acmicpc.net/problem/1867
4. uig1 **
단위 구간 그래프에서 최소 정점 덮개, 최대 독립집합, 최대 클리크 수, 최소 채색 수, 그리고 가능한 가짓수들을 출력. 가짓수 빼고 출력하면 40점을 줬음. 퍼펙트 그래프 성질때문에 잘 DP를 돌릴 수 있는 것 같긴 한데... 음...
5. uig2
단위 구간 그래프에서의 해밀턴 사이클. 단순구현문제
6. traffic **
평면그래프에 점이 n개가 있는데 x좌표가 0인 점 각각마다 몇 개의 x좌표가 최대인 점으로 갈 수 있는지 개수를 세 줘야 함. 평면 그래프의 성질을 이용해서 SCC DAG에서의 DP를 돌리는 문제인데 정말로 갓문제인것같음. 꼭 풀어봐야지
7. wakeup
https://www.acmicpc.net/problem/4013
SCC DP 연습문제 (치고는 좀 어려움)
8. tron **
장애물 있는 격자 그래프에서 서로 반복해서 이동할 때 이동하지 못하는 쪽이 진다. 각 칸마다 승자를 표시. 이분 매칭에서 증가 경로 가지고 뭘 하는 거 같은데 솔직히 잘 이해 못했다. 너무 갓문제임.
9. circle **
uig에서 n개의 두 정점 쌍 중 하나의 정점만 선택하여 간선이 하나도 없도록 하고 싶다. 이때 uig의 최대 d 값을 묻는 문제. 파라메트릭에 세그를 박고 세그 위에서 투샛을 돌리면 된다. ㄹㅇ 갓문제인거같고 반드시 꼭 풀어볼거임.
'일상' 카테고리의 다른 글
| Mstone Groove T87A 게이트론 저소음 갈축 후기 (0) | 2019.12.23 |
|---|---|
| 최근 MBTI 약식검사 결과 (2) | 2019.10.18 |
| INTP's Life (2) | 2019.10.11 |
| NYPC 본선 가요 (1) | 2018.09.18 |
| 블로그를 처음 시작해보면서 (1) | 2018.01.31 |
