2021. 1. 14. 21:17ㆍPS/Problem Solving
Educational Codeforces Round 102 (Rated for Div. 2)
Dashboard - Educational Codeforces Round 102 (Rated for Div. 2) - Codeforces
codeforces.com
나름 잘했다고 생각한다. 다만 에듀코포여서 모든 문제의 점수가 같다
따라서 빨리 풀고 적게 틀리는게 관건
C를 못 푼게 살짝 심각..
코포에서 자주 쓰이는 알고리즘을 저장한 템플릿을 어서 빨리 만들어야 겠다. B,D,E 구현이 느렸다
E는 재밌는 문제다. 고급 알고리즘 시간에 다룬 그래프 변환을 여기서 써먹게 됐다.
주어진 그래프를 문제의 정답을 그대로 유지하되, 정점과 간선을 추가/삭제하는게 그래프 변환이다.
여기서는 정점을 상태에 따라 여러 정점으로 나눈다.
업솔빙 목록
inversion 개수를 유지하면서 가능한 큰 permutation을 찾는 문제.
자고 일어나서 해야지..
이런 관찰에 굉장히 약한데, 코포 애드혹 문제를 많이 풀어보자.
에듀코포 많이 치는게 도움이 될듯
최종답: [1 ... k - (n-k) -1] [k .... k - (n-k)]
Maximum Flow 문제 -> 라왈리님 소스 보니까 maximum Flow Struct가 있던데 알고리즘마다 struct를 만들어 놓는게 편하겠더라
neal도 보니까 Tree, Graph struct를 따로 만들어놓고 사용함.
얘는 FFT네
라왈리님 코드들이 대체로 깔끔하다.
레드 가려면 능지와 준비성을 갖추자.
오늘 수학 문제를 풀면서도, 코포를 하면서도 느낀게 있다.
결과를 기준으로 역산하는게 문제를 빠르게 푸는데 도움이 된다는 것.
관찰할 부분을 잘못 잡으면 큰일난다.
내가 구하고 싶은 결과값을 기준으로 역산해나가면 유의미한 관찰을 하기 쉽다.
1일 3BOJ
어디선가 낚아온 문제들. 아직 안 풀었다.
17236번: Heights
각 줄에 실존하는 삼각형의 높이 값 ha, hb, hc가 각각 주어진다. ha, hb, hc는 실수이며, 0.01 ≤ ha, hb, hc ≤ 100.00이다.
www.acmicpc.net
삼각형의 넓이를 기준으로 이분탐색한다는 생각만 하면 쉬워진다. sinA를 기준으로 이분탐색한 내 코드는 왜 틀린거지..?
헤론 공식 이용해서 이분탐색 해서 풀었다.
S를 이용해 a,b,c를 구하고 real S를 구한다.
S가 realS보다 커지면 S를 줄이고
S가 realS보다 작아지면 S를 증가시키는 방향으로 이분탐색한다.
그런데 생각해보니 그냥 공식이 유도되네?
1405번: 미친 로봇
첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자
www.acmicpc.net
처음에 4^n ~ 2^28 = 2억이여서 쫄았는데
단순 경로고 n이 매우 작으므로 믿음의 dfs를 돌렸다.
맞았다.
20543번: 폭탄 던지는 태영이
시험을 망친 태영이가 인하대학교에 폭탄을 던진다! 인하대학교는 N×N 크기의 정사각형 모양의 땅이다. 인하대학교의 모든 땅은 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)
www.acmicpc.net
누적합 + 그리디
둘 중 하나라도 못 떠올리면 못 푼다 ㅋㅋㅋ
fastio 써서 1등 먹었으~
'PS > Problem Solving' 카테고리의 다른 글
| 2021년 1월 16일 PS 일지 (3) | 2021.01.16 |
|---|---|
| How to win Gold Medal in IOI (0) | 2021.01.15 |
| 2021년 1월 14일 PS 일지 (0) | 2021.01.14 |
| 2O21년 1월 13일 PS 일지 (1) | 2021.01.14 |
| 2021년 1월 12일 PS 일지 (0) | 2021.01.12 |