penguin

이번 라운드도 모든 사람을 참가 대상으로 하는 대회였다. 여느 때와 같이 A를 빠르게 풀고, B를 빠르게 풀어야 했지만 문제 이해를 잘못해서 4번을 틀리고 40분이 지나서야 맞았다. 복구해야 한다는 생각으로 C와 D를 봤는데, 아무리 봐도 모르겠어서 E를 읽었다.  E는 팰린드롬에 관련된 문제였는데 케이스워크를 열심히 하고 나니 무조건 TLE가 나는 O(N ^ 2)풀이가 떠올랐다. 그런데 그 풀이가 O(N ^ 2)인 이유가 팰린드롬을 확인하는 과정이 한번에 O(N)시간이 걸리기 때문이었고, Manacher's를 사용하면 O(N)으로 최적화를 할 수 있길래 열심히 Manacher's를 짜고 맞았다. 그 와중에 continue를 안 써서 출력을 두번 하는 코드를 제출해서 한번 틀리고 맞았다. 나중에 E의 에..

이번 라운드는 모든 참가자를 대상으로 하는 라운드였고, 1024등부터는 TON코인으로 상을 주는 대회였다. 큰 금액이 아니어도 상금이 나오면 좋기 때문에, 열심히 했다. 결과도 퍼플급 퍼포먼스가 나오고 등수도 아슬아슬하게 1024등 안에 들어서 굉장히 만족스러웠다.  A를 빠르게 풀고, B에서 핵심 관찰을 빠르게 해서 잘 풀고, C는 기하인 줄 알았지만 그냥 성질 잘 찾고 개수 세는 문제라서 Easy를 빠르게 풀고, Hard도 priority_queue사용하면 비슷하게 풀려서 3번 틀리고 맞았다. 그리고 나서 거의 1시간 동안 손 댈 수 있는 문제가 없어서 열심히 째려보다가, D가 그냥 최대값을 구하는 문제로 단순화한다면 O(n ^ 2) DP로 풀리는 것을 발견하고 먼저 그 코드를 짜고 변형하기 시작했다..

이번 라운드는 Div1과 Div2 두 라운드가 동시에 열리는 라운드였다. 문제가 굉장히 어려웠던 것 같고, Div2 400등 부터 6000등 까지 A, B, C를 푼 사람이 있을 만큼 A, B, C를 빨리 푸는 것이 중요한 라운드였다. C를 푼 사람과 D를 푼 사람의 차이를 보면 난이도 커브가 너무 가팔랐던 것 같다. B에서 원소들을 분리하는 부분을 잘못 짜서 2번 틀리고, 어찌어찌 40분정도에 C까지 푼 후에 1시간 50분 정도 거의 아무것도 못 한것 같다. A. Destroying Bridgeshttps://codeforces.com/contest/1944/problem/A더보기/*여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라*/#include #include using ..

Think-cell라운드는 레이팅 제한이 없는 Div1+Div2라운드 같은 라운드였다. Div1도 참가 대상이기 때문에 문제가 굉장히 어렵게 느껴졌고, 퍼포먼스는 잘 나왔지만 약간 벽을 느낀 것 같다. 전체적으로 (내가 푼 ABCD는) 관찰이 어렵고 구현이 간단했던 것 같다. 특히 C번은 대회가 끝나기 20분 전에 풀었는데, 생각할 거리가 좀 많았던 것 같다. 후기를 적으려고 문제를 다시 보니 어떻게 풀었는지가 잘 생각이 안났다. 그래서 거의 문제를 다시 풀면서 후기를 적었다. 역시 기록은 제때 하는 것이 최고인 것 같다. 그래도 후기를 적으며 엄밀한 증명을 계속 생각하는 것이 사고력에 많은 도움이 되는 것 같다. A. Maximise The Score https://codeforces.com/conte..

9번째 라운드에서 Div3을 졸업하고, 10번째 라운드로 코포 스타일의 Div2 라운드를 참가했다. 스코어보드만 봐도 무난해 보이지는 않는 결과인데, 아무튼 C, D번이 별로였다고(개인적으로)생각한다. 항상 그래왔듯이 A, B를 빠르게 풀고, C에서 약간의(?)삽질을 하고, D를 열심히 쳐다봐도 답이 안보여서 체념한 상태로 E를 보니까, 대충 냅색 DP로 풀릴 것 같아서 풀고 맞았다. 2300명이 푼 C와 959명이 푼 D는 둘다 놓쳤지만, 감사하게도 E에 DP가 있어서 아무튼 레이팅은 올랐다. 확실히 내가 DP에만 강하고 다른 분야들(특히 수학)에는 부족함을 느껴서 다른 분야도 열심히 공부해보려고 한다. A. Rectangle Cutting https://codeforces.com/contest/192..

여러가지 우여곡절이 있었지만 어쨌든 F까지 풀어서 높은 등수를 받고, 레이팅도 100점 넘게 올라서 블루를 달성하게 되었다. F번을 푼 사람이 290명인것을 생각하면 패널티로는 거의 맨 밑이었고, 스코어보드(C)만 봐도 벌써 두달이 지난 대회의 추억(?)이 떠오른다. 대회시작 6분에 A를 풀고, B를 제출했는데 test1 에서 WA가 나와서 살짝 말렸음을 직감했다. 그래도 패널티가 누적되지는 않았으니 일단 빠르게 넘기고 C를 풀어서 test8 에서 WA를 받고 시원하게 패널티를 적립했다. 다시 B를 보니 문제를 잘못 이해했음을 발견하고, 고쳐서 AC를 받았다. 다시 C를 열심히 고쳐서 WA를 받고, D와 E를 약 20분동안 풀어서 맞췄다. 그리고 다시 C로 돌아와서 WA를 한번 더 받고, 그제야 배열 크..

이번 라운드에는 D에 doubly linked list가 출제되었는데, 물론 나도 못 풀었고, E는 1700명이 풀었지만 D는 1300명밖에 못 푸는 기현상이 벌어졌다. 에디토리얼을 보니 구현도 그렇게 복잡하지 않았던 것 같은데, PS를 하는 사람들은 대부분 머리에서 링크드 리스트를 지우고 있기 때문에 킬러 문제로 나올 수 있는 것 같다. 자주 만날 일은 없겠지만 그래도 연습을 좀 해야겠다는 생각을 했다. 이번에도 교회 기도회가 끝나고 라운드를 시작해서 1시간정도 자체 패널티를 가지고 시작했지만, 그래도 풀 수 있는 문제는 다 푼 것 같다. E가 굉장히 코포스러운 해 구성하기 애드 혹 문제였는데, 종료 6분 전에 아슬아슬하게 AC를 받았다. 코포를 열심히 하다 보니 이런 류의 문제에도 어느정도 적응이 된..

라운드가 끝난지 약 2달 만에 후기를 올린다. 사실 배치 6판이 끝나고, 제목을 정하지 못해서 글을 안 쓰다가, 이러다 평생 글을 못 쓸까봐 그냥 대회 이름을 제목에 쓰고 후기를 적기 시작했다. 교회에서 기도회가 있어서 1시간 정도 자체 패널티를 가지고 시작했는데, 그래도 무난하게 한 것 같다. F는 제곱근 분할법 까지 떠올리고 세그멘트 트리로 해야하는 줄 알고 넘겼는데, 누적합으로 풀리는 문제였다. 고급 알고리즘들을 공부할수록 쉬운 알고리즘을 두고 어려운 알고리즘으로 짜는 경우가 생기는 것 같다. 조금 더 생각하면서 이런 경우를 줄이는 연습이 필요하다. A. Square https://codeforces.com/contest/1921/problem/A 더보기 /* 여호와를 경외하는 것이 지혜의 근본이요..

배치 마지막 판은 Div2 라운드였다. 기본 점수 50점을 주기 때문에 이번에 무난하게 하면 블루를 달성할 것이라 생각했지만, 역시 모든 일이 생각처럼 풀리지는 않는 것 같다. A는 A치고 어려웠던 것 같고, 그래도 단순 구현 문제라서 하라는대로 구현하고 AC를 받았다. B는 전형적인 정렬 후 그리디와 스위핑이었고, 생각하면서 구현하고 한번에 맞췄다. C에서부터 문제가 생겼다. 배열을 나눌 수 있는 크기가 적기 때문에, 모든 나누는 경우에 대해서 검증을 하면 된다는 것 까지는 알았다. 그리고 조건을 만족하는지 확인하는 부분을, 에테체로 모든 소수를 구해놓고 확인해봤다. 숫자가 작아서 될 줄 알았지만, TLE를 받고, 몇번 커팅을 시도하다가 계속 TLE만 받고 넘어갔다. D는 2번연산을 많아야 60번 할 ..

이번에는 Hello 2024로, 모든 사람을 대상으로 Rated였다. 대회 시간이 2시간 30분이었는데, 무려 2시간 21분동안 한 문제도 못풀었고, 제출도 한번도 못해봤다. 여느 때처럼 A, B를 10분동안 밀고, C를 봤는데 풀이가 안 떠올라서 일단 E로 넘어갔다. E는 경우의 수 문제였고, 대충 n^2스위핑으로 풀릴 것 같아서 풀다가, 생각해야 할 경우가 좀 많아서 결국 구현을 못하고 대회가 끝났다. 아무리 점수가 높아도 쉬운 문제를 거르고 어려운 문제를 푸는 것은 아직 욕심인 것 같고, 다음 대회때는 반드시 쉬운 문제들은 풀고 넘어가야 할 것 같다. 깔끔하게 A, B만 풀고 대회를 종료하니 한 8000등 정도를 했는데, 레이팅은 딱 1점 떨어졌지만, 원래 5번째 판에는 100점을 주므로 실질적으로..