오늘 기분이 좀 안 좋았었는데 문제가 잘 풀려서 싹 나았다. +) 32일 스트릭 뱃지 달성 +) 세그트리 태그 티어 플래5 달성 냅색문제 문제 링크 기억에, 옛날에 못 풀고 끙끙댔던 것 같은데 오늘 풀어보니까 풀이가 바로 떠올랐고, 구현도 쉬웠다. 풀이 더보기 $N\le 30$이니까 meet in the middle을 써야 한다는 것이 보일 수 밖에 없다. $\lfloor N/2\rfloor$랑 $N-\lfloor N/2\rfloor$개로 각각 나눠서 모든 경우를 나열한 뒤에 이진 탐색으로 하나씩 확인해주면 된다. 구현도 간단해서 코드는 생략한다. 데이터 만들기 1 문제 링크 APIO 2013 기출이다. 최단경로를 입문하는 사람한테 반례에 대한 사고력을 높여줄 만한 문제들인 것 같다. 풀이. 더보기 간단..

공항 문제 링크 각 비행기를 도착하는 순서대로 남은 조건을 만족하는 게이트에 도킹시키는 문제이다. 물론 도킹 수가 최대가 되는 것이 목적이다. 풀이 더보기 게이트의 선택지는 $1\cdots g_i$이다. $g_i$가 큰 비행기들은 굳이 작은 게이트를 택함으로써 $g_i$가 작은 비행기들의 자리를 뺏을 이유가 없다. 따라서 $g_i$ 이하 중 가장 큰 게이트를 택하는 그리디 전략이 성립할 수 있다. 근데... 증명은... 어케하지..? Overplanting 문제 링크 jinhan814님 코드가 깔끔하길래 본계정으로 다시 풀었다. 풀이. 더보기 직사각형의 합집합의 넓이를 구하는 유형인데, $N$이 작다. 그냥 좌표압축 느낌으로 풀이하면 되는데, 구현이 중요하다. 코드 더보기 query, update을 밖으..

LCM 문제 링크 개인적으로 오랫동안 고민했던 문제이다. 거의 4번? 정도에 거쳐서 풀다 미뤘다를 반복했다. 풀이 더보기 $\mathrm{lcm}(x,y)=xy/\gcd(x,y)$인데, 분모가 유동적이니까 $\gcd(x,y)$를 결정했을 때 $xy$의 최솟값을 각각 구해주는 방식으로 접근하면 된다. 손으로는 자연스러운 접근인데, 이상하게 코드로 짤 생각을 못했다. $\gcd(a+n,b+n)|(b-a)(\mathrm{wlog}\ a\le b)$이라는 사실을 이용해 $b-a$의 약수들만 훑어주면 된다. 코드 더보기 $x|(b-a)$ 검사를 빼먹었는데 예제가 돌아가서 눈치를 못 채고 있었다. 그리고 $a=b$인 경우도 빼먹고 있었다. 점점 실력이 떨어지는 느낌이다 ㅋㅋㅋ 이런건 좀 그만 실수해!! #inclu..

살짝 호들갑이기는 한데, 어쨌든 블루를 달성했다. 며칠 '블루 가자!!' 이러면서 치는데 계속 못 가다가 간발의 차로 블루에 들어와서 더 기분이 좋았던 것 같다. 아무튼 목표는 퍼플이므로 다시 담담하게 버추얼을 돌리면서 레이팅을 올려야 한다. 그래서 대충 계획 같은 걸 세웠다: Codeforces Anytime 기준 1700을 달성한 뒤 코드포스 복귀하자. Upsolving 리스트 풀기, 26문제다. 대부분 Div.2 D 난이도, 1900~2000이다. = 대충 플4 난이도. 플4 많이 풀자! 완전 다른 얘기긴 한데 코포 찾다가 이 문제를 내가 리스트로 깔끔하게 풀었는데, 꼭 리스트여야 하는지, 그렇다면 왜? 혹은 다른 방법? 등을 정리해보자. interactive 문제에 익숙해지자.

리뷰 A는 평소처럼 살짝 늦지만 틀리지 않고 풀었다. B에서 말렸다. 일단, DP가 정해일 리는 없는데 DP 밖에 생각이 안 났다. WA 1 한 번 받고서 시간 지체하다가 제출했다. 에듀라서 다행이다. C는 계산이랑 케이스 나누는게 너무 고단해서 '망했다...' 싶었는데, 다들 힘들어하더라. $ \max_{1\le i\le n}h_i+1$로 만드는 경우를 빼먹고 있다가 극적으로 떠올리며 AC... D는 B보다도 아이디어가 쉬웠다. 일단, 문제에서 주어진 연산을 무엇을 사용해서 풀 수 있는지를 알고 있기 때문이다. 하지만 나는 그런 문제를 푼 적이 없어서 검색을 해서 코드를 하나씩 맞춰나갔다. 7초 남짓 남았을 때 $a_1,\ldots, a_{k-1}$에만 적용하는 방법을 그리디로 진행한 방법이랑 동일하게..

타일 밟기 문제 링크 좋은 문제다. 요약하자면 배열에 존재하는 각 등차수열들의 원소의 합 중 최대를 구하는 것이다. $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..