전체 글
-
c++ 에서 +는 매번 string을 복사하는 연산이 아님(python과 다름)아무거나적어~ 2023. 12. 5. 10:34
String concatenation complexity in C++ and Java Consider this piece of code: public String joinWords(String[] words) { String sentence = ""; for(String w : words) { sentence = sentence + w; } return sentence; } On each stackoverflow.com Time complexity of string concatenation in Python I'm analysing the complexity of my code. From what I found online, since strings are immutable in python, a con..
-
Codeforces Round 797 (Div. 3)코드포스 2023. 12. 5. 10:04
Dashboard - Codeforces Round 797 (Div. 3) - Codeforces codeforces.com E $ \left[ \dfrac{b}{a}\right] =\left[ \dfrac{aq+r}{a}\right] =a+\left[ \dfrac{r}{a}\right] $ 으로부터 주어진 정수들을 K로 나눈 나머지만을 생각하여도 좋다. 합이 K를 넘게 쌍을 짓는 방법은 two pointer를 이용하면 된다. F permutation을 이용하여 문자열을 변환하다보면 독립된 사이클을 발견할 수 있다. 한편, 사이클 2개가 있고, 각각의 주기가 a, b라고 하자. 두 사이클은 모두 [a, b]번 이동하면 제자리로 돌아온다. 이는 n개의 사이클에 대해서도 n개의 LCM을 구하는 것으로 일반화..
-
Codeforces Round 640 (Div. 4)코드포스 2023. 11. 30. 16:22
Dashboard - Codeforces Round 640 (Div. 4) - Codeforces codeforces.com B 방법 1 - binary search 방법 2 - 관찰 N = 7이라고 가정하자. (1 2 3 4 5 6 7) (8 9 10 11 12 13 14) (15 16 17 18 19 20 21) ... 자연수 1부터 N개씩 하나의 블럭으로 생각하자. 그러면 하나의 블럭에는 N으로 나누어떨어지지 않는 수가 (N-1)개 존재한다. 따라서 K개의 나누어떨어지지 않는 수를 위해서는 적어도 K/(N-1)개의 블럭이 필요하다. G i) N부터 1까지 홀수들을 나열한다. ii) 4 2를 출력한다 iii) 6부터 N까지 짝수들을 나열한다. N = 10이면 다음과 같다. 9 7 5 3 1 4 2 6..
-
Codeforces Round 898 (Div. 4)코드포스 2023. 11. 27. 17:50
Dashboard - Codeforces Round 898 (Div. 4) - Codeforces codeforces.com B 가장 작은 값에 1을 더하는 것이 결과값(어떤 수에 1을 더하고 모든 수를 곱한 값)을 최대로 만드는데 최적이다 pf) basis step) 1개의 수에 대해서는 자명하다 2개의 수 a ≤ b에 대해, a(b+1) = ab + a ≤ ab + b = (a+1)b 이므로 작은 수에 1을 더하는 것이 최적이다. 2개 이상의 수들에 대해 생각하자. i) 0이 2개 이상이면 어떤 수에 1을 더하든 상관 없이 결과값은 0이다. 따라서 가장 작은 값에 1을 더하는 것이 최적이다. ii) 0이 1개이면 쉽게 생각할 수 있다. iii) 0이 존재하지 않는 n(≥ 2)개의 양의 정수에 대해 a..
-
Codeforces Round 898 (Div. 4)코드포스 2023. 11. 27. 17:47
Dashboard - Codeforces Round 898 (Div. 4) - Codeforces codeforces.com B 가장 작은 값에 1을 더하는 것이 결과값(어떤 수에 1을 더하고 모든 수를 곱한 값)을 최대로 만드는데 최적이다 pf) basis step) 1개의 수에 대해서는 자명하다 2개의 수 a ≤ b에 대해, a(b+1) = ab + a ≤ ab + b = (a+1)b 이므로 작은 수에 1을 더하는 것이 최적이다. 2개 이상의 수들에 대해 생각하자. i) 0이 2개 이상이면 어떤 수에 1을 더하든 상관 없이 결과값은 0이다. 따라서 가장 작은 값에 1을 더하는 것이 최적이다. ii) 0이 1개이면 쉽게 생각할 수 있다. iii) 0이 존재하지 않는 n(≥ 2)개의 양의 정수에 대해 a..
-
Codeforces Round 886 (Div. 4)코드포스 2023. 11. 27. 14:47
Dashboard - Codeforces Round 886 (Div. 4) - Codeforces codeforces.com D An arrangement that always minimizes the absolute difference between adjacent pairs is the array in sorted order. G 평면상의 직선 위에 있는 서로 다른 점의 개수를 세는 방법 H 병사들을 노드로, 병사간의 거리를 directed edge의 weight로 모델링한다. 이때 핵심은 양방향 간선을 모두 포함하여 임의의 노드에서 시작하여도 상관 없게 만드는 것! 그 후 dfs를 이용하여 모든 병사간의 거리를 결정한다. 마지막으로 모든 조건이 충족되는지 확인하면 된다. 6 5 1 2 2 2 3 4..