AtCoder Beginner Contest 258

A. When?

code

문제 설명

정수 \(0 \le K \le 100 \)이 주어진다. 21:00 으로부터 \(K\)분 지난 시간을 hh:mm 형식으로 출력해야 한다.

알고리즘

60분 이상인 경우 hour에 1을 더해주고, minute를 60만큼 빼준 뒤 출력하면 된다.

B. Number Box

code

문제 설명

정수 \(1 \le N \le 10\)과 \(N \times N\)짜리 정사각 행렬이 주어진다. 행렬의 각 값은 1이상 9이하이다.

한 점을 정한 뒤, 상하좌우와 대각선까지 총 8방향 중 한 방향을 정해 \(N-1\)칸 움직인다.

만약 범위 바깥으로 나가면 행렬의 반대 방향으로 이동한다. 예를 들어, 맨 왼쪽에서 왼쪽 방향으로 이동하면 맨 오른쪽으로 이동한다.

이와 같이, 총 \(N\)칸을 밟게 되고 밟은 칸에 적힌 숫자를 밟은 순서대로 적으면 N자리 숫자가 된다.

만들 수 있는 \(N\)자리 솟자 중 가장 큰 숫자를 구해야 한다.

알고리즘

\(N\)의 범위가 작기 때문에 만들 수 있는 모든 숫자를 구하고, 그 중 가장 큰 숫자를 출력하면 된다.

C. Rotation

code

문제 설명

문자열의 길이 \(N\)과 쿼리의 수 \(Q\) 그리고 문자열 \(S\)가 주어진다.

각 쿼리는 \(1 \space x\), \(2 \space x\) 중 하나이다.

\(1\space x\)의 경우 문자열의 맨 끝에 있는 문자를 땐 뒤, 맨 앞으로 옮기는 작업을 \(x\)회 수행한다.

\(2\space x\)의 경우 문자열의 \(x\)번째 문자를 출력한다.

알고리즘

첫 번째 쿼리를 수행할 때, 문자열을 실제로 옮기지 말고 해당 작업을 \(x\)회 수행한 뒤의 문자열의 첫 번째 문자가 원래 문자열의 어느 위치에 해당하는 지를 계산하면 된다.

두 번재 쿼리를 수행할 때, (첫 번째 문자의 위치 + x) 위치에 있는 문자를 출력해주면 된다.

D. Trophy

code

문제 설명

이 게임에는 총 \(N\)개의 stage가 있다. 처음에는 1번 stage만 들어갈 수 있고 \(i\)번째 stage를 깨면 \(i+1\)번째 stage에도 들어갈 수 있다.

처음 i번째 stage를 깰 때에는 \(A_i + B_i\) 분이 소요되지만, 그 이후에는 \(B_i\)분만 소요된다.

stage 종류를 구분하지 않고, 총 \(X\)번 stage를 깨려고 할 때 필요한 최소 시간을구해야 한다.

알고리즘

먼저 \(S_i = A_1 + B_1 + A_2 + B_2 + ... + A_i + B_i\)로 정의하자.

그렇다면 i번째 stage까지 클리어한 후, i번째 stage를 \(X-i\)번 더 깨는 데 필요한 시간은 \(S_i + max(0, X-i) * B_i\)가 된다.

i stage까지 클리어한 뒤, j < i인 j stage를 \(X-i\)번 깨는 경우가 더 최적일 수 없다. 만약 i stage까지 클리어한 뒤, j stage를 계속 깨는 것이 더 좋다면, j+1, j+2, ... i번 stage를 깨는 것이 j번 stage를 깨는 것보다 더 적은 시간이 걸린다는 것을 의미한다. 하지만 처음 깨는 데 걸리는 시간은 \(A+B\)이고, 다시 깨는 데 걸리는 시간이 \(B\)이므로, 이는 \(A < 0) 인 경우가 있다는 의미이므로 모순이 발생한다.

따라서 i번째 stage까지 클리어한 후, i번째 stage를 \(X-i\)번 더 깨는 데 필요한 시간을 모든 stage에 대해 구한 뒤 최솟값을 출력해주면 된다.

E. Packing Potatoes

code

문제 설명

무한히 많은 감자들이 있다. \(N\)개의 감자 무게가 주어지고, i번째 감자의 무게는 \(W_{(i-1) mod N}\)이다.

첫 번째 상자에는 첫 번째 감자부터 순서대로 넣는다. 만약 상자에 넣은 감자의 무게가 \(X\)를 넘어가면 해당 상자를 포장한다. 그리고 두 번째 상자도 다음 감자부터 무게가 \(X\)가 넘어갈 때가지 감자를 넣고 상자를 포장한다. 이를 무한히 반복한다.

총 Q개의 쿼리가 주어진다. 각 쿼리는 \(K_i\)로 이루어져 있으며, \(K_i\) 번째 상자에 몇 개의 감자가 들어있는 지를 출력해야 한다.

알고리즘

\(X\)를 \(sum(W)\)의 나머지로 바꾼 뒤, 최종 정답에는 \(X / sum(W) * N\)만큼 더한 뒤 출력한다. \(N\)개의 감자를 \(X / sum(W)\)

i번째 감자를 상자에 넣기 시작할 때, 몇 번째 감자까지 넣어야 무게가 \(X\) 이상이 되는 지를 계산한다. 

queue를 이용하면 이를 \O(N)\)에 구할 수 있다. 이 값을 이용하면, i번째 상자가 몇 번째 감자부터 넣었는지 알면 i+1번째 상자는 몇 번째 감자부터 넣었는지 알 수 있다.

그 후, sparce table을 이용하면, i번째 감자를 몇 번째 상자에 넣었는지 알면 임의의 정수 \(k\)에 대해 i+k번짜 상자는 몇 번째 감자부터 넣는지 알 수 있다.

sparce table을 이용하여 각 쿼리를 처리할 수 있다.

F. Main Street

code

문제 설명

총 \(Q\)개의 아래 쿼리를 처리해야 한다.

모든 자연수 \(n\)에 대해 \(x=n\), \(y=n\)의 길이 있다.

자연수 \(B\)에 대해, 모든 \(x=Bn\), \(y=Bn\)은 큰 길이고 나머지는 작은 길이다.

상하좌우로 1만큼 이동할 수 있고, 큰 길로 이동하면 1초, 작은 길로 이동하면 \(K\)초가 소요된다.

\(S_x, S_y\)에서 \(G_x, G_y\)로 이동하는 데 걸리는 시간을 구해야 한다.

알고리즘

case work로 문제를 해결할 수 있지만, 어렵기 때문에 다익스트라를 이용하여 풀었다.

한 점이 있으면, 그 점 바로 옆에 있는 \(x\)축 방향 큰 길 2개와 \(y\)축 방향 큰 길 2개, 그리고 그 점을 포함하는 작은 길 각 축 방향으로 1개씩만 고려하였다.

시작점과 끝점, 2개의 점이 주어지므로 고려해야 할 x좌표와 y좌표는 각각 6개로 고려해야 할 총 교점의 수는 36개이다.

36개의 점 위에서 시작점부터 끝점가지 가는 데 걸리는 최소 시간을 다익스트라를 이용하여 구한 뒤 출력했다.

G. Triangle

code

문제 설명

정점의 수가 \(1 \le N \le 3000\)개인  방향이 없는 단순  그래프의 인접 리스트가 주어진다.

만약 \(i, j\)를 잇는 간선, \(j, k\)를 잇는 간선 그리고 \(k, i\)를 잇는 간선이 주어지면 \(i, j, k\)는 삼각형이다.

서로 다른 삼각형의 개수를 출력해야 한다.

알고리즘

i, j를 고정하고, 삼각형을 만들 수 있는 k의 수를 bitset을 이용하면 \(O(\frac{N}{\omega}), \omega = 64\) 안에 구할 수 있다.

따라서 간선이 존재하는 i, j 에 대해 가능한 k의 수를 모두 구한 뒤 합을 출력하면 된다.