뒤늦게 정리해보는 카카오 코드 페스티벌 후기. 솔직히 수상을 전혀 기대하지 않았는데 수상하고 상금 32만원도 받게 돼서 정말 기분이 좋았던 대회였다. 온라인 예선본선 진출자를 겨우 64명 밖에 안 뽑는다고 해서 굉장히 긴장됐었다. 아래는 타임라인별 요약. 무려 6시간동안 진행된 대회라 풀면서 너무 힘들었다. ~ 03:28 Solve AA번은 그냥 너무 간단한 구현이었어서 쉽게 맞췄다.~ 14:47 B WA 1B번도 쉽다고 생각했는데, WA를 받았다. 로직적으론 분명 잘못된 게 없다고 생각했고, 그래서 문제가 될만한 건 실수 오차 밖에 없을 것 같아서 실수 오차를 줄이는 방향으로 이리저리 고민을 했다.~ 19:38 B WA 2~ 27:46 B WA 3몇 번 더 시도를 했음에도 불구하고 계속 WA를 받았고,..
아쉽게도 본선에서는 닉값을 하지 못했다 흑흑 조금만 더 신중하게 잘 했으면 충분히 8솔브할만 했는데 못 해서 더 아쉬운 것 같다. 아래는 타임라인 별 진행 ~00:00 내가 상대적으로 구현 실력이 조금 더 나은 편이지만 5시간동안 나 혼자 코딩을 다 했다간 체력이 버틸 수가 없기 때문에, 초반의 쉬운 문제는 다른 팀원 두 분이 코딩을 맡아주시고 그 동안 나는 비교적 어려워 보이는 문제의 풀이를 고민하기로 했다. 처음부터 팀의 목표는 패널티 상관없이 무조건 8문제를 푸는 것이었고, 그래서 틀리거나 빠르게 못 풀거나 하는 것에 연연하지 않고 최대한 침착하게 풀기로 팀원들과 여러 번 이야기 했다. ~17:45 Solve J (WA 2) 내가 문제들을 쭉 훑어보는 사이, 다른 팀원 분이 2번의 실수 끝에 J를 ..
뭔가 운좋게 문제가 잘 풀려서 팀명대로 8 솔브에 성공하고 17등으로 본선 진출권에 안착했다. 아래는 타임라인 별 진행 ~00:00 시작하기 전에 내가 맨 앞 4문제, 규정님이 중간 3문제, 진일님이 마지막 3문제를 읽어보고 풀기로 정했다. ~01:43 Solve A A번 읽고 보니 굉장히 쉬운 문제라 그냥 바로 코딩에 들어가서 AC. ~06:59 Solve B 그다음 B번을 읽었는데, 그리디하게 풀면 풀릴 것 같아보이긴 했지만 증명이 감이 안 잡혀서 넘겼다. 그 다음 C,D 둘 다 읽어봤는데 이 두 문제도 별로 만만치 않아보였고, 이 시점에서 스코어보드를 보니 B를 많이 풀었길래 그러면 그리디가 맞겠지 생각하고 에라 모르겠다 짜서 제출 후 AC. 하지만 여전히 왜 그리디가 동작하는지 증명하지 못했고 증..
링크 : http://codeforces.com/contest/961 아직 시스템 테스트가 남긴 했지만 적당히 5문제 잘 풀었다. E번에서 코드 짜다가 갑자기 생각이 이상해져서 패널티를 많이 먹은게 아쉽다. 처음부터 좀 더 정확하게 생각했으면 패널티를 4~50은 덜 받았을텐데.. 그게 좀 아쉽. D번도 그렇고 E번도 그렇고 코드 짜다가 꼬이는 걸 어떻게 좀 해야할텐데 싶다. A. Tetris 그냥 나온 숫자들 중에 제일 횟수 적은 거 출력해주면 된다. B. Lecture Sleep t 값이 1인 건 다 답에 포함시켜놓고, 맨 앞부터 k개 구간을 유지하면서 그 k개 안쪽에 있는 0인 애들을 다 1로 바꿨을 때의 값을 순서대로 구해서 그 중 최댓값을 출력해주면 된다. C. Chessboard 완전 구현 문제..
문제 링크 : https://oj.uz/problem/view/JOI13_collecting 순서대로 10점 -> 30점 -> 100점 풀이를 최적화하는 과정을 통해 떠올렸다. 점수 배치도, 접근 과정도 굉장히 재미있는 문제였다. 일단 가장 단순하게 떠올릴 수 있는 해법부터 고려해보자. 사진의 어떤 일부분에 대해서, 그 사진을 4등분해야하는지 아닌지 조건을 우선 파악해야한다. 이건 비교적 간단한데, 해당 사진의 크기가 n*n이라고 했을 때, 위아래 선분이 0개 또는 n개 이면서 좌우 선분이 0개 또는 n개이면 해당 사진은 자르지 않아도 된다. 모든 선분이 다 0개 -> 전체 흰색, 둘 중 하나가 n개 -> 전체 검은색, 둘 다 n개 -> 전체 흰색이기 때문이다. 그러면 이제 여기서 4등분을 해야하는 경우..
링크 : https://csacademy.com/contest/archive/task/amusement-park/ 문제 요약T개의 티켓을 가지고 1번 놀이공원부터 A번 놀이공원까지 순서대로 사용한다. 이 때, 내가 현재 갖고 있는 티켓 개수 T와 현재 놀이공원의 번호 A에 따라 리더기가 잘못 동작할 확률 P가 테이블로 주어진다. 이 P만큼의 확률로 리더기가 잘못 작동하면 티켓을 사용하지 않고 해당 놀이기구를 탈 수 있다. 남은 티켓이 0개가 될 때까지 반복해서 1번부터 A번까지 놀이기구 사용, A번까지 사용 후 다시 1번 놀이기구로 돌아오는 걸 반복할 때 갖고 있는 티켓 T개로 사용가능한 놀이기구 개수의 기댓값을 구하는게 문제. T와 A는 모두 1000이하의 자연수.풀이 기댓값 DP 문제인데 싸이클을 처..
C,D 두 문제 풀고 105등. E번이 이 방법 저 방법 다 써가며 한참 끙끙댔는데 네트워크 플로우(민컷) 문제였다. 한 번도 풀어본 적이 없어서 ㅠㅠ 결국 못 풀고 끝났다. 빨리 플로우쪽도 지식적으로 부족한 부분 보강해야하는데.. C. HSI8:47 솔브 수식을 유도하는 문제였는데, 무한급수 공식 유도 잘 기억 안나서 그냥 wolfram alpha 써서 공식 찾아서 풀었다. 이런 거 공식 유도하는 연습도 해야하는데 ㅠㅠ 대회에서 맨날 wolfram alpha에 의존하게 되는 듯 D. ABS 23:26 솔브 게임 관련 DP 문제. 요런 쪽 문제는 그래도 몇 번 풀어본 경험이 있어서 실수 없이 빠르게 잘 풀었다.
에듀 코포인데 레이티드라고 해서 부캐로 참가해봤다. 5문제 풀 수 있었을 것 같은데 D번에서 엉뚱하게 실수해서 그거 버그 찾다 결국 찾지도 못하고 3문제 풀고 끝나버렸다 ㅠㅠ 매번 느끼지만 코드를 정확하게 짜고 잘 검증하는 능력이 부족한 것 같다. 예외 케이스를 좀 더 꼼꼼히 생각하고 프로그램의 정당성을 제대로 증명하는 연습을 해야겠다. A. Chess For Three 그냥 문제에서 요구하는 조건에 맞춰서 구현했다. 현재 게임 중인 플레이어 / 관찰중인 플레이어 나눠서 바뀌게 해주고 조건 안 맞으면 틀리게. 4분 8초에 솔브 B. Beautiful Divisors 문제에서 요구하는 divisor 개수가 적어서 그거 그냥 미리 계산해두고 조건 맞춰서 검사해보면 된다. 7분 30초에 솔브 C. Rumor ..
링크 : http://codeforces.com/contest/883/problem/J 풀이는 생각보다 금방 떠올렸는데 구현하면서 실수를 너무 많이 해서 계속 틀렸다. 대회였으면 못 풀었을 것 같다. 생각을 좀더 엄밀하게 정리하고 증명한 다음에 코드를 짜는 습관을 들여야 하는데 매번 그게 잘 안되는 듯. 더 신경써야 할 것 같다. 문제 요약: m개의 철거 예정인 빌딩이 있다. n일동안 철거를 진행할텐데, 빌딩을 철거하는데에는 비용이 든다. pi = i번째 빌딩을 제거하는데 필요한 비용. 그리고 n일동안 날마다 철거를 위한 지원금 ai가 들어온다(ai=i번째 날에 받은 지원금). 여기에 추가적으로 bi라는 변수가 빌딩마다 하나씩 주어지는데, i번째 날에 j번째 빌딩을 제거하기 위해서는 bj