79brue의 PS 블로그

11주간의 마라톤 끝에 드디어 450km를 찍었다. 특별한 동기가 없는 한 더 이상 마라톤을 지속하지는 않을 것 같다.앞으로 마라톤을 풀지 않으니 점점 난이도가 떨어질 텐데, 난이도 변경폭을 최소로 바꿔 놓으려고 한다. A. Расписание기초적인 그리디 문제로, 가장 작은 수부터 차례대로 $1$부터 수를 붙여 주면 된다. 나는 $O(n^2)$에 풀었고, 그 이하의 시간 복잡도로도 풀 수 있다.#include using namespace std;typedef long long ll;int n;int arr[102];int ans[102];int main(){ scanf("%d", &n); for(int i=1; iB. Crazy tea party원탁에 있는 $n$개의 수들을 최소 횟수의 (..

랜덤 마라톤은 계속 나를 한계로 몰아붙이는 것 같다. 아무래도 랜덤 문제가 뽑히다 보니 실력 향상을 크게 느끼지는 못하고 있고, 그나마 승부욕 때문에 계속 푸는 것 같다. 이제는 재미로 문제를 푼다기보다 압박처럼 느껴지는 부분이 더 많은데, 450km를 달성하면 아마 그만둘 것 같다. 리롤 기록: 1회(B, E, H), 2회(H), 3회(H)A. Fair and Square (Small)나이브를 돌려 보면 이 성질을 만족하는 수가 거의 없다. 리스트를 precomputation해 두면 Large1 문제까지도 쉽게 풀 수 있다. precomputation으로 풀었기 때문에 정답 코드를 첨부하지 않는다.B. Kind of a Blur문제를 잘 읽어 보면 단순히 연립방정식을 풀면 되는 문제라는 것을 알 수 있..

점점 다이아가 많아지고 있다. 아무래도 몇 주 정도만 더 하게 될 것 같은데, 얼마 뒤에 루비가 나올 수도 있을 것 같다.리롤 기록: 1회(F, H), 2회(H)A. Make America Grade Again역시 문제에 적힌 것을 그대로 구현하면 되는 문제이다.l,h,p,e,n=map(int,input().split())dct = {'l': [0, 0], 'h': [0, 0], 'p': [0, 0], 'e': [0, 0]}for i in range(n): s = list(input().split()) s[0] = s[0].lower() r = s[-1].split('/') dct[s[0][0]][0] += int(r[0]) dct[s[0][0]][1] += int(r[1])a..

현황은 아래와 같다.리롤 기록: 1회(G), 2회(G)A. 6174문제에 나온 것을 그대로 구현하면 된다.#include using namespace std;typedef long long ll;int t;int n;int main(){ scanf("%d", &t); while(t--){ scanf("%d", &n); int ans = 0; while(n != 6174){ string s = to_string(n); sort(s.begin(), s.end()); n = -atoi(s.c_str()); reverse(s.begin(), s.end()); n +=..

문제를 풀면서 정리한 생각 노트이다.D서브태스크가 갑자기 많아졌다. 아무래도 ABC 풀고 D/E 긁기로 본선 컷을 자르겠다는 게 의도 같아 보인다. 한편으로는 제출 횟수가 10회 제한이 걸려 있는데 섭테를 6개 주는 것은 조금 잔인하다는 생각도 들었다.문제 이해 (+Subtask 4)초기에 $a$의 값이 모두 다르다고 가정하자. $a$는 여러 연산을 통해 그 값이 바뀐다. 이때 $b_i$를 (몇 회의 연산 이후) 현재 $a_i$가 초기의 $a_j$와 같은 $j$값으로 정의하자. 이때 어떤 연산을 시행한 이후 $b[l \dots r]$은 $l \le i \le r$인 기존의 $b[i]$ 값 중 하나로 전부 바뀌게 된다. 예를 들어,$a = [1, 4, 2, 3]$이었고, 초기에 정의상 $b=[1, 2, 3..

이번 주는 처음으로 브론즈 문제가 빠지고 다이아 문제가 두 개가 나왔다. 이번 주는 문제풀이에 쓸 수 있는 시간이 매우 한정되어 있었기 때문에 문제 풀이가 바로 보이지 않으면 리롤을 했다. 결국 마감 6시간 전에 겨우 완주에 성공했다. 리롤 기록: 1회(D, F, H), 2회(F)A. COMPRESS상당히 테크닉적인 문제이고, 실버 문제임에도 구현 아이디어가 쉽지 않다. $C$에서 남길 자릿수를 $k$자리라고 하자. 그러면 $R$은 $C$를 $10^k$로 나눈 나머지가 된다. $K = 10^k$라고 하자. 만약 $F \bmod K #include using namespace std;typedef long long ll;ll a, b;int main(){ while(scanf("%lld-%lld", ..

이번 주는 처음으로 다이아 문제가 나왔다. 일주일에 한 티어씩 올라가는 느낌이다. 이번 주에 일정이 많아서 많은 시간을 투자하지 못했는데, 중간에 스페셜 저지 오류도 나오는 등 다사다난한 마라톤이었다. 리롤 기록: 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$라는 결과가 나온 두 사람..