학교에서 볼록최적화입문을 수강중이라 선형계획법 문제들을 풀고 있어서 풀이를 적습니다. 풀이 서술이 힘들어 디테일한 부분을 많이 생략하였습니다. 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등 팀연습을 여러번 해봤..
#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
오늘은 태훈이가 앞쪽, 내가 중간, 남일이가 뒤쪽 문제를 봤다. 내가 3시간도 자지 못해서 컨디션이 많이 안 좋았었다... 대회날에는 컨디션 관리를 잘 해야할 듯 나는 E,F,G,H를 모두 읽었는데 풀 수 있는 문제가 하나도 없어서 당황했다... 그 사이 태훈이가 문제를 하나씩 풀기 시작했다. 00:07 태훈이가 A를 풀었다. 00:23 태훈이가 B를 풀었다 00:37 태훈이가 C를 풀었다. 태훈이가 엄청난 퍼포먼스로 골드급 문제를 빨리 밀어줘서 내가 상대적으로 어려운 문제들을 오래 고민할 수 있었다. 나는 K를 BCC로 풀 수 있겠다고 생각하고 풀이를 정리하고 있었다. 01:08 그 사이 태훈이가 I를 풀어냈다. 대단... 나는 K의 풀이를 코딩하고 나서 시간복잡도가 예상보다 제곱배로 크다는 걸 깨닫고..
00:13 오늘도 내가 앞부분 문제를 읽었다. A랑 B가 뭔가 할만해 보이게 생겼었는데 스코어보드에 C솔브가 올라와서 내가 C를 읽고 풀었다. 급한 마음에 타이핑을 실수해서 한 번 틀렸다... 00:44 그 다음으로 K가 많이 풀리길래 내가 K를 읽고 풀었다. 이 문제는 코딩을 좀 더 빠르게 했었어야 할 것 같다. 01:16 태훈이가 펜윅을 짜고 F를 풀었다. 실수로 한 번 틀린 것 같다. 01:42 내가 E를 읽고 아호코라식+dp 풀이를 만들었는데 구현하기가 막막했다... 일단 팀노트에 있는 아호코라식 코드를 옮기고 열심히 코딩을 했는데 예제가 안 나왔다. 키보드를 넘겨주고 문제를 다시 읽어보니 빼먹은 조건이 있어서 다시 키보드를 뺏고 고쳐서 맞았다. 02:21 남일이가 H에서 고전하길래 내가 문제 설..
약간 아쉬운 성적인 20등으로 마무리했다. 팀연습 때처럼 로봇융합관에 모여서 했는데 도중에 에어컨이 꺼지는 이슈가 있었다. 그것때문에 제 퍼포먼스를 발휘하지 못한 거라고 정신승리를 하기도 했다. 00:01 구현이 빠른 태훈이가 A를 읽기로 했고 퍼솔을 먹었다. 00:17 문제들을 쭉 한 번 훑어보고 내가 가장 쉬워보이는 B를 풀었다. 00:20 태훈이가 아마도 구현문제였던 E를 풀었다. 그 뒤로 약간 정체가 있었는데 나는 D에서 '분수 이분탐색? 설바 stern-brocot 트리인가?' 하며 뇌절을 했다. 실제로 전명우 선배님 블로그를 보며 stern-brocot 트리를 공부하려고 시도했었다. 00:42 남일이가 J의 풀이를 알아내고 맞았다. 01:01 태훈이가 F를 밀어줬다. 01:08 D가 생각보다 ..
00:13 내가 앞부분 문제를 읽고 B를 풀었다. 실수해서 한 번 틀린 건 그럴만 한데 스코어보드를 잘못봐서 B를 늦게 읽은 건 반성해야겠다. 00:21 내가 A를 제출했지만 틀렸다. 다시 생각해보니 풀이에 반례가 존재했다. 00:34 태훈이와 남일이가 상의를 하고 H를 풀었다. 00:55 내가 A에 꽂혀있는 사이 태훈이가 D를 읽고 풀었다. 내가 조금 더 일찍 읽었어야 했던 거 같다. 01:26 G는 실수+기하라 풀기 싫었지만 그다지 어렵진 않은 것 같아서 내가 풀었다. 이분탐색 구현을 실수해서 한 번 틀렸다. 01:41 남일이가 I를 짜고 제출했지만 틀렸다. 풀이는 들어봤는데 맞는 것 같았다. 01:50 태훈이가 K를 풀었다. 02:07 남일이가 I의 틀린 부분을 알아내고 맞았다. I의 아이디어는 나..