leo020630의 블로그

이번 주말은 유독 칠 대회가 많았다. 총 앳코더 2개, 코포 2개, 구글 코드잼 1A 라운드가 있었는데, 코드잼은 자느라 못쳤고, 앳코더는 (실력적으로) 못 쳤기 때문에 특별히 잘 친 2개의 코드포스 라운드를 정리해보도록 하겠다. Codeforces Round #781 (Div. 2) A. GCD vs LCM (0:00, +) 보자마자 답이 보여서 짜서 냈다. 덕분에 코포하면서 처음으로 500점을 먹을 수 있었다. ㅎㅎ B. Array Cloning Technique (0:05, +) 가장 많이 등장하는 수의 개수를 센 후, 적당히 2배씩 하면서 횟수를 구해주면 된다. C. Tree Infection (0:33, +3) 킹받는 그리디 문제이다. 우선 노드를 Sibling 단위로 묶으면 트리와 관계 없는 ..

앳코더는 레이팅이 잘 오르는 것 같다. 아직 낮아서 그런가? A. Four Prints (0:01, +) *28 직사각형의 세 꼭짓점이 주어졌을 때 남은 하나의 점을 구하면 된다. 적당히 if문을 써주면 구현할 수 있다. A번치고 오래 걸렸다. B. Get Closer (0:03, +) *79 구하라는 것을 계산하면 된다. 문제에서 제한을 상당히 편하게 주어 대충 짜도 된다. C. Coupon (0:07, +) *336 \(A_{i}/X\)의 합과 \(K\)를 잘 비교해 처리해주면 된다. D. 2-variable Function (0:30, +3) *1148 \(A\)를 고정한 후 \(B\)는 이분 탐색으로 찾아주면 된다. 최대 \(10^6\)까지 돌리면 되니 오버플로우는 고려할 필요가 없으며, 예외처리..

분명히 작년에 ICPC를 같이 나갔지만 놀랍게도 처음인 팀 연습이다. slah007, qjatn0120 선배와 함께 진행하였다. 셋은 BAPC 2018 예선을 사용하였다. ~00:00 동아리 부원들의 실력 증진 차원에서 팀 연습을 함께 진행하였는데, 여러가지 issue로 인해 예정보다 10분 늦게 시작하였다. 내가 A~D, qjatn0120 선배가 E~G, slah007 선배가 F~K를 잡기로 했다. 00:10 A가 좀 화나게 생기긴 했지만 문제 자체는 간단하다는 것을 깨닫고 바로 짜 AC를 받았다. 5분 후에 H 역시 AC가 나왔다. 00:26 영어 지문을 읽는 데에 조금의 애로사항이 있었지만, 다 읽고 나니 B도 쉬웠다. 쉽게 짜서 AC를 받았고, 거의 동시에 E도 AC가 나왔다. 00:39 J AC..

앞으로 어떤 방식으로던 하루에 문제를 많이 푼 날에는 이렇게 정리글을 작성하려 한다. 사실 그냥 여러개의 CP 글을 따로 쓰기 귀찮아서 하나에 합치는 것 같기도 하다. 오늘은 백준 나코더 입부테스트 Open이랑 ABC를 쳤다. 2022 IamCoder Qualification Test Open A. 카드 색칠 (00:20, 3 try) 적당한 난이도의 Constructive 문제다. 연속된 0의 구간을 잘 칠해주면 되는데, 난 잘 생각이 안나서 좀 더럽게 풀었다. B. 개표 (00:31, 2 try) 조건은 간단한 수식으로 나타낼 수 있다. 그 과정에서 나는 각 후보의 득표수를 multiset으로 관리했는데, 어차피 받는 표가 양수기 때문에 그냥 변수 하나로 관리하면 된다고 한다. C. Split the..

이 사이트에 가입한게 8년이 다 되어 가는데, 1000솔을 이제서야 했다. 최근에 동아리 세미나 연습 문제 선정을 비롯해서 문제 풀 일이 좀 있었고, 개강을 하니까 공부하는게 진짜 너무 싫어서 백준을 좀 많이 풀었다. 푼 문제 종류는 주로 단계별로 해결하기 문제들이고, 가끔 랜덤 플레 문제 + 눈여겨보았던 웰노운성 플&다 문제를 위주로 풀었다. 2주동안만 거의 100문제 가까이를 푼 거 같은데, 그러다 보니 문제 수도 꽤 차고, 웰노운성 플&다 문제 중 클래스 8에 포함된 문제가 꽤 있었다. 오늘 오후에 확인해보니 1000솔까지 남은 문제 수와 클래스 8 취득을 위해 남은 문제 수가 4개로 똑같길래 적당히 풀이를 아는 문제 (또는 공부해보고싶었던 문제) 3개를 잡아서 풀고 마지막 1000번째 문제를 뭐로..

대회중 과정과는 상관 없이, 에듀만 치면 결과가 귀신같이 좋다. A. Integer Moves (00:01, +) 주어진 점이 원점이면 0, 원점과의 거리가 정수면 1, 아니면 2이다. B. XY Sequence (00:03, +) 그리디하게 해주면 된다. C. Bracket Sequence Deletion (00:18, +) 괄호 문자열에서 팰린드롬을 생각해본건 처음이라 뇌절이 와 지문을 좀 느리게 읽었다. 만약 앞 두 글자가 ((이나 ))인 경우 팰린드롬이라 지울 수 있고, ()인 경우 올바른 괄호 문자열이라 지울 수 있다. 남은 경우는 )(인데, 이 경우 )(((..(()가 팰린드롬이므로 )가 다시 나올때까지 확인해주면 된다. D. For Gamers. By Gamers. (01:11, +7) 핵심..

코포랑 앳코더가 같이 있었는데, 코포가 테크노컵+앳코더 블루까지 레이팅이 얼마 남지 않았었기 때문에 앳코더를 쳤다. 결과적으로는 괜찮은 선택이었던 것 같다. A. Last Letter (0:00, +) *6 B. Go Straight and Turn Right (0:02, +) *30 생략 C. Yamanote Line Game (0:04, +) *165 앳코더에서는 처음 보는 인터랙티브였다. 하지만 인터랙티브인게 별 의미가 있는 수준은 아니었고, set등을 이용해 구현하면 쉽게 맞을 수 있다. D. Swap Hats (0:08, +) *165 D번 정도면 꽤 귀찮다는 인식이 있었는데, 너무 쉬워서 놀랐다. 두 배열의 inversion parity가 일정해야 하는데, n이 3이니 대충 if문으로 구현해주..

랜덤 플레 디펜스를 하다 풀게 된 문제이다. 오렌지 컵 문제인데, 에디토리얼도 아직 없고 구글링했을 때 풀이가 나오지 않길래 내가 적어보려 한다. 앞으로도 푼 백준 문제들 중에 자료가 없는 것들은 이렇게 풀이를 작성할 예정이다. 문제 요약 오렌지 농장에 \(N\)개의 오렌지를 심을 수 있는 지점이 있다. 오렌지는 심은 후 \(k\)초가 지나면 수확이 가능하다. 모든 지점에 오렌지를 심고 모든 지점에서 오렌지를 수확하기 위한 최소의 시간을 구하여라. 풀이 \(DP[i]\)를 \(i\)번째 오렌지까지 모두 수확하고 i번째 지점에서 멈췄을 때의 최소 시간으로 정의하자. 그러면 다음과 같은 점화식을 통해 \(DP[i]\)를 구할 수 있다: \(DP[i]=min_{0

전날 있던 Div. 2에서 2095->1943이라는 기염을 (또) 토한 터라 멘탈이 좋지는 않았다. Div. 1에서 오른 적이 거의 없던 터라 좀 무섭기도 했고.. 그래도 레이팅이 엄청 낮아져 있었기 때문인지 어떻게 오르긴 한 것 같다. A. Weird Sum (00:38, +) Div. 1에서의 흥망을 가르는 요인은 A라고 생각한다. 그리고 나는 대부분의 Div. 1에서 A만 보면 뇌가 굳는다. 이번 역시 그랬다. 스코어보드는 10분만에 초록색이 쫘르륵 깔리는데 나는 감이 하나도 안 왔다. 30분을 넘게 생각한 후에야 정해도 아닌 \(O(NsqrtN)\) 시간복잡도의 풀이를 찾아서 해결할 수 있었다. 이때만 해도 엄청 망할줄 알았다. B. Integral Array (01:01, +1) 문제를 처음 봤..

방학에는 시간이 남아돌아도 코포 정도만 치고 PS를 그렇게 열심히 하지는 않았는데, 최근에 코포가 없기도 했고 개강을 하니까 갑자기 문제가 풀고 싶어졌다. 마침 solved.ac 다이아 4 + 900솔브를 동시에 달성할 수 있을 것 같아서 최근 3일정도를 투자해 티어를 올렸다. 엄청나게 열심히 푼 것은 아니고, 풀이를 알고 있던 웰노운 다이아 몇 개(1557+8464, 13310, 2803)랑 랜덤으로 돌려서 나온 플레 몇 개를 풀었더니 점수가 쭉쭉 올랐다. 말은 쭉쭉 올랐다고 하지만, 솔브드 티어 올리는거도 참 쉬운게 아닌 것 같다. 여기서 100점을 더 올리려면 다이아5 문제를 기준으로 30개정도를 더 풀어야 할텐데, 솔직히 알고리즘 날먹이 아닌 이상 (다이아는 사실 알고리즘 날먹이어도 좀 어려운거 ..