ABC 339 D번 복기 - 4차원 visited 배열 BFS 백트래킹

1. 문제 D - Synchronized Players (atcoder.jp) D - Synchronized Players AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 하라는대로 구현하면 된다 두 플레이어 P가 움직이는데 두 플레이어는 같은 방향으로 움직이게 되어있다. 또한 한 플레이어가 해당 방향으로 움직일수 없더라도 다른 플레이어가 움직일 수 있다면 움직이는 경우로 생각한다 그래서 먼저 두 플레이어의 위치를 찾고 BFS를 수행하는 전형적인 형태 n = int(stdin.readline()) maps = ..

  • format_list_bulleted 경쟁 프로그래밍/Atcoder
  • · 2024. 2. 5.
  • textsms

ABC 336 C번 복기 - 0,2,4,6,8로만 만든 숫자들 중 n번째 숫자를 찾는 놀라운 방법

C - Even Digits (atcoder.jp) C - Even Digits AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 0,2,4,6,8로만 이루어진 모든 10진수 정수들을 오름차순으로 나열할 때, N번째 숫자를 구하는 문제 N이 $10^{12}$까지니 다 해보면 당연히 시간 초과일거고 최초 몇가지를 한번 나열해보면? 0 0 2 1 4 2 6 3 8 4 20 10(5) 22 11(5+1 = 6) 24 12(5+2 = 7) 26 13(5+3 = 8) 28 14(5+4 = 9) 0,2,4,6,8,20,22,24,26..

  • format_list_bulleted 경쟁 프로그래밍/Atcoder
  • · 2024. 1. 21.
  • textsms
ABC 337 D번 복기 - 2차원 배열에서 행,열로 연속한 O의 개수를 빠르게 세는 방법(sliding window + prefix sum)

ABC 337 D번 복기 - 2차원 배열에서 행,열로 연속한 O의 개수를 빠르게 세는 방법(sliding window + prefix sum)

D - Cheating Gomoku Narabe (atcoder.jp) D - Cheating Gomoku Narabe AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp . o x로 이루어진 2차원 배열에서 .을 o로 바꿀 수 있다. 이 때 행이나 열로 연속한 o의 개수가 k개가 되도록 최소로 바꾸는 횟수 처음에 DFS로 o의 좌표에서 시작해서 .을 o로 바꿔서 해보다가 당연히 시간초과났고 그러다가 행이나 열 각각에서 모두 조사해보면 된다는 생각이 들었다 여기까지는 좋았음 행 한줄에서 어떻게 .을 o로 바꿔야 연속한 o의 ..

  • format_list_bulleted 경쟁 프로그래밍/Atcoder
  • · 2024. 1. 21.
  • textsms
ABC 335 C번 복기 - 놓치기 쉬운 deque를 사용할 때 주의할 점(deque indexing is O(N)) + 배열과 연결리스트 접근 시간복잡도 차이

ABC 335 C번 복기 - 놓치기 쉬운 deque를 사용할 때 주의할 점(deque indexing is O(N)) + 배열과 연결리스트 접근 시간복잡도 차이

1. 문제 C - Loong Tracking (atcoder.jp) C - Loong Tracking AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 1번부터 N번까지 좌표가 있고, 1번 좌표는 쿼리에 의해 움직이게 된다. 1번 좌표가 움직이면, 2번,3번,4번,...,N번 좌표는 각각 1번,2번,3번,...,N-1번 좌표가 된다. 쿼리가 20만개이고 좌표수도 최대 100만개라 단순하게 접근하면 시간초과를 받을 것인데 그림으로 생각해보면 접근법을 생각할 수 있다 처음에 배열에 1번부터 N번까지 좌표가 있는데, ..

  • format_list_bulleted 경쟁 프로그래밍/Atcoder
  • · 2024. 1. 7.
  • textsms
ABC 333 D번 복기 - 리프 노드부터 특정 노드까지 최소로 지우는 법

ABC 333 D번 복기 - 리프 노드부터 특정 노드까지 최소로 지우는 법

1. 문제 D - Erase Leaves (atcoder.jp) D - Erase Leaves AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 리프 노드부터 차례대로 지울 수 있을때, 1번 노드를 지우기 위해서 최소로 지워야하는 노드의 개수는 몇개인가? 평소에 골드3정도 트리 DP 문제를 연습했더니.. 해법이 보이긴 하더라 리프 노드라는 것은 자식이 없는 노드인데, 목표로 하는 노드가 1번 노드니까, 1번 노드를 루트라고 생각한다면.. 다음과 같은 트리는 다음과 같이 바꿀 수 있는데, 이런 경우에 리프 노드부터..

  • format_list_bulleted 경쟁 프로그래밍/Atcoder
  • · 2023. 12. 17.
  • textsms

ABC 332 D번 복기 - 행,열 바꿔서 다른 2차원 배열과 똑같이 만드는법(BFS가 된다고?)

1. 문제 D - Swapping Puzzle (atcoder.jp) D - Swapping Puzzle AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 비슷한 문제들이 그리디로 풀려가지고... 숫자 다르면 무조건 바꾸는 그리디인가도 생각해봤는데.. 제한이 H,W가 5 이하라서 완전탐색이 가능할 것 같다고 생각을하고, 생각까진 하더라도 완전탐색을 어떻게 해야할지.. 근데 그 전에 문제부터 제대로 못읽었던것도 문제.. Choose an integer i satisfying 1≤i≤H−1 and swap the i..

  • format_list_bulleted 경쟁 프로그래밍/Atcoder
  • · 2023. 12. 11.
  • textsms