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(N2lg(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 다음 목록 더보기
