월간 향유회 2024. 01.
조오금 말린 감이 있습니다아... (All solved at +00:59)
솔직히 조금 귀찮게 하는 구석들이... 있는데 전부 걸려들어서 조금 민망;;
A. 장난감 강아지
우선 S를 이용해 강아지를 이동해보면서 강아지의 모든 시각당 좌표를 구하자 (x[i], y[i]라고 할 수 있다)
그리고 마지막에 강아지의 위치를 (cx, cy)라고 하자.
그렇다면, 강아지가 있을 수 있는 좌표는 무조건 (x[i] + cx * p, y[i] + cy * p)가 된다. (단, 0 <= p < K)
따라서 x[i] + cx * p = 0, y[i] + cy * p = 0, 0 <= p < K인 p가 존재하는지 확인해주면 된다.
cx = 0, cy = 0에 대한 처리를 잘 해주면 틀릴 일이 없다.
처리를 개같이 해서 4번이나 틀렸다.
B. 캬루
흔히 알고 있는 배수판정법이 뭐가 있을까?
3의 배수판정법에 의하면, 각 자리수의 합이 3의 배수라면 항상 3의 배수이다.
따라서 모든 N개의 자리에 대해서 (0 ~ 9)를 넣어보면서 기존의 숫자가 아닐 때 3의 배수가 되는 경우를 출력해준다.
주의 1) 맨 앞자리는 0이 될 수 없다
주의 2) 답 자체가 3이 된다면 소수이기에 안된다
위의 두 주의점 때문에 (0~9)가 아니라 (4~9)를 넣는게 좋다.
C. 기부왕의 님게임
의도가 뭔지 고민을 딱히 하지 않았다.
숫자가 200으로 널널하게 주어지기에 DP[X][Y][Z] = (X, Y, Z일 때 선수가 내는 기부금)으로 정의했다.
-> DP[X][Y][Z] = MAX( X + Y + Z - DP[X - i][Y - j][Z - k] )가 된다. (단, 승패여부를 고려해야 하며, i, j, k 중 하나만 양수)
이때 DP[X][Y][Z] = DP[X][Z][Y] = ... 등으로 모두 동일하니 계산량을 1/6 가량 줄일 수 있다.
따라서 대충 200 * 200 * 200 * 200 / 6 번의 계산을 DP로 굴리면 답을 굴릴 수 있다.
D. LR
고려해야하는 부분문자열 [p, q]과 그 개수 cnt[p][q]를 관리하자.
예를 들어, 맨 처음에는 [0, N - 1]을 고려하며, 그 개수 cnt[0][N - 1] = 1개이다.
이것만 해주면 되고, 아래 기나긴 풀이는 구현일 뿐이다.
그러면 [0, N - 1]에서 파생될 수 있는 문자열은
-> L을 사용할 경우 A[0] + [1, N - 1]
-> R을 사용할 경우 A[N - 1] + [0, N - 2]
1) A[0] < A[N - 1]이라고 가정하자
1 - a) K <= 2^(N - 1)이라면, 우리가 구하는 문자열은 A[0] + [1, N - 1] 중에 있다.
-> A[0]를 출력하고, 다음 문자(=char)을 찾을 때 고려해야하는 부분문자열은 [1, N - 1]이다.
-> 이 경우 cnt[1][N - 1] = 1, cnt[0][N - 2] = 0이 된다.
1 - b) K > 2^(N - 1)이라면, 우리가 구하는 문자열은 A[N - 1] + [0, N - 2] 중에 있다.
-> A[N - 1]를 출력하고, 앞의 불필요한 2^(N - 1)개를 제거한 뒤(K -= 2^(N - 1)), [0, N - 2]만 고려한다
-> 이 경우 cnt[0][N - 2] = 1, cnt[1][N - 1] = 0이 된다.
2) A[0] == A[N - 1]이라고 가정하자
-> 우선 L를 하던, R을 하던, 어차피 맨 앞에는 A[0] == A[N - 1]이 오므로, 이를 출력한다
-> 이 경우 cnt[0][N - 2] = 1, cnt[1][N - 1] = 1이 똑같이 주어진다.
즉, i번째 문자를 찾을 때, 길이가 N - i + 1인 모든 부분문자열 [X, X + N - i]에 대해서
이들은 A[X], A[X + N - i]로 시작하는 문자열을 cnt[X[X + N - i] * (1ll << (N - i))개씩 만드므로
각 26개의 문자에 대해 그 문자로 시작하는 문자열의 개수를 셀 수 있고,
(맨 앞이 'a' + j보다 작은 개수) < K <= (맨 앞이 'a' + j보다 작거나 같은 개수)인 숫자 j를 구할 수 있고,
1) 'a' + j를 출력하고
2) 고려해야하는 부분문자열들, cnt[X + 1][X + N - i]나 cnt[X][X + N - i - 1]에 cnt[X][X + N - i]를 더해주고
3) K -= (맨 앞 문자가 'a' + j보다 작은 문자열 개수)
의 작업을 해주면 된다.
다만 N = 1000으로 무지하게 크고, cnt 또한 최악의 경우 매우 거대해질 수 있어 overflow를 걱정해야 한다.
따라서 이들을 1ll << 60 이하로 유지시켜주는 작업을 해주어야 한다. (K < 1ll << 60이기에 상관 없다)