코드포스 썸네일형 리스트형 [코드포스 Round 677] A. Boring Apartments intercoms : 인터폰 (구내전화) resident : 주민, 거주자 대회 중에 문제 이해 잘 안 됐는데 지금 다시 보니 알겠다. 11, 111 이런게 지루한 아파트 번호이고 얘가 이 번호로 계속 전화를 걸다가 누가 받으면 끊는다는구나. 문제 그대로 구현했다. 1부터 9까지 가는데 각 수마다 1, 11, 111, 1111 찍었다. 그리고 문자열 길이 더해나갔음 #include #include #include #include #include #include #include #include #include #include #include #include #include #define xx first #define yy second #define all(x) (x).begin(), (x).end() us.. 더보기 [코드포스 Round 677] 후기 첫 버츄얼! 이전에 북님이 만든 practice만 계속 풀다가 백준으로 넘어가서 백준 주구장창 풀고 다시 코포로 돌아왔다. 하지만 바로 풀기는 무서워서 버츄얼로 좀 돌다가 블루 찍으면 실전으로 갈 예정. 올해 블루 찍는게 목표여서 12월까지 계속 알고에 미친년처럼 풀 예정.. 일주일에 두 번 푸는게 목표다. 이번 결과는 1410 민트 이렇게 결과나오니 너무 재밌다ㅋㅋㅋ 의욕 불탐 활활.. 블루 조진다.. Standings ~ 00:13 A 솔브 역시나 영어.. 읽는데 시간 너무 오래 걸린다. 단순히 같은 수 구하는 문제라 문자열 더해가면서 풀었음. ~ 00:30 B 솔브 제일 처음 1이 나타나는 시점과 끝에 나타나는 시점 사이 0의 개수를 세면 되는 문제. 이것도 바로 아이디어 떠올랐다. ~ 00:45 .. 더보기 D. AND, OR and square sum https://codeforces.com/contest/1368/problem/D Problem - D - Codeforces codeforces.com 처음에 어떻게 풀 지 몰라서 힌트 받아서 풀었음ㅋㅋ x|y = x + y - (x&y) 공식을 사용하면 전체의 합이 일정하다는 걸 알 수 있다. 전체 합이 일정할 경우 숫자를 최대한 몰아줘야 제곱의 합이 최대가 된다. 풀이 방법은 먼저 각 자리수 별 비트 개수를 세고 → 비트 최대치를 사용해서 큰 수를 만든다음 → 제곱해서 답에 더해준다. 어제 비트마스크를 사용하는 문제를 풀어서 비트 연산이 어렵지 않았다ㅋㅋ 배운 걸 써먹으니 뿌듯하네 #include #include #include #include #include #include #include #in.. 더보기 [코드포스 Practice22] E. Restaurant 운영체제 스케줄링이 먼저 생각났지만 그리디 문제였다. 그리디는 왜이리 어렵지? 다른 기법들에 비해 많이 안 접해봐서 너무 낯설고 증명도 어렵다. 처음에는 먼저 도착한 순으로 처리를 하되, 시간이 많이 걸리지 않는 것부터 처리하려 했다. 하지만 9-25, 10-11, 12-13 같은 경우에 9-25를 먼저 처리하게 되면 하나 밖에 수행하지 못한다. 이 경우에는 끝나는 시점 순서대로 순서를 세면 해결할 수 있다. #include #include #include #include #include #include #include #include #include #include #define xx first #define yy second #define MAX 1e9 #define all(x) (x).begin().. 더보기 [코드포스 Practice22] D. Uniqueness 문제 이해는 했는데 어떻게 풀지 몰라서 못 푼 문제였다. 나름 구간이 있어서 투포인터랑 부분합이 떠올랐고 또 구간의 최소 길이를 구하는 문제니깐 파라매트릭 서치도 생각 났는데 전부 활용하기 어려웠다. 투포인터는 l, r 한 번씩 훑는다고 최소 길이를 찾기 어려웠고 부분합은 여기 쓰는 건 아닌 듯하다. 파라매트릭 서치는 답이 있는 구간이 정확히 두 개의 구간으로 나눠지지 않아서 쓰기 어렵다. 이 문제의 힌트는 n이 작다! n이 2000 이하의 값이라 n^2까지 계산이 가능하다. 또 이걸 구간의 최소를 구하는 건 구간 외의 길이가 최대가 되면 된다. 그래서 구간 밖의 오른쪽과 왼쪽이 중복되지 않는 최대의 길이를 구해보자. 갑자기 손코딩이 해보고 싶었음 메모리 얼마나 쓰는지도 배웠다. 배열 크기에 자료형 크기.. 더보기 [코드포스 Practice22] C. Alice, Bob, Two Teams 구해야 하는 값이 연속적으로 있어서 구간합이나 투포인터가 떠오르긴 했는데 구간합은 시작과 끝을 정하는 부분이 많아서 패스하고 투포인터는 l, r이 움직이는 기준을 잡기 어려워서 포기했다. 시간 촉박한 와중에 투포인터 ppt도 봤는데 거기서도 투포인터는 주로 구간의 길이를 구한다고 했고 최댓값을 구하는 데 적합하지 않아서 패스했음. 이 문제도 내가 잘못 이해했다. 여기서 prefix랑 suffix란 용어가 나왔는데 이걸 찾아보니 접두사 접미사였다. 그래서 구간을 선택하면 그 구간의 처음과 끝을 바꾸는 건가 싶었는데 예시를 보니 아니었다. 도저히 어떤 값인지 알 수 없어서 패스하고 풀기 시작했는데 알고보니 prefix가 문자열의 처음부터 특정 위치까지의 문자열을 뜻하는 것 같았다. suffix는 반대로 특정.. 더보기 [코드포스 Practice22] B. Chat Online 아니 왜!! 안 풀리지!!! 싶었는데 그냥 내가 예시를 잘 못 생각해서 문제였다. a, b가 2-3이고 c, d가 0-1이라 t가 2, 3이어야 한다고 생각했다. 그래서 답이 2인데 왜 3이지 계속 생각하다가 패스.. 이 문제는 가능한 모든 t의 개수를 구해야 해서 복잡했다. 그런데 값이 50이 최대이다? 그래서 그냥 다 구했음. l부터 r까지 범위가 1000이라 1000번 확인하고 구간 50개 * 50개 확인하면 최대 2,500,000번 반복문을 돈다. 1초에 1~2억번까지 루프를 돌 수 있으므로 시간 내에 돌아간다. #include #include #include #include #include #include #include #include #include #include #define xx fir.. 더보기 [코드포스 Practice22] A. Lesha and array splitting 주어진 배열을 sub배열로 나누는데 sub배열의 합이 0이 되면 안 된다. 전체 0인 경우는 NO를 출력하면 된다는 걸 알겠는데 그 다음을 어떻게 해야할지 몰라서 해맸다. 이걸 하나씩 출력하려고 했는데 그럼 중간에 0이 있으면 또 단위를 크게 해서 묶어줘야 하고. 0이 아니게 묶어주는 기준을 못 찾아서 결국 못 풀었다. 이 문제는 일단 전체 합이 0이 아니면 범위를 전체로 해서 구할 수 있다. 다음으로 전체 합이 0인 경우가 문제인데, 이 경우는 두 개의 구간을 사용하면 해결할 수 있다. 임의의 좌표 i를 기준으로 오른쪽의 합이 k라고 하면 왼쪽은 -k일 것이다. (전체의 합이 0이어야 하므로) 그래서 왼쪽에서 합이 0이 아닌 지점을 찾아서 그 지점을 기준으로 왼쪽, 오른쪽을 나누면 된다. #includ.. 더보기 이전 1 2 3 4 5 ··· 16 다음
