분류 전체보기
-
문제 풀이공부 2023. 2. 17. 22:47
1. iterator를 이용해서 배열을 순차적으로 한번만 돎, random access X 배열의 길이는 알려지지 않았다. 이 중 n개를 뽑아야 하는데 배열의 길이를 m이라고 한다면 배열 모든 원소를 같은 확률인 n/m의 확률로 뽑아야 함. 메모리의 용량은 n개의 원소들을 저장할 수 있는 배열 하나이다. n=1인 경우부터 시작 iterator 순회하면서 1개를 배열에 투입. 2부터 iterator 마지막까지 1/n+1 ... 1/n+k의 확률로 뽑아서 배열에 있는 수와 변경하거나 1-(1/n+1), ... 1-(1/n+k) 의 확률로 뽑히지 않거나 계산한다. 모든 원소의 뽑힐 확률이 1/m = n/m으로 동일하다 n의 일반적인 경우에 대해서 이야기 해보자 마찬가지로 n개의 원소에 대해서 무조건 투입하고,..
-
846, 842 div2 virtual대회/코드포스 2023. 2. 15. 20:16
https://codeforces.com/contest/1780 Dashboard - Codeforces Round #846 (Div. 2) - Codeforces codeforces.com A. 숫자 배열이 주어지고, 이 중 세 개의 원소를 합쳐서 홀수가 될 수 있는지 묻는 문제 홀수 = 홀수가 홀수가 필요하다 따라서 홀수가 1개도 없으면 불가능 짝수가 하나만 존재해서 - 홀,홀,짝 불가능 이 두가지 경우만 체크하면 된다. 원소까지 출력해야 하므로 홀/짝을 나누어서 받으면 가능하다. B. [l1, + ... + r1], [l2 + , .... , + r2], .. 나누는 방법은 2개 이상 대충 이렇게 subsegment들의 gcd를 최대로 만드는 경우 gcd(a1, a2, a3, ... ) k, y -..
-
852 div2 virtual대회/코드포스 2023. 2. 13. 20:01
Codeforces Round #852 (Div. 2) Dashboard - Codeforces Round #852 (Div. 2) - Codeforces codeforces.com A. 어떤 빵집에서 첫째날에 구매하면 빵 하나에 a 금액, 둘째날에 구입하면 b 금액에 구매할 수 있다. 빵 n개를 구매하는데 드는 최소 금액 여기에 첫째날에 빵 구매하면 m개 구매할 때 1개를 보너스로 더 줌 m+1개의 빵을 구매하는 금액인 a*m vs b*(m+1) 을 비교함 왜냐 우선 a, b의 대소는 한눈에 알 수 있는데 m+1개의 빵을 구매할 때 첫째날이 더 합리적인지 둘째날이 더 합리적인지 알고 싶어서 -> a,b의 대소 말고 변화를 주는 요인이 행사이기 때문에 자연스럽게 비교함 a*m < b*(m+1) 이라면 n..
-
12/13일상 2022. 12. 13. 23:09
사람이란 무엇일까 우리는 기억들의 합의로 형성된다. A는 여러 사람들의 기억에 의해 형성된다. A는 A의 육체가 아닌 A의 본질이기 때문이다. 물론 추상적 의미에서의 본질이다. A가 착하다는 것은 A를 착하게 바라보는 사람들이 많다는 소리이지, A의 절대적 본질이 착하다는 것이 아니다. 그렇기 때문에 어떤 그룹에서는 A가 착한 사람, 어떤 그룹에서는 A가 나쁜 사람으로 동시에 될 수 있다. A에 대한 평가를 바꿀 수는 있다. A가 새로운 행동을 하거나 과거에 한 행동에 대한 정보가 타인에게 전달이 되어서 사람들이 합의를 이룬다면 A에 대한 평가가 바뀌는 것이다. 하지만 누군가가 사람들의 기억을 임의로 조작하는 일은 거의 불가능하다. 일일이 사람들에게 인셉션 혹은 맨인블랙 같은 일을 해야하기 때문이다. 모..
-
edu 130, 804, 803 virtual대회/코드포스 2022. 7. 8. 16:20
edu 130 https://codeforces.com/contest/1697 Dashboard - Educational Codeforces Round 130 (Rated for Div. 2) - Codeforces codeforces.com A 쉬면 에너지 회복 아니면 에너지 소비해서 이동, 현재 에너지 m 따라서 1에서 n으로 이동할 때 필요 에너지 m이하면 0만큼 휴식 아니라면 모든 필요 에너지-m 만큼 휴식 필요 B x 개 산다면 y개가 공짜 공짜 금액 최대로 가장 비싼 것들로만 산다. C 주어진 string s1에서 ab 는 ba로 바꿀 수 있고, bc 는 cb로 바꿀 수 있다. s1을 s2로 바꿀 수 있는지에 대한 문제 a,b,c의 관계에 대한 operation이 주어져 있는데 두 개의 ope..
-
#800 div2 6/30 virtual대회/코드포스 2022. 7. 1. 00:11
https://codeforces.com/contest/1694 A만 풀고 나머지 업솔빙 왜 그런지 엄청 어려웠는데 업솔빙할때는 바로바로 생각남 A 1은 +1 0은 -1 모든 prefix sum의 합의 절대값이 최소가 되도록 -> 번갈아가면서 나오도록 한다. B 10 은 0이되고 01은 1이된다. string이 주어지고 sub string의 길이를 1로 만드는 모든 경우의 수 operation을 왼쪽꺼 삭제로 생각해보자 *****01 꼴이면 무조건 1의 index만큼 가능 ******10 꼴이면 무조건 0의 index만큼 가능 왜냐면 ******0은 *****10 또는 *****00 인데 001은 01로 101도 01로 가능 C 오른쪽으로 가면 +1 왼쪽으로 가면 -1 각 값이 의미하는 내용은 = 오른쪽..