A. Aramic script$\!$
입력으로 문자열이 들어오는데, 각 문자열이 가지는 문자의 집합의 개수를 세는 문제이다.
예를 들어 a aa aaa의 각 문자 집합은 a로 동일하므로 1을 출력해야하며,
a aa aaa ab abab abbbb 는 {a}, {a, b}로 2개이므로 2를 출력해야한다.
간단히 들어온 문자열을 정렬한 뒤, unique 함수로 문자를 중복없게 뽑아낸 뒤, set<string>에 넣어주면 된다.
한 번 틀렸는데, unique함수가 sorted 상태의 stl만 받는 다는 점..
14칸 짜리 판에 구슬이 들어있는데 (0개 이상), 1개 이상의 구슬이 들어 있을 경우, 그 칸의 구슬을 모두 뽑아서 오른쪽으로 1칸씩 이동하면서 그 구슬을 1개씩 넣을 수 있다. 모두 넣고난 뒤, 각 14개의 칸에 짝수개의 구슬의 합이 점수다.
이 행위를 딱 1번 수행했을 때 최대 점수를 구하는 문제이다.
칸이 14개로 고정이므로 그냥 1개 이상의 구슬이 들어있는 칸에서 뽑아서 다 분배해보는 식으로 하면 통과된다.
한 번 틀렸는데, 처음상태의 각 칸의 구슬의 개수가 최대 $10^9$개 이므로 14로 나눈 몫과 나머지로 처리해주어야 하는데 몫을 처리할 때 if문을 잘 못 설정했다.
영어가 안 되니 이런 문제는 해석이 참...
n명의 병사의 체력이 각각 $a_i$이고 한 차례 화살을 쏠 때 $k_j$번 쏘는데, 각 차례마다 화살을 다 쏜 뒤에 남아있는 병사의 수를 출력하는 문제이다. 그런데 만약 병사가 모두 쓰러지면 토르(?)가 망치를 휘둘러 모든 병사를 다시 살린다. 단, 이번 차례에 쏠 화살이 남아있는데 병사가 모두 죽어 다시 살리는 경우, 남아있는 화살이 살아난 병사를 쏘지는 않는다. 즉, 모두 무시된다.
$a_i$의 부분합을 구해놓은 뒤, $k_j$의 sum을 부분합 배열의 lower_bound로 위치를 찾고 적절히 처리하면 답을 구할 수 있다.
lower_bound로 index를 찾은 뒤, 부분합[index]의 값과 $k_j$의 sum이 같은 경우와 다른 경우로 나누어 주어야하고,
또한 $j$번째 화살을 쐈을 때 모든 병사가 죽는다면 $k_j$의 sum을 0으로 맞춰주고 n을 출력하고 하는 식으로 조금 귀찮게 구현했는데 생각해보니 upper_bound로 때려버리면 깔끔하게 때려진다.
항상 lower_bound를 생각할 때에는 upper_bound로 때려버리면 더 간단하게 풀리지 않는지 한번 생각하고 넘어가야겠다.
A, B, C 모두 풀고 난 뒤 1시간동안 고민했는데 결국 못 푼 문제다. 답지는 정말 간단하고 명료하게 잘 구현해놔서 허탈하다.
모든 각 유령들은 $V_x, V_y$의 일정한 속도로 각각 x, y축을 움직이는데, 어떠한 시간(T)에 모든 유령들의 위치가 우연히도 $y=ax+b$의 직선위에 위치하게 된다. 이때, 각 유령들이 서로 만나게 되는 횟수를 구하는 문제이다. 물론 이 횟수는 어떠한 시간(T)이후에 만난 횟수와 어떠한 시간(T)이전에 만난 횟수 모두를 의미한다.
직선 $y=ax+b$가 주어지고, T일 때 각 유령의 x좌표 그리고 각 유형의 속도들이 모두 주어지므로 유령의 t시간에서의 위치는 $(V_x*t+x, V_y*t+y)$가 된다.
두 유령 i, j가 어떤시간 t에 만나려면 $( V_{x_i}*t_x+x_i, V_{y_i}*t_y+y_i) == (V_{x_j}*t_x+x_j, V_{y_j}*t_y+y_j) $의 등식이 성립하는 $t_x, t_y$가 서로 같으면 어떤 점에서(어떤 점인지는 알 필요가 없다)만나게 된다.
여기서 나오는 두 식을 잘 정리하면 $aV_x -V_y$가 같은 점들은 서로 만나게 되어있다. $aV_x -V_y$가 같지만 만나지않는 경우가 존재하는데, $(V_x, V_y)$ pair가 같은 경우이다. 즉, $aV_x -V_y$가 같은 경우 중 $(V_x, V_y)$ pair가 같은 경우의 개수를 빼주면 정답이다.
문제는 O($n^2$)으로 TLE가 뜬다는 점이다. BOJ-전깃줄문제처럼 하나를 입력받을 때 마다 $aV_x -V_y$가 같은 개수와 $(V_x, V_y)$ pair가 같은 개수를 ++해주면서 ONLINE알고리즘 처럼 풀면 O($n * map과 set속도$)만큼 빠르게 나온다.
$aV_x -V_y$가 같은 놈들 중 $(V_x, V_y)$ pair가 다른 녀석들만 만난다는 점을 캐치해내기도 까다롭지만 BOJ-전깃줄문제처럼 처리해줘야한다는 점도 조금 어려웠다. 느낌상 이렇게 처리해줘야한다는 것을 생각해내긴 했지만 BOJ-공장문제와도 비슷해서 2D segmentTree인가? 라는 생각도 잠깐 했다.
비록 D번을 시간내에 문제를 풀지는 못 했지만, set이나 map을 써야되겠다하는 점과 ONLINE으로 처리해줘야겠다 하는 생각을 조금이나만 했기때문에 나름 알고리즘 공부하면서 뿌듯했던 순간이었다. 못 풀었지만.. ㅠ
