공항 문제 링크 각 비행기를 도착하는 순서대로 남은 조건을 만족하는 게이트에 도킹시키는 문제이다. 물론 도킹 수가 최대가 되는 것이 목적이다. 풀이 더보기 게이트의 선택지는 $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] !..
별건 아니고... 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$을 ..
A. Luntik and Concerts B. Luntik and Subsequences C. Grandma Capa Knits a Scarf D. Vupsen, Pupsen and 0 E. Pchelyonok and Segments F1. Korney Korneevich and XOR (easy version) A. Luntik and Concerts 번역/요약: \(a\)개의 \(1\)분짜리 노래, \(b\)개의 \(2\)분짜리 노래, \(c\)개의 \(3\)분짜리 노래가 있다. 공연 두 번에 나눠서 모든 노래를 부를 것이다. 두 공연의 공연 시간 차이가 최소가 되게 하고 싶다. 시간 차이의 최솟값을 구하라. 풀이: \(2\mid a+b\) 라면 \(0\), \(2\nmid a+b\)라면 \(1\)이..
