26.04.23 ~ 26.05.05 PS

BOJ가 서비스 종료를 하게 되었다.

solved.ac를 주축으로 OJ들을 연결하려는 움직임이 보이고, 난이도 기여 시스템은 남게 될 것 같다.

BOJ에서만 풀 수 있던 쏠쏠한 문제들을 더 이상 채점할 수 없다는 사실이 안타깝다.

전역하고 PS를 다시 빡세게 할 때가 되면, 전과 같은 좋은 인프라가 남아있었으면 좋겠다.

 

IOI 2019 — Rectangles

View problem - Rectangles (IOI19_rect) :: oj.uz

재밌는 문제다.

일단 좋은 직사각형의 개수가 sparse하다는 관찰을 할 수 있다.

row - col을 독립적으로 다루고 싶다는 생각도 할 수 있다.

$1\times N$에 대해서, 좋은 직사각형이 $O(N)$개라는 것도 알 수 있다.

 

그런데 여기서 풀이를 찾는 것이 굉장히 어렵다.

 

착안점은 $1\times N$에 대해서, 좋은 직사각형이 $O(N)$개라는 것을 거꾸로 뒤집어 생각한다는 것이다.

모든 셀에 대해서, 그 셀을 최댓값으로 가지게 하는 후보 구간은 정확히 하나로 특정된다는 일대일 대응 성질이 중요하다.

 

생각해보면 당연하다!

 

그런데, 이 점으로 인해, 각 셀에 대해서 좋은 직사각형 후보도 당연히 정확히 하나로 특정된다는 것을 알 수 있다.

그러면, $O(NM)$개의 직사각형에 대해 결정 문제를 해결하는 것으로 문제가 바뀌게 된다.

 

세로 구간들, 가로 구간들의 개수 총합이 각각 $O(NM)$이 된 순간,

결정 문제를 해결하는 것은 굉장히 단순해진다. vector<int> rows[L][R] 꼴로 리스트를 만들고 이진탐색으로 확인하면 끝이다. 공간 복잡도가 amortized $O(NM)$이기 때문에...

 

IOI 2018 — Werewolf

View problem - Werewolf (IOI18_werewolf) :: oj.uz

기가 막힌 문제다. 이런 문제 더 많이 누가 찾아서 풀라고 알려주면 좋겠다.

Linear Graph일 때 subtask는 각 component가 정확히 연속적인 구간으로 나와주기 때문에, 쿼리에 쉽게 응답할 수 있다.

 

이 연속적인 구간의 특성을 써먹고 싶다.

그래서 kruskal reconstruction tree를 구성한 뒤, dfs ordering으로 구간이 되게 펼쳐준다...!!

 

그러면 ordering이 다른 두 구간에 대해서 겹치는지 파악하는 문제가 되는데, 이걸 좌표축 두 개로 분리하면 직사각형 2D 쿼리로 환원된다.

 

따라서 세그먼트 트리 스위핑으로 잘 처리하면 문제가 해결된다.

 

Codeforces #1095 — Mental Monumental (Hard Version)

Problem - E - Codeforces

Easy Version을 빨리 풀었는데, 그냥 Hard Version도 별로 안 어려울 것 같아서 잡았다.

디버깅을 오래 했는데, q(l,r) 호출에서 q(l,min(n,r)) 호출을 안 해서 multi TC 데이터에서 WA가 났다.

dirt가 어디서 생겼는가 찾느라 오래 씨름했는데... 6개월간 군대에 있어서 그런지 구현력이 낮아진 것 같아 서러웠다.

Easy Version에서 얻을 수 있는 철학:

• 각 원소 $x$는 $\left [0,\lfloor \frac{x+1}2 \rfloor - 1 \right ] \cup \{x\}$ 중 하나로 변경할 수 있다.
• 두 부분을 각각 '작은구간', '큰값' 이라고 명명하겠다.

 

$[0,mex-1]$은 이미 확보한 구간이다.

모든 수는 기본적으로 '작은구간' 형태로 차곡차곡 사용한다.

확보한 구간 내부로 '큰값'이 대응될 수 있을 때, '작은구간'을 버리고 '큰값'으로 올라타며, 그 값을 구간이 아닌 specific한 값으로 fix한다.

 

'작은구간'이 커버하는 범위 자체가 monotone하기 때문에 segtree로 잘 처리할 수 있다.

'큰값'으로 올려주는 부분은 priority queue 등으로 처리해주면 되겠다.

 

Codeforces #1095 — Reserved Reversals

Problem - D - Codeforces

기억나는 최근 코포 D 중에 가장 괜찮은 문제였던 것 같다.

홀수는 홀수끼리, 짝수는 짝수끼리 정렬된 상태로 몰아줄 수 있다면, 전부가 정렬된 상태가 되도록 합병하는 것이 가능하다.

 

두 짝수가 inversion 관계를 이룬다고 할 때, 이걸 풀어주려면 반드시 두 짝수보다 크거나, 두 짝수보다 작은 홀수가 필요하다. 그렇지 않다면 두 짝수를 포함하는 구간을 잡아 뒤집는 것이 불가능하다. 다른 방법으로는 inversion을 풀어줄 수 없다.

 

만약 모든 짝수 inversion 쌍 사이에 그러한 홀수가 항상 존재하고, 홀짝 반대에서도 똑같이 그러하다면 모든 inversion을 풀어줄 수 있는 필요조건이 마련된다.

 

인접한 두 짝수 inversion을, 둘을 제외한 배열 전체가 훼손되지 않도록 둘의 자리만 swap해주는 것이 가능하다.

배열 전체에서 두 짝수의 inversion을 매개해 줄 홀수를 찾는다. 그리고, 그 매개홀수를 기준으로 왼쪽에 있는 모든 홀수는 인접한 두 짝수보다 왼쪽으로 밀어준다. (홀수들은 순서를 유지한 채 짝수들을 관통하는 것이 가능) 반대로, 매개홀수 오른쪽에 있는 모든 홀수들은 오른쪽으로 밀어준다. 매개홀수는 두 짝수의 사이에 위치시킨다. 그 다음 이 세 수를 뒤집은 뒤, 모든 홀수를 제자리로 되돌려 놓는다. 이러한 방법으로 배열의 훼손 없이 원하는 인접 짝수 inversion을 뒤집는 것이 가능함을 확인했다.

 

따라서, 짝수들의 순서가 정렬되고, 홀수들의 순서가 정렬된 상태를 만든 뒤, 홀수 전체를 왼쪽이던, 오른쪽이던 싹 밀어놓으면, 풀이의 시작해서 말했던 상태를 세팅할 수 있다. 합병하는 것은 하나하나 자리를 찾아가면 되므로 당연히 가능하다.

 

끝. 신기한 문제였다.

 

USACO 25/26 Third Platinum — Min Max Subarrays II

Min Max Subarrays II - Problem - QOJ.ac

지문이 짧길래 좋아서 잡았다.

어디서 본 적 있는 것 같은데.... 하고 고민하다가 https://mathsciforstudent.tistory.com/429 "흔한 수열 문제" 였다는 걸 알아차렸다.

근데 흔한 수열 문제의 상위 버전이면 해결할 수 없는 제한인데.... 하고 고민하다가, 아무래도 흔한 수열 문제의 풀이 상 모든 원소가 distinct해야 한다는 조건이 붙었겠군 하고 생각했다. (BOJ가 사라진 관계로 제한조건을 역추적했다)

생각해보니, distinct가 안 붙으면 그렇게 어려울 이유가 없다는 생각이 들었고 조금 고민했는데,

일단 모든 $a_i$가 될 값의 범위를 $[L_i, R_i]$로 줄이는 것 까지는 어려움이 없다는 것을 알았고...

 

경계값을 택하지 않을 이유가 없다는 것에 착안해, 양면성을 이용한 그래프 모델링을 떠올렸다. (like 최고인 대장장이 토르비욘)

https://mathsciforstudent.tistory.com/336

즉, $L_i$와 $R_i$를 잇는 간선을 만드는 식으로 그래프를 construct한다는 것.

 

모든 정점의 outdegree가 1 이상이 되도록 무향 간선들에 방향을 매기는 작업을 성공적으로 수행하면 문제가 해결된다는 것을 확인했다.

 

하지만 그래프에 multi-edge가 존재하고, $L_i=-\infty$ 또는 $R_i=+\infty$가 되는 케이스를 효과적으로 처리함에 어려움이 있어 구현은 실패했다.

 

아무래도 싸지방 코딩은 어려운 면이 있다.

 

USACO 25/26 Third Platinum — All Pairs Shortest Paths

All Pairs Shortest Paths - Problem - QOJ.ac

 

생각할 거리가 많고 재밌을 것 같아서 잡았다.

그러나, 풀이가 너무 단순하면서 코딩은 너무 case work인 것 같아서 official solution을 확인했더니 그 풀이가 맞았다.

USACO Platinum에 이런 문제가 나온다니 굉장히 의외고 당황스럽다.

입풀이:

삼각형 내부를 3등분하는 간선들은 제쳐두고 커다란 거리부터 측정한다.

그러면 $x+y=k$꼴, $y=k$꼴, $x=k$꼴 3가지 좌표축을 찾을 수 있다.

건너가야 하는 좌표축 라인의 수를 따서 1차적으로 rough한 거리 요소를 찾을 수 있다.

거기에 $\times 2 -1$을 해주면, 3등분하는 간선들이 중간에 나오는 걸 세어줄 수 있다.

마지막으로, 양끝에 붙는 3등분하는 간선들은, 삼각형의 긴 변의 연장선을 기준으로 갈라진 두 평면 중 어디로 가야 하는지로 나누어 계산할 수 있다.