문제 아카이브 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) 구문으로 바꾸기만 하면 손쉽게 반복문 형..
Searching for Soulmates $a_i$를 $b_i$로 바꾸기 위한 연산의 최소 횟수를 구하라. 연산에는 3가지 종류가 있다. $a_i\leftarrow a_i \times 2$ $a_i\leftarrow a_i / 2\ (\text{when}\ 2|a_i)$ $a_i\leftarrow a_i+1$ $1\le N\le 10, 1\le a_i,b_i\le 10^{18}$ #include #define REP(i,a,b) for (auto i = (a); i k) >= a) { ret = min(ret, (b>>k)-a+k+__builtin_popcountll(b)-__builtin_popcountll((b>>k)> n; REP(i,1,n) cin >> p[i].first >> p[i].seco..
*중요: 궁금한건 댓글로 남겨주세요!* int는 32개의 비트의 조합으로 표현된다. signed int의 경우 첫 비트가 부호를 나타내어 $[-2^{31},2^{31})$의 정수를 표현하고, unsigned int의 경우 첫 비트도 일반적인 비트로 사용되어 $[0,2^{32})$의 정수를 표현한다. * 만약 10진수를 2진수로 출력하고 싶다면 cout = 0; --k) cout >k&1); 집합 집합의 표현 정수 $x\in [-2^{31},2^{31})$와 정수 집합 $U=[0,32)$에 대해, $\displaystyle X:=\{k\in U|x\&2^k\neq 0\}$이다. 편의상 $f(x)=X$라고 표기하겠다. 또, $f^{-1}(X)=x$라 하자. 여러가지 집합 $f(0)=\varnothing$, ..
