jwvg0425 Problem Solving

지난 번 팀연습도, 이번 팀연습도 생각보다 훨씬 퍼포먼스가 잘 나왔다. 문제 푸는 것도 매끄럽고 아주 좋다. 재밌다! 초중반에 몇 가지 아쉬웠던 점들이 있지만 뭐 아쉬운 점이 하나도 없는 대회는 있을 수가 없으니.. 아래는 타임라인에 따른 진행. 이번에도 내가 앞에서부터 읽고, xtalxlr님이 뒤에서, acka님이 중간을 읽었다. 00:30 I AC 초반에 상당히 멘붕이었다. 사람들이 푸는 문제들을 이것저것 봤는데 전부 다 어려워보이는데 이게 도대체 왜 풀리지 하는 느낌.. 일단 I, D가 제일 많이 풀려서 그걸 봤는데 둘 다 잘 모르겠었고.. 그 다음에 악어님이 E 풀어볼만할 것 같다고 하셔서 나는 E를 봤다. 그리고 E 대충 풀이가 나왔고, 그 사이에 xtalxlr님이 I번 풀이를 생각해서 AC. ..

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..

오늘은 태수님의 휴가 일정에 맞춰 오후 반차를 쓰고 둘이서 팀연습을 돌았다. 승원님은 아쉽게도 일정상 참여할 수가 없어서 참여하지 못함. 둘이서 도는 거라 그냥 각각 컴퓨터 써서 풀었다. 목표는 9솔브였는데 8솔브로 끝난게 좀 아쉽다. 아래는 타임 라인에 따른 정리 00:06 J WA 태수님이 문제 쭉 읽어보시더니 J가 쉽다고 바로 작성해서 제출. 하지만 WA 00:08, 00:09 J WA 이어서 연달아 뭔가 이상한 실수를 반복했고 ㅋㅋ 여기서 그냥 패널티는 포기하자고 이야기했다. 00:09 J AC 4번째 시도 끝에 AC. 우리가 퍼스트 솔브였다. 00:17 H AC 이어서 태수님이 H도 빠르게 솔브. 00:23 B WA 나는 태수님이 다른 문제 풀 동안 B를 계속 붙잡고 있었다. 제출했지만 WA....

오늘은 NEERC 08을 셋으로 돌았다. 꾸사가님이 2시간 패널티 주고 시작했는데도 패배... A번 실수 오차의 벽을 넘지 못한게 너무 안타까웠다. 당시 대회에서 8솔브가 월파 컷이었다고 해서 꼭 8솔브하고 싶었는데.. 많이 아쉽다. 그래도 실수 오차같은 건 연습 때 겪어봐야 나중에 같은 실수를 안 하니 배운 건 많은 연습이었다고 생각. 실제 대회에서 진짜 저렇게 실수 오차에 털려서 망했으면 얼마나 기분이 참담했을 지 생각해보면.. 그 외에 좀 만족스러운 점은, 저번에 패널티를 너무 많이 먹었던 것과 다르게 이번에는 거의 실수 없이 잘 풀었다는 점이다. 오늘은 풀이 짜고 코딩 들어가기 전에 반드시 팀원과 풀이를 한 번 공유한 후 잘못된 점 체크하기 + 제출 직전에 한 번 더 테스트 케이스 생각해보고 제출..

매주 일요일 오후 1시 ~ 5시까지 4시간동안 12문제를 푸는 연습을 하고 있다. 코드포스에서 난이도 1700,1800,2300,2400 각각 한 문제씩 4개, 1900~2200까지는 각각 두 문제씩 8개 해서 12문제 셋으로. 지금 목표는 4시간동안 10솔브 이상을 꾸준히 하게 되는 실력을 쌓는 것. 업솔빙은 꾸준히 하고 있는데 업솔빙보다도 대회 시간중에 내가 어떻게 풀었고 뭘 개선해야할지를 복기하는게 좋을 것 같아 했던 연습들 진행 과정을 전부 글로 정리해두려고 한다. 1라운드는 문제 선정이 좀 잘못돼어서 10문제 풀긴 했는데 별 의미는 없는 듯. 아래는 타임 라인에 따른 문제 풀이 복기. 00:03 J AC : 문제 길이 짧은 것부터 쭉 읽어보니 J가 너무 말도 안 되게 쉬운 문제였음. 바로 AC...

오늘은 UCPC 팀(민승원 - zxcv551133, 서태수 - cheetose, 남현욱 - hyunuk) 연습을 했다. 꾸사과님이 갑자기 같이 연습하고 싶다고 말씀하셔서, 같은 셋에 3 대 1로 참가하는 형태로 연습 진행. 셋도 꾸사가님이 골라주셨다. 셋 링크 : https://codeforces.com/gym/101967 초반에 엄청 말렸는데, 다행히 결과적으로 9솔브하고 25등이라는 아주 만족스러운 결과로 끝. 팀 호흡이 생각보다 훨씬 괜찮았던 것 같다. 실제 본선에 맞춰서 컴퓨터 한 대로 셋이서 진행했는데, 이런 식으로 해본 적이 한 번도 없었음에도 불구하고 풀 수 있는 수준의 문제는 대충 다 풀어낸 듯. 조금 아쉬운건 패널티가 너무 높다는 거. 한 번에 푼게 딱 한 문제.. 대부분 안 받아도 될 ..

한참 고민하다가 쿠사가님으로부터 힌트를 듣고 풀었다(원본 풀이는 큐브러버님 것이라고 함). 오늘 쉬운 것만 푼 것 같아서 이 문제를 잡았는데 정말 좋은 풀이여서 풀길 잘했다는 생각이 들었다. 문제 링크: https://www.acmicpc.net/problem/1848 문제 요약n개의 정점과 m개의 간선으로 이루어진 그래프가 있다. 각 간선은 a b c d로 표현되는데, 이는 a->b로 갈때는 비용이 c이고 b->a로 갈때는 비용이 a라는 뜻이다. 이 그래프에서, 1번 정점에서 시작해서 다시 1번 정점으로 돌아오는 최단 경로를 구해야 한다.이 때,1. 모든 정점과 간선은 딱 한 번만 지나갈 수 있다(1번 정점 제외)2. 1번 정점 외의 정점을 반드시 하나는 거쳐야 한다. 문제 풀이 1번 정점에서 임의의 ..

문제 링크: https://www.acmicpc.net/problem/8098 문제 요약n개의 구간이 있다. 각 구간은 (p,k)로 구성되며 각 숫자는 1이상 30000이하이다. 서로 다른 두 구간은 겹치게 선택할 수 없을 때, 선택한 구간들의 전체 길이 합의 최댓값을 구하여라(단, 두 구간에 대해 한 구간의 끝점과 다른 구간의 시작점이 같은 경우는 선택할 수 있다). 풀이일단 하나의 구간만 놓고 생각해보자. 특정한 한 구간을 골랐을 때, 이 구간을 맨 끝 구간으로 포함하는 길이 합의 최댓값은 어떻게 구할 수 있을까? 간단하게 생각하면, 현재 구간이 (l,r)일 때 1~l까지의 최댓값 + 현재 구간의 길이가 곧 전체 최댓값이 될 것이다. 이러한 논리를 반복적으로 적용하면, dp(pos) = 1 ~ pos..

문제 링크: https://www.acmicpc.net/problem/8094 문제 요약w와 5이상 w이하의 숫자 n개가 주어진다. 이 숫자들을 몇 개의 그룹으로 묶을 건데, 각 그룹에는 최대 2개의 숫자가 들어갈 수 있고 그 두 수의 합은 w를 넘으면 안 된다. 또, 모든 숫자가 그룹에 포함되어야 한다. 이 때 가능한 한 최소 그룹 개수를 구하여라. 풀이그리디한 접근 방법으로 풀 수 있다. 직관적으로, 제일 작은 숫자부터 숫자 k에 대해서 w-k이하인 숫자들 중에 제일 큰 걸 그 k와 묶어주면 답이 될 것이다 라는 생각을 할 수 있고(그렇게 해야 최대한 해당 한 그룹에 많이 넣을 수 있으니까), 그 생각대로 구현하면 AC를 받을 수 있다. 이런 그리디한 문제는 답 보다도 그 풀이의 정당성에 대한 증명이..

문제 링크: https://www.acmicpc.net/problem/8103 문제 요약n x n 크기의 체스판 위에 n개의 룩을 서로가 서로를 잡을 수 없게 배치할 것이다. 이 때, i번째 룩은 (ai,bi) 에서 (ci,di)위치 사이에만 놓을 수 있다. 모두 배치할 수 있다면 그렇게 배치할 수 있는 경우를 아무 것이나 출력하고, 배치할 수 없다면 NIE를 출력하라. 풀이 록끼리 서로가 서로를 잡을 수 없게 배치하려면, 하나의 룩이 배치된 위치와 같은 행 또는 열에는 다른 룩이 배치되어선 안 된다. 또, 룩은 항상 일직선으로만 위치를 차지하기 때문에 행과 열은 독립적이다. 따라서, 행과 열을 분리해서 보아도 상관없다. 룩이 x좌표에서 어느 위치에 있느냐는 그 룩의 y 좌표에서의 배치에는 전혀 영향을 ..