A. Equator$\!$
배열이 주어지면, 배열의 값을 더하다가 지금까지 더한 값이 배열값의 총 합 $/ 2$ 보다 크거나 같을때 그 index를 출력하는 문제이다.
설명필요없다.
B. Students in Railway Carriage
일렬의 좌석이 주어지고, 컴공생과 체대생이 자리에 앉으려한다. 컴공생은 컴공생옆에 앉지 못 하며, 체대생은 체대생옆에 안지 못 한다. 이때 최대한 앉을 수 있는 학생수를 구하는 문제다.
앉을 수 있는 자리 component를 각각 보자. component의 크기가 짝수이면 아무렇게나 서로 건너 앉으면 된다. component가 홀수 이면 컴공생이나 체대생 중 많은 숫자먼저 앉고 건너 앉으면 최대로 앉을 수 있다. 자리가 *...*일때 $a, b$가 1, 2라고 하면 *bab*가 최적일것이다.
한번 틀렸는데, 각 component마다 $a, b$값 중 큰 값으로 선택해서 먼저 채워넣어야하는데 그냥 첫 입력값이 $a$가 크면 전부 $a$먼저 채워넣어버렸다. 왜 그렇게 했는지는 모르겠다. ㅠ
양수 $n$이 주어지면, 그 숫자에서 $k$자리를 삭제해서 제곱수로 만들 수 있으면 $k$의 최솟값을, 아니면 -1을 출력하는 문제다. 단, 숫자의 앞자리가 0이 될 수없다.
$n$이 $2*10^9$ 이하이므로 최대 10자리란 소리다. $n$을 string으로 보고 bfs나 dfs나 완전탐색해서 하나씩 빼 보면서 제곱수 인지 체크해주면 된다.
string으로 보면 생각보다 좀 느린데 int로 보는것 보다 처리해줘야할게 훨씬 적기때문에 나쁘지않은 것같다.
진짜 부글부글 끓는 문제다.
수열이 주어지는데, 수열에서 2번 이상 나오는 값 중 가장 작은 값을 보자. 이 값들 중 가장 왼쪽 값은 수열에서 지워버리고, 그 다음 값은 2배 해준다. 이 작업을 계속 2번 이상 나오는 값이 없을 때 까지 했을 때 수열을 출력하는 문제다.
pair(값, index)를 저장하는 오름차순 priority_queue에 값을 싹다 넣고 두 개 빼고 값 비교해서 같은 값이면 문제에서 수행하라는 연산을 수행해주고, 아니면 다시 값 하나 더 빼서 비교하고 하는식으로 쭉 돌리면 간단하게 끝난다. 빌어먹을
문제에서 We choose the smallest value x that occurs in the array 2 or more times. 에서 smallest를 빼고 해석버렸다. 그래서 문제를 2개 이상 나오는 값들 중 가장 왼쪽값과 그 다음 값으로 생각해버렸다. 그래서 문제 난이도가 수 배 크게 느껴졌다. map으로 수 압축하고, priority_queue배열로 압축한 각 값의 index를 저장하고 priority_queue배열에서 size가 2이상인 녀석들을 다른 priority_queue에 넣어주면서 체크하고 난리 부르스를 찍었다. 한번 제출하고 나서 왜 틀렸나 디버깅해보다가 10분만에 문제 잘 못 읽은걸 발견해서 부랴부랴고쳐서 제출했는데 long long 안 해줘서 틀리고 겨우겨우 맞췄다. 어쩐지 좀 복잡한데 다들 간단하게 풀어서 map쓰는게 안 익숙해서 조금 느린갑다 생각했는데 개뿔.
제대로 읽었으면 10분 안에 풀었을 문제를 1시간 넘게 투자한게 너무 화가 난다.
E. Byteland, Berland and Disputed Cities
=수정중=
