PS/2020 ICPC 본선 대비 뇌셋 (23) 썸네일형 리스트형 [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와 유사한가보다) 그쪽으로 풀이를 짰다. 풀이 자체는 간단하다만 세시간동안 메모리초과와 시간초과를 사이좋게 나눠 받다가 사망했다. [풀이] 세상에.. [ICPC 본선 대비 뇌셋] Day 15 백준 18753번 Alternative Accounts www.acmicpc.net/problem/18753 18753번: Alternative Accounts For each test case, output one line with one integer: the answer. www.acmicpc.net k를 하나씩 늘려가다보면 벤다이어그램을 그려볼 생각을 할 수 있다. [관찰 1] 벤다이어그램에서 같은 contest에 속한 계정은 다른 오너가 운영해야한다. 관찰 1로부터 k [ICPC 본선 대비 뇌셋] Day 14 백준 20077번 Wiring www.acmicpc.net/problem/20077 20077번: Wiring C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang) www.acmicpc.net IOI기출은 처음 풀어보는듯..? 문제가 되게 좋았다. 물론 코딩은 안했다.ㅋㅋ 생각도 나름 오랫동안 한거같다. 섭테를 보고 힌트를 좀 얻은것 같기도 하다. [관찰 1] 그림과 같이 최적의 상황에서 파랑과 빨강은 연속한 블록에서만 이어져야 한다. [관찰 2] 그림과 같이 두 그룹간의 간선이 겹치면 안된다. 따라서 최적의 경우는 다음과 같이 노란색 그룹 안에서만 연결이 일어나야한다. 그리고 각 그룹에서 노드 사이의 거리는 최소 그림 위에 적혀있는 숫자만큼.. [ICPC 본선 대비 뇌셋] Day 13 백준 16128번 스눕시티 www.acmicpc.net/problem/16128 16128번: 스눕시티 첫 줄에 땅의 크기를 의미하는 정수 N과 일일 퀘스트가 주어지는 날의 수를 의미하는 정수 M(1 ≤ N ≤ 40, 1 ≤ M ≤ 100,000)이 주어진다. 땅의 크기는 2N × 2N임에 유의하라. 둘째 줄에 최초의 꽃밭의 www.acmicpc.net 간만에 쉬운문제다. 사실 광고 매칭 문제를 풀다가 막혔고, 어제 계측때문에 포스팅을 계속 못했다. 꾸준히하는게 정말 어려운 것 같다. [풀이] 몇번 요리조리 돌려보면, A(이전 점), B(이후 점)의 x, y좌표를 각각 2진법으로 볼 생각을 할 수 있다. A, B의 x, y좌표가 가장 많이 겹치는 prefix를 잡으면, A지점에서 prefix지점까지 이동.. 이전 1 2 3 다음
