타일 밟기 문제 링크 좋은 문제다. 요약하자면 배열에 존재하는 각 등차수열들의 원소의 합 중 최대를 구하는 것이다. $N\le 3000$이고 원소들은 $10^6$ 이하이다. 풀이 & 코드 Solution 1 더보기 DP + 이진탐색 #include using namespace std; using ll = long long; #define REP(i,a,b) for (auto i = (a); i sync_with_stdio(0); cin >> n; REP(i,1,n) cin >> a[i]; ll answer = 0; REP(i,1,n) REP(j,1,i-1) { dp[i][j] = a[i]+a[j]; int k = lower_bound(a+1,a+j,2*a[j]-a[i])-a; if (a[i]+a[k] !..
1시간 차에 3번 풀고 2시간 차에 1번이랑 2번 섭태 풀었다. 3시간 반 차까지 2번 풀태를 고민했지만 별 진전이 없어서 승급 컷도 넘겼겠다, 버리고 튀었다. 2시간 만에 2.5문제 풀었다는 것만 봐도, 난이도가 근 3개 contest보다 쉬웠다. Visits $1\cdots N$로 이름 붙여진 Bessie의 친구들은 각자 자신의 농장을 소유하고 있다. 각 소 $i$는 소 $a_i(\neq i)$네 농장에 방문하고 싶다. $1\cdots N$의 순열 $(p_1,p_2,\cdots,p_N)$에 대해 다음을 시행한다: $a_{p_i}$가 이미 농장을 떠났다면, $p_i$는 자신의 농장에 남는다. 그렇지 않으면, $p_i$는 자신의 농장을 떠나 $a_{p_i}$의 농장에 방문한다. 이러한 방문은 즐거워서 소..
이 글은 암호학 교육 및 온라인 저지를 제공하는 사이트 cryptohack.org의 입문 코스인 "Introduction to Cryptohack"의 요약 과 번역 및 간단한 역자의 풀이를 적은 글입니다. Overview 암호학(Cryptography)에 입문을 돕습니다. 이 장에서는 암호학에서 흔히 쓰이는 데이터 타입간의 인코딩과 디코딩을 배웁니다. 그 뒤, 대칭키 암호 시스템(Symmetric cryptosystem)의 중심에 있는 배타적 논리합(eXclusive OR; XOR) 연산을 쉽게 받아들일 것입니다. 마지막으로, 장의 끝에는 재밌는 XOR 퍼즐로 실력을 테스트합니다. Introduction - Challenges Finding Flags 문제를 해결하려면 'Flag'를 찾아야 합니다. 이러..
문제 아카이브 Hello, Postman ROX 푼 날짜: 2022년 3월 20일 풀이 더보기 처음 푼 문제라서 뭐가 결과인지 파악을 못했다. 풀다가 모르겠어서 Welcome의 문제 2개를 풀었더니 Flag는 공통적으로 H4CGM{...} 형식을 띤다는 것을 알아냈다. 그래서 result에 저게 나오면 되겠다 싶었다. 근데 Message 문자열? 리스트?에 나오는게 뭐지 싶어서 print(type(Message[0])) 해보니까 정수형이라고 하더라. 그리고 이것저것 만져보니까 ord가 chr$^{-1}$이더라. 그래서 $\text{result}[0] = chr(\text{Message}[0] \oplus ord(\text{known_plaintext}[0]))$를 정리하니까 $chr(ord(\text{r..
별건 아니고... CSA에서 OI 세트가 뭐가 있나 뒤져봤었는데, 이런 것들이 있었다. 루마니아 문제는 들어본 적이 없어서 솔직히 꺼려진다. IOI 2016 Training Round IOI 2016 Training Round #1 IOI 2016 Training Round #2 IOI 2016 Training Round #3 IOI 2016 Training Round #4 IOI 2016 Training Round #5 Romanian IOI 2017 Selection Romanian IOI 2017 Selection #1 Romanian IOI 2017 Selection #2 Romanian IOI 2017 Selection #3 Romanian IOI 2017 Selection #4 Romanian..
밥 먹기 문제 링크 7577번: 탐사의 마이너 버전이라고 할 수 있다. 필자는 '탐사'를 자력으로 못 풀었지만, 어쨌든 '탐사'에 사용되는 방법을 배워서 이 문제를 수월하게 풀 수 있었다. 어쩌면 '밥 먹기'를 푼 뒤 '탐사'를 시도하면 풀 수 있을 것 같기도 하다. 풀이 더보기 상당히 어려운 문제이고, 아이디어성 문제이다. 문제에서 요구하는 것을 간단하게 바꾸면 '연립 부등식의 해를 결정해라' 정도의 얘기가 된다. 완전한 결정을 의미하는 것은 아니지만 아무튼. 신기하게도 떨어지는 거리의 범위가 큰 것이 문제의 힌트가 된다. '탐사'의 경우는 범위가 적어서 오히려 접근이 어려웠다. 따라서 DP의 가능성은 적다. $1\cdots N$을 쭉 나열하고 범위를 표시하면서 파악하면 감을 잡기 쉽다. $D_1$을 ..
계산기하의 기본 도구들을 소개합니다. 마음가짐 기하 문제는 예외 처리가 적고, 구현이 쉬운 형태의 표현 방법 및 풀이를 이용해야 한다. 그리고 실수 좌표보다는 정수 좌표를 이용해야 한다. 그래서 이 글은 실수를 적극적으로 이용하는 문제는 논외로 한다. 그래서 이중적 의미로 "실수 없는 계산기하"이다. 템플릿 기하를 여행하는 Competitive Programmer를 위한 안내서에서 소개된 편리한 표현 방법을 따른다. 위 글에서 참고한 예외 사항이다: 점이 [1, 2개 / 일직선상 / 위에 존재] 직선, 선분이 [평행 / 일직선상] 중복 존재 점과 벡터 complex을 사용한다. Unspecified Behavior임을 감안하여 몇몇 함수들을 재정의한다. Unspecified Behavior임에도 사용하는..
책 "알고리즘 산책"에서 다음과 같은 내용을 보았다. ...하지만 재귀 호출을 완전히 없애서 함수 호출에 따르는 오버헤드를 피해 보자. 정의 2.1 모든 형식 매개변수를 각각에 상응하는 인자로 사용하는 꼬리 재귀 호출을 순 꼬리 재귀 호출(strictly tail-recursive)이라고 한다. 재귀 호출을 하기 전에 변수의 값을 미리 설정해 주면 순 꼬리 재귀 호출로 고칠 수 있다. int mult_acc3(int r, int n, int a) { if (odd(n)) { r = r+a; if (n == 1) return r; } n = half(n); a = a+a; return mult_acc3(r,n,a); } 이제 꼬리 재귀 호출을 while(true) 구문으로 바꾸기만 하면 손쉽게 반복문 형..
