10/15~10/16 Atcoder 연습

10/15~10/16 Atcoder 연습
/*
원래 하루에 5시간씩 PS 연습을 하려고 했는데.. 장난이 아니고 말 그대로 시간이 없다. 자는 시간을 빼면 하루종일 뭔가 일을 하고 있는데, 해야 할 일의 큐가 점점 쌓인다... 수강 과목이 너무 많은가 ㅠㅠ
친구들과 Atcoder regular contest를 한 세트씩 풀어가려고 했는데, 이마저도 시간이 없어서 제대로 준비를 하지 못했다. 그래도 모임을 하니 나름의 소득이 있다. 시간이 없긴 하지만 계속 짬을 내서 공부를 해야겠다.

*/



AtCoder Regular Contest 095


C – Many Medians (9:42)
간단한 문제. 모든 원소에 대해 그 원소를 뺐을 때 중간값을 출력해주면 된다.
원소 갯수가 짝수라서 안그래도 쉬운 문제가 더 쉬워졌다.
솔루션은 sorting했을 때 앞 절반 원소는 n / 2 + 1번, 뒤 절반 원소는 n / 2번 원소가 답이다.
9분 42초나 걸린 이유는… 노트북을 산 뒤 처음 써봤는데 쉬프트, 방향키, end키가 이상한 곳에 있다..
적응하려면 상당한 시일이 걸릴 것 같다..


D - Binomial Coefficients (12:57)
항상 가장 큰 원소가 들어가야 최선의 선택이 된다는 것은 간단하게 알 수 있다.
따라서 가장 큰 원소와, 가장 큰 원소 / 2에 가까운 원소를 찾아서 골라주자.
고른 두 원소가 달라야 한다는 사실을 관과했다가 WA를 한 번 받았다.


E - Symmetric Grid (30:00 + 1:10:27)
* 숫자가 작을 때는 다 해보는 것도 훌륭한 방법이 될 수 있다

행, 열을 swap하는 operation을 반복하여, 중앙대칭(?)의 문자열을 만들 수 있는지 묻는 문제.
30분간 고민을 했는데 몇 가지 특징은 찾았지만 별다른 접근법을 생각하진 못했다. 2d array 넘나 어려운 것..
해답을 보니, 상당히 간결한 풀이가 존재했다. 바로 다 해보는것...

물론 다 해보는 것도 그리 쉽지는 않다.
핵심 아이디어는 행/열을 분리해서, 열에 대한 모든 조합을 다 해보고
각 조합마다 행만 바꾸어서 우리가 원하는 최종 결과를 얻을 수 있는지를 확인하면 된다. 이는 각 행을 reverse한 결과와 똑같은 행이 있는지를 체크하여, 쉽게 확인할 수 있다.
모든 열에 대한 조합을 다 해보는 것은 그리 만만하지 않은데, 우선 조합의 갯수가 12!개인데 이는 너무 큰 수이다. 몇 가지 특징을 확인하면, 결국 어떤 열 i가 어떤 열 j와 대칭 pair를 이루고 있는지만이 결과에 영향을 미치는 것을 알 수 있다. 조합 수는 11!!, 10000개 정도로 줄어든다.

이를 코드로 짜는 것 또한 전혀 쉽지 않다. 차분한 마음으로 코드를 작성하다 보면 AC를 받을 수 있을 것이다. 알고리즘 이해와 코드 짜는 시간이 1시간이 넘게 걸린 극악의 문제였다. 아마 대회 때 이런 문제를 맞닥드린다면... 아마 나는 눈물이 날 것 같다.

c.cpp

d.cpp

e.cpp

Atcoder Regular Contest 097
친구가 푼 부분이다. 문제 내용과 풀이법을 알고 풀어서 상대적으로 빨리 풀 수 있었다.


C - K-th Substring (8:05)
중복 제외 substring 중 k번째 수를 구하는 문제이다. k가 5 이하이므로 다 해보면 쉽게 풀 수 있다.
중복 검사는 set을 이용하면 굉장히 쉽고 코드도 간결하다.


D - Equals (10:08)
vim에서 복붙이 익숙하지가 않아서 조금 오래 걸렸다..

전형적인 disjoint-set 문제이다. 쿼리로 들어온 것을 모두 merge한 뒤, 인덱스와 인덱스번 원소가 같은 집합에 있는 것의 갯수를 세면 된다.

c.cpp

d.cpp

Atcoder Regular Contest 070
마찬가지로 친구가 푼 부분. 어려운 문제를 풀어야 실력이 오를텐데, 여유가 없다..


C - Go Home (6:23)
문제를 읽는 데 시간이 조금 걸렸다.
이번 ACM-ICPC 예선 A번 문제와 접근법이 완전히 동일하다. ACM-ICPC 문제가 더 어려우므로 관심가는 사람은 풀어보길.


D - No Need (6:21)
내 PS 인생 최고의 충격 중 하나..
김모 양이 아무 생각 없이(?) 그리디 알고리즘을 만들었는데 놀랍게도 맞았다. 해설지에는 $O(N^3)$ 풀이와, 그를 보완시킨 $O(N^2logN)$, $O(N^2)$ 풀이가 나와있는데 해설지에도 나와있지 않은 $O(NlogN)$ 풀이가 존재한다. 과제가 밀렸으니 나중에 써야겠다.

c.cpp

d.cpp