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 (•̀ᴗ•́)و
study 29
82 81 ABC_178_E - Dist Max
x, y 좌표가 주어질 때 가장 먼 맨해튼 거리를 구하는 문제. 일단 유명한 문제라고 하는데... 처음 대회에서는 풀지 못했다... 다시 천천히 해보면 어렵지 않은 문제이긴 하다 먼저 조건을 잘 써보면,| xi - xj | + | yi - yj |의 최댓값을 찾는 문제인데 절댓값을 벗겨준 후 정리해줄 수 있다. xi > xj, yi > yj (xi - xj…
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
모든 벽을 부수기 위해 최소 몇 번 펀치를 해야 하는지 구하는 문제. 모든 벽을 부숴야 하므로 정렬 후 왼쪽부터 쭉 나가면 될 것 같다. 근데 이게 생각보다 안돼서... 대회 중에 결국 못 풀었다 에디토리얼을 참고해서 재작성. 일단 정렬은 맞는데 오른쪽 좌표를 기준으로 정렬해야 한다. 해당 벽을 제거할 때 최대한 오른쪽을 제거해야 다른 벽도 같이 제거할 수…
73 ABC_080_C - Shopping Street
상점을 오픈하는데, 특정 시간에 다른 상점이 열린 개수에 따라 최대로 만들 수 있는 이익을 구하는 문제. Fij : i 상점이 j 시간에 열려 있는지 여부. Pij : i 상점이 j 시간만큼 열린 시간이 겹쳤을 때 얻을 수 있는 이익. 처음에 문제 자체를 이해하기 좀 어려웠는데 계속 보니까 대략 머리에 들어왔다. 일단, Joisino가 상점을 열지 말지 두…
72 ARC_091_B / ABC_090_D - Remainder Reminder
N을 넘지 않는 a, b 쌍 중에서 a % b가 K 보다 크거나 같은 개수를 구하는 문제. 예제 1에 힌트가 있는데, b에 대해 K + 1부터 N까지 다 돌려가면서 나머지가 K 이상이 되는 a의 개수를 구해주면 된다. N % b를 r로 두면, a가 r 이하인 경우엔 N / b + 1번 가능하고 r보다 큰 경우는 N / b번만 가능하다. K == 0일 땐, …
70 ABC_140_D - Face Produces Unhappiness
사람들이 L, R 방향을 바라보며 서 있고, 서로 같은 방향을 바라보면 happy이다. 이때 k 번의 횟수만큼 (l, r) 범위의 사람들의 방향을 뒤집을 수 있다. 최대로 happy 하게 만들 수 있는 사람의 수를 구하는 문제. 딱 보면 어려운데 포인트를 잘 알아채면 굉장히 쉬워지는 문제. 위 사실을 알면 쉽게 풀린다. 먼저 간단한 증명은 LLL ... R…
69 CODEFESTIVAL_2016_QUALA_C - Next Letter
문자열과 k가 주어진다. k번 연산을 통해 만들 수 있는 사전 순으로 가장 작은 수를 구하는 문제. 연산: 다음 문자로 변경, 단 z는 a로 변함. 일단 그리디 적으로 생각해보면 사전 순으로 최소가 되려면 앞 문자를 최대한 a로 만들어야 한다. a로 만들 수 없으면 아예 연산을 안 하는 것이 낫다. 위 두 규칙에 맞게 문자열을 돌면서 계산해주면 된다. 단,…