jwvg0425 Problem Solving

A에서 좀 헤맨게 아쉽지만 그래도 B,C는 깔끔하게 푼 것 같다. D는 풀이를 생각했음에도 불구하고 시간복잡도가 안 된다고 생각해서 시도를 안했다.. 이게 너무 아쉽다. O(N^5)가 안 된다고 생각해서 O(N^4)로 어떻게 줄여야할지를 한참 고민했는데, 생각해보면 O(N^5)는 맞는데 쌩 N^5가 아니라 상수가 많이 줄어서 충분히 할만하다. 이걸 마지막에 시도라도 해봤어야 했는데 시도를 왜 안 했을까.. 정확하게 / 타이트하게 판단하지 않고 적당한 경험에 의거해서 대충 판단하는 것도 나쁜 습관인 것 같다. 2100 초반에서 수렴하는 중.. 정말 바닥을 치고 있다... D를 풀었으면 꽤 올랐을만한 상황이었는데 시도를 안한게 너무 아쉽다. 끝나고 짜서 제출해보니 바로 맞던데 흑흑 A. MP3 서로 다른 수..

이제는 뭐 기대를 하면 안 될 것 같애.. 조만간 퍼플로 내려가겠다. A1. Add on a Tree 문제를 잘 정리해보면, degree = 2 인 노드가 하나라도 있으면 불가능하다. degree 2인 트리에서 양쪽 리프를 하나씩 잡으면 해당 두 엣지에 항상 같은 값이 추가되는데, 이 때문에 이 양쪽 엣지에 다른 값이 들어가있는 경우 생성이 불가능. A2. Add on a Tree: Revolution B가 수식을 잘 조정해서 푸는 문제였는데 못 풀겠어서 A2만 한참을 붙잡았다. 근데 못 풀었다.. 문제에서 주어진 조건을 좀 더 잘 활용해서 유연하게 생각했어야 했는데 그걸 못 했다. 왜 이렇게 생각이 빨리빨리 안 돌아가는지.. 모든 값이 짝수 / 서로 다르다는 점을 생각해보자. 모든 엣지에 들어가있는 값..

끝을 모르고 내려가는 중이다. 문제가 내가 많이 약한 부분에서 나왔다고 위안이라도 하고 싶지만.. 애초에 이 난이도 범위에서 약한 파트가 있다는 것 자체가 아쉽다. 뭐가 나와도 빠르고 정확하게 잘 풀어야지. A에서 코딩 실수한 건 반성해야 할 부분일 듯. B도 냄새는 맡았는데 빠르게 접근을 떠올리지 못한게 아쉽다. C는 못 풀었을 것 같은데, 이 비슷한 발상에서 내가 좀 약한 것 같다. A. Increasing by Modulo 답이 최대 M이라는 사실은 비교적 쉽게 도출할 수 있다. M번 돌면 모듈러한 모든 값을 다 만들어줄 수 있고, 더해줄 때 한 번에 여러 인덱스를 묶어서 더해줄 수 있으니 M번보다 많이 더해줄 이유가 없다. 따라서, 0 ~ M 사이에서 parametric search를 이용해 답이..

오늘은 그래도 나쁘지 않았다. 일단 두 문제 다 한 번에 맞았다는 게 다행. 업솔빙 무조건 하나는 하고 넘어가고 싶었는데, C번은 에디토리얼을 봐도 뭔 소린지 이해도 안 되고, 증명이 제일 중요한 파트인데 이거 대충 읽고 구현한다고 해서 뭐 실력에 도움이 될 것 같지도 않아서 패스. A. Grid game 지워지는 규칙이 단순해서, 그냥 1번 줄에는 1x2, 3번줄에는 2x1을 순서대로 배치하는 걸 반복하면 된다. 한 줄 지워지면 다시 맨 처음으로 돌아가서 배치하는 식. 이렇게 하면 어차피 양쪽 배치의 동작이 독립적이고 무조건 첫줄은 4개 채울 때마다 삭제, 세번째줄은 2개 채울 때마다 삭제 반복이기 때문에 간단하게 풀린다. B. Game with modulo 좀 더 풀이를 빨리 생각할 법도 했는데, 자..

오늘도 대차게 망했다. B는 내가 잘 아는 유형이고 비슷한 문제도 몇 번 풀어봤는데, 풀이를 빠르게 못 떠올린 것 / 자잘한 구현 실수 여러 번 한 것 / 엄밀하게 풀이를 검증하지 못한 것 세 가지의 실수를 저질렀다. 근데 이 세 가지 실수가 버추어 세 번 치는 동안 세 번 내내 다 나왔다.. 미칠 노릇. A는 그럭저럭 잘 푼 것 같은데 B에서 삽질한게 너무 뼈아프다. A. The Beatles 그냥 모든 경우의 수를 다 해주면 된다. 시작점이 a 혹은 k - a 둘 중 하나라고 고정하고 보면, 한 번 이동한 다음에 있을 수 있는 위치는 모든 x * k 에 대해 x * k - b 위치거나 x * k + b 위치거나 둘 중 하나다. 이 각각의 위치에 대해 다시 시작점에서 시계 방향으로 돌거나 반 시계 방향..

unrated된 대회라 등수가 애매하다. 실제 대회였다면 A도 C도 훨씬 많이, 빨리 풀렸을 듯. 이번에도 코딩 미스가 너무 많았다. 풀이도 충분히 빨리 떠올릴 수 있는 문제들을 제대로 못 떠올리고, 모호한 상태에서 구현에 들어가면서 더 많은 실수를 한 것 같다. A. Diana and Liana 간단한 투 포인터로 해결할 수 있는 문제다. 어떤 l 위치에서 l...r이 문제에서 주어진 schematic 조건을 만족하기 위해 제거해야하는 원소 개수를 구하고, 그 중 최소가 되는 것을 출력하면 된다. 간단한 off-by-one 에러, 수식에서의 예외 케이스 처리 등을 제대로 못해서 두 번이나 틀리고 맞았고, 26분이나 걸렸다. 10분 내외로 풀었어야할 문제 같은데 너무 구현 정확도가 떨어졌다는 기분이 든다..

최대한 1일 1 virtual을 도는 걸 목표로 하고 있다. 얼마나 할 수 있을진 모르겠지만.. 대회를 계속 안 쳤더니 너무 감이 떨어져서 최대한 감을 끌어올리기 위해 열심히 하는중. 거하게 조졌다. A도 실제 대회였더라면 systest failed. 어처구니 없는 코딩 실수도 실수고 충분히 풀만한 문제의 풀이도 빠르게 / 정확하게 생각하지 못하게 된 것 같다. 시간 제한이 걸린 상황에서 빡세게 고민해서 푸는 훈련을 좀 많이 해야 할 필요가 있을 것 같다. A. Elections K표 초과를 받는게 목표일 때 그걸 달성하기 위한 최소 비용을 모든 K에 대해 구해주는 것으로도 쉽게 해결할 수 있다. 시간 복잡도는 O(N^2logN). 어처구니 없게도 반복문에서 n을 써야하는데 m을 써서 틀렸고(systes..

https://codeforces.com/gym/102501 셋 다 코드포스 오렌지 + 대충 은퇴한 늙은이들 팀(xtalclr, acka1357, nong)으로 ICPC를 온라인 미러로라도 나가보자라는 생각으로 팀을 짰다. 원래 3주 정도 전에 돌려고 한 셋이었으나.. 이런 저런 사정이 겹쳐서 오늘 진행. 아래는 타임 라인에 따른 진행. 내가 앞에서부터 읽고, xtalxlr님이 뒤에서부터 읽고, acka님이 가운데부터 읽었다. 00:02 I AC xtalxlr님이 I 읽고 AC. 00:04 B AC 내가 B 읽고 AC 00:07 C AC 이어서 내가 C 읽고 AC 00:17 F AC xtalxlr님이 F AC. 여기까지는 꽤 무난하게 쉬운 문제를 잘 풀었다. 이 다음에 나는 A,D 정도를 읽어보았고 ac..

이제 플래티넘 이하 난이도 문제는 총 3개가 남았다. 내일 모레쯤 끝날 듯. 다이아는 천천히 풀어야지(천천히 풀기 싫어도 천천히 풀게 되겠지) 18260. Bessie's Snow Cow 내가 비교적 잘 푸는 유형이라 쉽게 풀었다. 이 문제도 일단 오일러 투어 테크닉을 써서 구간으로 펴서 생각한다. 이렇게 펴서 생각하면, 업데이트는 특정 구간에 색깔 c가 없는 위치에 전부 c를 추가하는 연산으로 생각할 수 있다. 쿼리는 그 구간에 존재하는 색 개수의 합을 구하는 형태가 되는데, 여기까지만 놓고 보면 제일 기본적인 형태의 Lazy propagation Segment Tree로 생각할 수 있다. 다만 색깔 c가 없는 위치만 골라서 c를 추가하는 부분이 조금 어려운데, 여기서 각 구간이 하나의 서브 트리를 나..

한 문제 한 문제가 고역이다 11990. Load Balancing (Platinum) 이 문제는 비교적 뻔한 문제여서 풀이는 금방 생각했다. 우선 모든 점을 x좌표를 기준으로 정렬해보자. 임의의 i번째 점과 i + 1번째 점 사이에 선을 그으면, 1 ~ i번째 점과 i +1 ~ n번째 점은 서로 다른 평면으로 분할이 된다. 이제 여기서 좌우로 선을 어떻게 긋는 경우가 최적인지를 찾아야 하는데, 이 때는 x좌표는 고려할 필요가 없다(x좌표는 이미 평면 분할된 걸 고려했으니). 그래서 y 좌표만 있는 일차원 배열 두 개에서 최적인 경우를 찾는게 되는데, 이 최적 그래프는 unimodal한 형태를 띈다(양쪽 평면 각각을 나눠서 생각했을 때 unimodal한 건 쉽게 생각할 수 있는데, 이 둘에서 다시 최대를..