PS (26) 썸네일형 리스트형 [ICPC 2020 Korea regional 풀이] 대회는 끝났지만 다시 풀어보면서 풀이를 올려보려고 한다. K. Tiling Polyomino 어제 문제가 올라왔지만 [계ㅡ측] 당해서 오늘 부관참시를 했다. 풀이는 굉장히 다양하게 존재하는 것 같으나 내 풀이(4500B)와 아인타 선생님의 훌륭한 풀이(1800B)를 적겠다. [4500B 망한 풀이] 모든 점의 deg가 2이므로 대부분의 경우 그래프가 뭉쳐있게 생겼다. 만약 deg가 2인 P의 점들이 모두 [관찰 1]이런 모양이라면, 단방향의 타일만 가지고도 덮을 수 있음이 쉽게 보장된다. [관찰 2]따라서 정사각형이 line을 이루게 될 경우만 따로 고려해주면 되고, 우리는 큰 컴포넌드들을 하나로 묶고, (deg가 2인) line의 점들로 이루어진 트리를 만들 수 있다. 트리의 리프는 무조건 큰 컴포넌트.. [KOI 2020 고등부] 이틀 전 KOI 고등부 open contest에 참가해 문제를 풀어봤다. 확실히 코딩실력에는 문제가 많다는 것을 느꼈고, 다양한 구현문제와 자료구조 문제들을 풀어보면 좋겠다는 생각을 했다. 그리고 블로그를 계속 한다면 블로그 포맷?들도 배우면 좋겠다고 생각된다. 1. 줄임말(3 try) S를 T*N번의 subsequence로 나타낼 수 있겠냐는 문제이다. S와 T의 알파벳을 제한할 이유는 없었던 것 같다. [풀이] T의 각 알파벳이 몇번째에 등장하는지 벡터로 저장하고, lower_bound질을 하면 된다. 인덱스를 계속 틀려서 3트라이를 박았다. 2. 순서 섞기(2 try) 수열 A가 주어질 때, A의 양 끝점을 하나씩 떼어나가면서 차곡차곡 쌓아 새로운 수열을 만드는 과정을 M번 반복하여 증가수열이 되도.. [ICPC Seoul Regional] PS를 시작한 지 2년이 살짝 넘어서 참가한 두 번째 ICPC 본선을 최종 성적 11솔브, 전체 3등으로 마무리했습니다. 나름 한 달 동안 창기가 열심히 골라 추천해준 문제들을 풀어보기도 했고 자신감도 늘었었는데 팀에 큰 도움이 되지 못한 것 같네요. 언제는 안 그랬냐만은 태규가 정말 멱살을 잡고 끌고 가다시피 했습니다. 풀이 도움이 거의 없이 혼자 8솔브를 했다는 점에서 같은 팀원으로써 정말 미안하다는 생각밖에 들지 않네요. 모든 대회에서 하등 의미없는 말이지만 운이 좋았다면 더 높은 등수도 기대할 수 있었을 것 같은데 제가 망친 느낌입니다. 하하. 저희 팀에서 저는 나머지 두 팀원에 비해 코딩 실력이 현저히 떨어져서 거의 알고리즘의 생각만 하고 약간의 디버깅만 해주는 편입니다. 그리고 PS 입문한지가.. [ICPC 본선 대비 뇌셋] Day 22 Day를 그냥 연장시키는 이유는 예뻐보이기 위해서이고 딱히 다른 이유는 없다. 남는 시간동안에 몇문제 더 풀어보기로 했다. 백준 5250번 최단 경로들 www.acmicpc.net/problem/5250 5250번: 최단 경로들 각각의 정수 t = 1 … k – 1에 대해, 각 줄마다 도로 (vt, vt+1)가 닫혔을 경우에 마을 a와 마을 b 사이의 최단 경로의 길이를 출력하라. 만약 경로가 없다면 -1을 출력하라. www.acmicpc.net 신기한 문제인거같다. [생각 1] 한 간선이 빠졌을 때 다른 최단 경로를 생각하면 뭔가 이전의 최단경로를 잘 이용해야할 것 같은 느낌이 든다. 따라서, 처음에 주어진 최단경로의 시작을 a, b라고 하면, a와 b로부터 각각 다익스트라를 해준다. [생각 2] 어떤.. [ICPC 본선 대비 뇌셋] Day 21 ICPC 본선 대비 뇌셋 포스팅 대망의 마지막 날이다. 작년에 못풀었던 문제들중 한문제인 2019년 ICPC Korea regional E번을 생각해봤다. 자료구조까지는 생각하지 않았지만, $O(N^2 lg(N))$에 풀리게 생겼다. 백준 17972번 Network Vulnerability www.acmicpc.net/problem/17972 17972번: Network Vulnerability Your program is to read from standard input. The first line contains a positive integer n representing the number of intervals, where n ≤ 2,000. In the following n lines, each.. [ICPC 본선 대비 뇌셋] Day 20 이제 이 제목의 글도 내일이면 끝이다.백준 10167번 금광 www.acmicpc.net/problem/1016710167번: 금광첫 줄에는 금광들의 개수 N (1 ≤ N ≤ 3,000)이 주어진다. 이어지는 N개의 줄 각각에는 금광의 좌표 (x,y)를 나타내는 음이 아닌 두 정수 x와 y(0 ≤ x,y ≤ 109), 그리고 금광을 개발하면 얻게 되는 이익 www.acmicpc.net오늘은 좀 쉬어가는 느낌으로 금광을 짰다. 풀이는 대충 창기한테 들었고, 구현을 해봤는데 시간이 좀 느리게 나왔다. 다른 여러 블로그에 풀이가 많으니 그걸 보는게 좋을 것 같다. 물론 이런 문제가 나오면 이메이미가 밀겠지만 어떻게 생겨먹은 세그인지는 알고싶어서.. 오늘 좀 놀았는데 그러기엔 죄책감이 들어서 재작년에서 어려웠던.. [ICPC 본선 대비 뇌셋] Day 19 백준 2427번 2012 지구 멸망 www.acmicpc.net/problem/2427 2427번: 2012 지구 멸망 3명씩 3개의 그룹으로 나누면, 각 그룹은 회의가 4분씩 걸리고, 다시 마지막에 3명이 회의에 참석해서 회의를 하면 4분이 걸리므로, 8분이 걸린다. www.acmicpc.net V가 i번, P가 j번 사용 될 때 가능한 최대 횟수가 얼마일지를 구해준 다음 이를 이용해서 최소 시간을 구해주면 된다. dp식은 다음과 같다. $dp[i][j] = max(dp[i][j], dp[i-1][k]*(j-k))$ for{k=j-2 ; k>= max(j-2050, 0) ; k--} dp가 왜 성립하는지에 대한 정당화가 필요하지만 개인적으로 다이아3 정도는 아닌 듯 하다. [증명] bottom top으.. [ICPC 본선 대비 뇌셋] Day 18 백준 2574번 마법색종이 www.acmicpc.net/problem/2574 2574번: 마법색종이 첫째 줄에는 색종이의 가로의 길이와 세로의 길이를 나타내는 양의 정수가 빈칸을 사이에 두고 주어진다. 가로와 세로의 길이는 모두 40,000 이하이다. 둘째 줄에는 색종이를 자르기 위한 점의 개 www.acmicpc.net 반도에 사는 초등학생의 위엄을 볼 수 있는 문제다. KOI 초등부 06년도 3번 문제인데, 지금까지 풀어본 바로 KOI는 좀 구현이 더럽거나 생각이 더러운 문제를 많이 내는거같다. 풀이는 여러가지가 있을 수 있는데, 두가지만 적겠다. [풀이 1] 2D Seg 영역 더하기 쿼리를 진행하면 된다... 세그에서 더할 변수를 A, B로 두개를 잡는다. A는 그 블록의 인덱스를 나타내는 변수이.. [ICPC 본선 대비 셋] Day 17 오랜만에 팀연습을 돌았다. 자카르타 2017 Regional 이었다. 처음 본 문제가 F인데, 딱봐도 수학이길래 레프한테 넘겼다. 그 다음 본 문제는 G, 기하였고 두 원의 교점이 어디에 있는지를 구해야했는데, 그 과정이 그냥 jot이었다. 그래서 일단 패스. 그리고 본 문제는 E다. dp를 엄청 조지면 풀리는 문제였고, dp식까지는 구했는데, 너무 복잡해서 일단 풀이만 적어두고 넘겼다. J를 레프가 대충 보고 넘겼는데, 거의 셋에서 제일 쉬운 문제여서 내가 짰다. --> 구현의 왕 즈홒의 활약으로 3틀 이후 AC 이제 남은 문제는 D였는데, parent, child관계가 있었으나 그걸 못봐서 문제가 엄청 어려워졌다. 문제를 다시 읽고 나서 짠 뒤 마찬가지로 구현의 왕 등판해서 4틀 후 AC. 남은 문제.. [ICPC 본선 대비 뇌셋] Day 16 이번에 레프와 같이 다이아를 다섯개쯤 쌓아두고 네시간동안 흙찡구놀이를 했다. 물론 처참하게 발렸다. 백준 10014번 Travleling Saga Problem www.acmicpc.net/problem/10014 10014번: Traveling Saga Problem n개의 정점으로 이루어진 가중치 없는 사과나무가 있고, 1번 정점에 사과 한 알이 매달려 있다. 여행을 좋아하는 사과는 사과나무의 모든 정점을 정확히 방문하려고 한다. 사과는 방문하지 않은 www.acmicpc.net 나답게 그리디스럽게 접근하다가 레프가 걍 센트로이드로 풀면 된다고 했고(트쿼 4와 유사한가보다) 그쪽으로 풀이를 짰다. 풀이 자체는 간단하다만 세시간동안 메모리초과와 시간초과를 사이좋게 나눠 받다가 사망했다. [풀이] 세상에.. 이전 1 2 3 다음
