학교에서 볼록최적화입문을 수강중이라 선형계획법 문제들을 풀고 있어서 풀이를 적습니다. 풀이 서술이 힘들어 디테일한 부분을 많이 생략하였습니다. https://www.acmicpc.net/problem/13091 13091번: Longest Shortest Path You are given a directed graph and two nodes s and t. The given graph may contain multiple edges between the same node pair but not self loops. Each edge e has its initial length de and the cost ce. You can extend an edge by paying a cost. Formally, ..
과제하기 싫어서 쓰는 중 ㅎㅎ PS를 4개월 넘게 접은 상태이기도 했고 싸국에 잘하는 사람들이 꽤 있어서 원래는 2등만 해도 감지덕지라는 생각이었는데 막상 결과를 보니깐 1등 못한 게 아쉽기는 하다. 그래도 재밌었고 연세대랑 경쟁하니깐 교내대회보다 긴장감도 있고 재미있었다 내년에 또 하면 좋겠다. 이런 대회 열어준 알프스와 모르고리즘 운영진에게 감사의 말을 전한다. 다만 패널티 규정이나 언어별 추가시간 관련 공지가 미흡했던 것은 아쉬웠다. A. 코딩하기 귀찮아서 정규식으로 날먹하려 했으나 4번이나 틀리고 울면서 밀고 다시 짰다. 사실 이 때부터 망했다는 생각과 함께 목표를 5등으로 수정했다. B. 그냥 적당히 풀었다. 퀄리티는 나쁘지 않은 문제인 듯. C. for문 범위 잘못써서 두 번 틀렸다... 좋은..
일단 이번 리저널은 별 기대를 하지 않은 채 참가했다. 그 이유는 1. 리저널 일주일 전에 월파를 조져서 자신감이 똑떨했다 2. 일주일 전에 내가 코로나에 걸려 컨디션이 안 좋았다. 다행히 대회 당일에 격리가 풀렸다. 3. 팀원 한 명이 코로나에 걸려 대회에 2인으로 참가해야했다. 이 때문에 월파진출에 대한 기대는 사실상 접었었다. 그래서 나는 이 대회를 마지막으로 PS를 접을 생각이었기 때문에 그냥 "수상권만 들고 유종의미만 거두자!"라는 생각이었는데 괜찮은 결과를 얻은 것 같다. 3년만의 오프라인 서울리저널이라 재미도 있었다 ㅎㅎ 팀원은 다음과 같다. knon0501: SCPC 2022 4등상, ICPC 2020 7등 Amel: SCPC 2021 4등상, ICPC 2021 13등 팀연습을 여러번 해봤..
2022.09.05:최초작성 2022.09.18:4등상 받았습니다! 전날까지 Suffix array등의 문자열 알고리즘들을 열심히 연습했는데 하나도 나오지 않았다. 온라인 대회에서는 이런 기조가 맞는 것 같다. 1번이 스위핑,2번이 dp였는데 내가 강한 유형의 문제가 나와서 어느정도 이득을 본 것 같다. 전날 9시에 잤는데 11시에 깨버렸다... 아침 8시에 겨우 다시 잠들었다가 11시 반에 일어나고 겨우 세팅을 했는데 컨디션이 굉장히 안 좋았다. 이런 대회에서 멘탈이 터져서 긁을 걸 다 못 긁고 망하는 경우가 꽤 많았어서 이번에는 문제를 모두 읽고 긁을 수 있는 걸 모두 다 긁기로 전략을 세웠다. 00:22 첫 문제부터 수식이 많아서 어질어질했다. 하지만 그다지 어려운 문제는 아니었고 누적합 비슷하게 ..
문제수는 괜찮지만 패널티가 아쉬운 것 같다. 내가 기본기 부족으로 C의 풀이를 구체화하는데 약간 절었었고 E도 그리디 증명을 못해서 코딩을 늦게 시작했다. 그리고 팀원들이 다른 문제를 볼 때 F를 제대로 봤었어야 했는데 지문조차 읽지 않은 점은 반성해야할 것 같다. 그래도 팀원들의 강점이 각자 다르고 시너지가 잘나서 레이팅에 비해 퍼포먼스가 잘나오는 건 고무적인 것 같다. 00:15 남일이가 G를 짜는 도중 태훈이가 A가 쉽다고 하고 키보드를 뺏어서 AC 00:32 H를 푼 팀들이 많아서 내가 풀이를 내긴 했는데 시간복잡도가 너무 크게 나왔었다. 내가 망설이고 있어서 남일이가 괜찮다고 했고 아슬아슬하게 AC. 골1 정도의 난이도라 생각했는데 빠르게 푼 팀들이 많아서 놀랐다. 00:43 남일이가 G에서 몇..
공식대회 기준 9등이고 패널티가 커서 썩 만족스러운 결과는 아니었다. 패널티가 큰 이유로는 서로 겹치는 문제를 보는 시간이 많았던 것과 내가 브론즈 문제인 K를 1시간동안 붙잡은 것, A에서 뇌절파티를 한 점이 큰 것 같다. 다행히 내가 뻘짓을 하는 동안 팀원들이 플래를 잘 밀어줘서 문제수가 밀리지는 않았다. 이 날은 잠은 그래도 4시간은 잤는데 배가 계속 아파서 화장실을 두 번이다 다녀왔다... 실제 대회날엔 스멕타라도 먹어야할 듯... 00:06 슼보에 I솔브가 올라오길래 내가 읽고 풀었다. 00:19 남일이가 그 다음으로 많이 풀린 H를 풀었다 00:52 태훈이가 C를 풀었다. 플3이라 쉽지 않은 문제인 것 같은데 나는 읽어보지도 않았다. 01:05 내가 K에서 고생하다가 늦게 풀었다. 사실 이 문..
#include using namespace std; int n; int a[257][257]; int b[257][257][9][9]; int c[257][257][9][9]; pair aa[256*256+1]; int mix[256*256+1][17]; int miy[256*256+1][17]; int mxx[256*256+1][17]; int mxy[256*256+1][17]; int p[256*256+1]; inline int f(int x,int y,int xx,int yy){ int k=p[xx-x+1]; int t=p[yy-y+1]; int kk=xx-(1
전날 새벽 1시에 노트북이 들어있는 가방을 술집에 두고온 걸 깨닫는 등의 사고가 있어서 잠을 조금밖에 못 잤었는데 ICPC때는 컨디션 조절 정말 잘 해야겠다 ㅠㅠ ~00:21 처음에 내가 쉬운 문제인 H와 J를 풀었고 태훈이가 그 다음으로 쉬운 문제인 L을 밀었다. 이 때 순간적으로 2등이었음... 하지만 그 뒤로 한동안 세 명 모두 말렸는데 나는 I를 지문을 잘못 읽고 잘못된 풀이를 열심히 짜고 틀리고 뇌절을 했다. I를 푼 팀이 거의 없길래 뭔가 함정이 있을 거라고 생각하고 당분간 다른 문제를 보기로 했다. 02:32 태훈이에게 F에 대한 관찰을 전달 받았는데 내가 재작년 KCPC에 출제한 수열 쪼개기의 하위호환이라는 걸 깨닫고 코딩을 했으나 실수를 너무 많이해서 패널티를 60이나 쌓았다... 반성해..