ABC_166_E - This Message Will Self-Destruct in 5s
배열에서 두 원소를 선택할 때 값의 합이 인덱스의 차이의 절댓값이 되는 경우의 수를 구하는 문제. 뭔가 수학적인 것이 보일 듯 해서 정리를 해봤다. j > i로 고정하고 절댓값을 풀면 j - Aj = i + Ai 가 되는데 i + Ai가 몇개인지 계속 더해주면서 j에 대해 j - Aj 개수를 더해주면 된다. 참고:
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
Posts 34
82 81 ABC_178_E - Dist Max
x, y 좌표가 주어질 때 가장 먼 맨해튼 거리를 구하는 문제. 일단 유명한 문제라고 하는데... 처음 대회에서는 풀지 못했다... 다시 천천히 해보면 어렵지 않은 문제이긴 하다 먼저 조건을 잘 써보면,| xi - xj | + | yi - yj |의 최댓값을 찾는 문제인데 절댓값을 벗겨준 후 정리해줄 수 있다. xi > xj, yi > yj (xi - xj…
80 ABC_231 - Panasonic Programming Contest 2021(AtCoder Beginner Contest 231)
A, B, C, D A, B, C: 간단 D: 결론만 말하면 연결된 곳이 3개 이상이거나 사이클이 있을 경우 No가 출력되어야 한다. 불친절한 예제로 직접 예외 케이스를 찾아야 한다. 엄청난 삽질.. 끝에 dsu로 풀긴 풀었다.
79 ABC_191_C - Digital Graffiti
그리드에 #, .으로 이루어진 문자열이 주어질 때 이 도형이 몇각형인지 구하는 문제. 문제 설명, 예제가 불친절한데... 오목 다각형도 존재할 수 있다. 어쨌든 다각형이 몇각형인지 구하려면 꼭지점의 개수를 구해야 한다. 이건 에디토리얼을 참고했는데 상하좌우 2칸씩 개수를 세서 검은색 블록 (#)이 1개 또는 3개이면 꼭지점이다. 예시를 보면 좀 이해가 가긴…
78 ABC_223_D - Restricted Permutation
1부터 N까지 순열 중에 Ai의 위치 < Bi의 위치를 만족시키는 사전 순으로 가장 작은 순열을 구하는 문제. 잘 보니 위상 정렬 문제이다. 사전 순으로 출력해야 하므로 우선순위 큐로 처리해주고 정답 사이즈가 n이 아니면 사이클이 존재하는 것이므로 -1을 출력하면 된다.
77 ABC_192_E - Train
도시들이 있고 철도의 정보 (소요 시간, 출발하는 시각)이 주어질 때 x 에서 y로 가는 최소 시간을 구하는 문제. 전형적인 다익스트라 문제이다. 단, 기차가 ki 의 배수로만 출발하므로 이를 보정하기 위해 ki 배수 미만이면 ki 배수로 만들고 ti를 더하도록 하였다.
76 ABC_230_D - Destroyer Takahashi
모든 벽을 부수기 위해 최소 몇 번 펀치를 해야 하는지 구하는 문제. 모든 벽을 부숴야 하므로 정렬 후 왼쪽부터 쭉 나가면 될 것 같다. 근데 이게 생각보다 안돼서... 대회 중에 결국 못 풀었다 에디토리얼을 참고해서 재작성. 일단 정렬은 맞는데 오른쪽 좌표를 기준으로 정렬해야 한다. 해당 벽을 제거할 때 최대한 오른쪽을 제거해야 다른 벽도 같이 제거할 수…
75 ABC_230 - AtCoder Beginner Contest 230
A, B, C A, B: 간단 C: 칠해지는 좌표의 규칙을 알면 된다. i-j, i+j 값을 이용하면 칠해지는 위치인지 판별 가능하다.
74 ABC_228 - TOYOTA SYSTEMS Programming Contest 2021(AtCoder Beginner Contest 228)
A, B, C, D A, B 간단. 단, A는 처음에 이해가 안되서 1번 틀림... C: 정렬을 한 후 자신보다 300점 높은 개수를 세고 K보다 작거나 같으면 Yes 출력. 개수를 셀 때 upper bound 이용. D: 들어갈 수 있는 자리를 map으로 예약해두고 값이 업데이트 될 때마다 제거, 자리를 찾는 건 lower bound 이용. 단, n을 넘…
73 ABC_080_C - Shopping Street
상점을 오픈하는데, 특정 시간에 다른 상점이 열린 개수에 따라 최대로 만들 수 있는 이익을 구하는 문제. Fij : i 상점이 j 시간에 열려 있는지 여부. Pij : i 상점이 j 시간만큼 열린 시간이 겹쳤을 때 얻을 수 있는 이익. 처음에 문제 자체를 이해하기 좀 어려웠는데 계속 보니까 대략 머리에 들어왔다. 일단, Joisino가 상점을 열지 말지 두…