상위 99.99%의 PS

https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 간선의 개수를 최소로 해서 모든 정점을 잇는 그래프는 트리이고, 이때 간선의 개수는 N - 1 개이다. 간선의 정보는 사용할 필요가 없다. 템플릿 코드 더보기 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..

https://www.acmicpc.net/problem/13925 13925번: 수열과 쿼리 13 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 x y v: Ai = (Ai + v) % MOD를 수행한다. (x ≤ i ≤ y) 2 x y v: Ai = (Ai × v) % MOD를 수행한다. (x ≤ i ≤ y www.acmicpc.net Lazy Propagation in Segment Tree 1번 쿼리는 (ax + b) * 1 + v = ax + b + v 2번 쿼리는 (ax + b) * v + 0= (v * a)x + v * b 3번 쿼리는 (ax + b) * 0 + v = v 꼴로 갱신할 수 있다. 곱하는 값, 더하는 값에 대해..

https://www.acmicpc.net/problem/10999 10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net Lazy Propagation 기초 문제이다. 모른다면 읽고 오자. https://m.blog.naver.com/PostView.nhn?isHttpsRedirect=true&blogId=kks227&logNo=220824350353 기존 세그먼트 트리의 방식으로라면 갱신 하나에 O(NlgN)이라는 시간이 걸려 총 O(MNlgN)이라..

불안해서 풀이/코드는 나중에 올린다. 망했다.

파이썬이 정말 안 좋은 언어라는 것을 다시 한 번 깨닫게 해줬던 대회였다. 1301.6점이라는 뭔가 애매한? 점수를 받았다. 할 수 있는건 다 한듯하다. 작년에는 2000점 만점에 무려 400점(!)을 기록하였지만, 그래도 발전해서 기분이 좋음 1 2 3 4 5 6 7 8 def ip(): return int(input()) def sp(): return str(input().rstrip()) def mip(): return map(int, input().split()) def msp(): return map(str, input().split().rstrip()) def lmip(): return list(map(int, input().split())) def lmsp(): return list(map(..

https://codeforces.com/contest/1559 Dashboard - Codeforces Round #738 (Div. 2) - Codeforces codeforces.com 에이펙스하느라 5분 지각했다. A (00:10) 모든 수에 AND 연산을 하면 된다. B (00:26) 그냥 구현하면 된다. B??R -> BRBR, B??B -> (두 알파벳이 번갈아 나오기만 하면 됨) C (00:40) 1 -> 2 -> ... -> n이 있을때, 이 사이 어디에 (-> n + 1 ->)를 끼워넣을 수 있으면 된다. 먼저, 처음과 마지막을 확인했고, 끼워넣는 경우를 확인했다. D1 (00:52) 두 포레스트에 대해 Union-Find를 하면 쉽게 풀린다. 나머지 두문제는 못풀었다. 퍼플 갈수 있나..

https://www.acmicpc.net/problem/18937 18937번: 왕들의 외나무다리 돌게임 길이 6짜리의 외나무다리에 흰 돌이 3번 칸에 있고, 검은 돌이 5번 칸에 있으면, 흰 돌은 1, 2, 4번 칸 중 하나로 이동할 수 있으며, 검은 돌은 4, 6번 칸 중 하나로 이동할 수 있다. 돌을 상대 돌로 www.acmicpc.net 외나무다리의 길이가 n이면, 그런디 수는 n - 2이다. 여기서 뒤로 가는 것은 승패에 영향을 끼치지 않으므로, 그냥 xor해주면 끝이다. 코드 bo 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 def ip(): return int(input()) def sp(): return str(input().rstrip()) def m..

https://www.acmicpc.net/problem/11871 11871번: 님 게임 홀짝 koosaga와 cubelover가 님 게임 홀짝 버젼을 하고 있다. 님 게임은 돌을 차곡 차곡 위로 쌓아올린 돌 더미 k개를 이용한다. 각각의 돌 더미에는 한 개 이상의 돌이 있다. 두 사람은 서로 턴을 번갈아가 www.acmicpc.net 노트에 8정도까지만 써보면 규칙이 보인다. 홀수면 (i + 1) / 2, 짝수면 (i - 2) / 2이다. 모두 xor해서 승자를 찾으면 끝이다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 def ip(): return int(input()) def sp(): return str(input().rstrip()) def mip(): return ..

https://codeforces.com/contest/1554 Dashboard - Codeforces Round #735 (Div. 2) - Codeforces codeforces.com 블루! A (00:09) 길이 3 이상의 연속하는 부분 수열을 보는 것이 길이 2의 부분수열보다 나은 답을 내놓지 않는다. 길이 2의 부분수열 N - 1개만 확인하면 된다. B (01:17) \( i * j - k * (a_{i} | a_{j}) \)에서, i, j가 맨 뒤에 있다고 하면, 곱은 대충 \(N^2\)라고 하고, \( (a_{i} | a_{j}) \)는 최대 2N이다. \(N^2 - 2KN \)을 최대화 하는 것인데, K의 조건이 min(N, 100)이므로 식은 \(N^2 - 200N \)정도로 볼 수 ..

64, 52, 5 긁고 장려뜸 1 반지름에 대한 dp를 생각해보았지만 아무리해도 생각이 안나서 n^2 dp를 짜고 끝냈다. 반지름 r에 대한 dp를 짜면 아무리 봐줘도 r은 최대 500이니까 안터진다. 2 한 정점의 값을 a로 두고 사이클에 주의하며 dfs를 돌리면 끝이다. 사이클이 생길때 홀수, 짝수일때 경우를 나눌 수 있다. 사이클이 홀수이면 a가 확정되므로, 여기서 정수인지 확인하고 모든 정점의 값을 식에 맞추어 쭉 대입하면 된다. 그러고 모든 간선에 대해서 식이 성립하는지 확인하면 끝. 사이클이 짝수이면, 식들에서 a가 사라지기 때문에 a를 확정할 수 없으므로 항등식이 되는지 확인하면 된다. 그렇게 a가 확정이 안되고 끝났으면 |a - k1| + |a - k2| ... 꼴의 식의 합을 최소화하는 ..