79brue의 PS 블로그

이번 주는 처음으로 다이아 문제가 나왔다. 일주일에 한 티어씩 올라가는 느낌이다. 이번 주에 일정이 많아서 많은 시간을 투자하지 못했는데, 중간에 스페셜 저지 오류도 나오는 등 다사다난한 마라톤이었다. 리롤 기록: 1회 (H)A. Undercut구현 문제이다. 문제에 나온 대로 짜면 된다.#include using namespace std;typedef long long ll;int n;int A[22], B[22];int main(){ while(true){ scanf("%d", &n); if(!n) break; for(int i=1; iB. Expansion Order현재 접근할 수 있는 역의 목록을 배열로 관리하자. $chk[x]$는 현재 역 $x$에 접근..

인터랙티브 문제와 투스텝 문제 몇 개를 풀어보았다.BOJ 31975. Staring Contest만점을 받기 위해서는 $q \le n + 25$회 이내에 문제를 해결해야 한다. 데이터가 사전에 결정되어 있고 제한이 애매하므로 무작위화 알고리즘을 고려해볼 수 있다. 어떤 사람 $s$를 정하고, 이 사람과 다른 사람들에 대한 쿼리를 계속 날린다. 날리다가 이미 들어온 값 $v$가 또 들어오는 시점이 있을 것이다. 두 사람의 실력이 다르므로 이 값은 사람 $s$의 실력이라고 생각할 수 있을 것이다. 즉, 사람 $s$의 실력을 $v$로 고정할 수 있다. 또한 앞에서 쿼리를 날렸을 때 $v$보다 작은 값이 들어온 경우 그 값들을 해당 사람들의 실력으로 확정할 수 있을 것이다. 이제 $v$라는 결과가 나온 두 사람..

이번에도 전 주에 비해 큰 난이도 상승폭을 볼 수 있다. 플래티넘이 5문제가 되었고 P1 문제가 나오기 시작했다. 한 문제를 풀지 못해서 처음으로 리롤을 하기도 했다. 빠르면 다음 주에 다이아 문제를 만날 수도 있을 것 같다. 리롤 기록: 1회 (H)A. Calculate!어떤 수에 $B$를 두 번 XOR하면 원래의 수가 된다. $(A \oplus B) \oplus B = A \oplus (B \oplus B) = 0$이기 때문이다. 따라서 $C$가 짝수이면 답은 $A$이고, $C$가 홀수이면 답은 $A \oplus B$가 된다. $C$의 범위가 크므로 문자열로 입력받아야 한다.#include using namespace std;typedef long long ll;int a, b; string s;in..

지난 주 마라톤이 끝나고 난이도 변동폭을 크게 설정했더니 드디어 난이도가 눈에 띄게 올라갔다. 최고 난이도는 P3에서 P2로 상승했다. 중간에 F랑 G라는 지뢰가 끼어 있어서 힘들었다. F는 $N=30000$인데 제곱이 뚫리는 문제고 (나는 $O(N \log^2 N) $ 풀이로 풀었는데 최소 다이아라고 생각한다), G는 APIO 2013의 악명 높은 Taskauthor 문제 중 하나였다. A. Rank Order두 순위 각각에 대한 등수표를 구한 뒤, 앞에서부터 차례로 비교해 처음으로 달라지는 지점을 찾으면 된다. 등수표를 구하는 것은 수열 $[1, 2, \cdots, n]$을 정렬하는데, 정렬 기준을 $A_i > A_j$일 때 $i#include using namespace std;typedef lon..

문제 링크 엄청 유명한 수학 루비 문제인데, 난 수학에 자신이 없어서 딱히 건드려 본 적이 없었다. 오늘따라 루비를 풀어보고 싶어서 잡기 시작했다. 엄밀한 증명이나 풀이 위주로 적는다기보다는 생각의 흐름 위주로 기록을 남겨 보려고 한다.예제 분석일단 문제의 풀이에 대한 감이 전혀 잡히지 않아서 예제를 가지고 놀아 봤다. 간단한 랜덤화 시뮬레이션 코드를 짜서 시행의 선택에 따라 어떤 결과가 나오는지를 알아보았다. 다양한 방법으로 시행을 해 본 결과, 다음과 같은 두 가지 추측을 하게 되었다.여러 가능한 시행 중 어떤 것을 선택하더라도, 모든 수를 $0$ 이상으로 만드는 데 필요한 시행 횟수가 같다.어떤 방법으로 시행을 완성하더라도 최종 상태가 동일하다.이 관찰을 통해 어떤 수열 $A$에 대해 이 문제의 답..

BOJ 17670. 난난을 $N$조각으로 잘랐을 때, 마지막 난을 누가 가져가야 할 지 생각해 보자. 각 사람별로, 왼쪽부터 $P_i$만큼의 난을 먹었을 때 전체 행복도의 $\frac{i}{N}$만큼을 얻게 되는 $P_i$를 구하자. 이때 $P_{N-1}$이 가장 큰 사람에게 맨 오른쪽 조각을 $P_{N-1}$부터 잘라서 주면, 마지막 사람은 $\frac{1}{N}$만큼의 행복도를 얻고, 남은 사람들 모두 남은 조각들로 최소 $\frac{N-1}{N}$의 행복도를 얻을 수 있는 상태가 된다. 이제 여기서 다음 사람은 아직 난을 받지 못한 사람 중 $P_{N-2}$가 가장 큰 사람에게 주고, 그 다음 사람은 $P_{N-3}$이 가장 큰 사람에게 주고, 이를 반복하면 모든 사람에게 항상 조건을 만족하도록 난..

세 번째 마라톤이다. 앞 두 마라톤을 전부 풀었지만 문제의 난이도는 거의 비슷한 것 같다. P3보다 높은 난이도가 나오기를 기다리고 있는데, 아직은 때가 아닌 것 같다.A. Поиски다음 세 가지 케이스로 나눌 수 있다.$x>0$: 문자열에 L과 R이 둘 다 존재하거나, R의 개수가 $x$ 이하면 가능하다.$x L과 R이 둘 다 존재하거나, L의 개수가 $-x$ 이하면 가능하다.$x=0$: 문자열에 L과 R이 둘 다 존재하면 가능하다.#include using namespace std;typedef long long ll;string str;int lc, rc;int main(){ cin >> str; for(char c: str){ if(c=='L') lc++; e..

두 번째 마라톤이다. 1주차 마라톤을 올솔했지만 2주차 문제들의 난이도 역시 거의 비슷한 (조금 더 낮은) 분포로 나왔다. 어째서인지 A번 문제는 나오지 않았는데, 다른 분들이 주신 정보에 의하면 해당 난이도대에 추천할 만한 문제가 없어서 일어나는 현상이라고 한다. 문제가 하나 적었음에도 E번과 H번을 잘못 읽어서 자체 하드 모드에 빠졌다… E는 불편도를 최댓값 대신 합으로 생각해서 30분 이상 고민하다가 결국 문제를 다시 읽고 틀렸음을 파악했다. H번은 선장의 배가 무조건 "중심으로 align된다"를 "align된다"로 읽어서 접근 방향 자체를 완전히 말려 (사실 이건 실력 이슈가 더 큰 것 같긴 하다) 역시 오랜 시간을 허비했다. 아직 solved.ac 웹페이지가 안 돌아와서 별조각은 못 받았다. 받..