PS 일기 (2월 4주차)

안녕하세요.

벌써 2주째 Pseudo-다이아스트릭을 이어나가고 있습니다.
지금까지 9문제 해결했고, 풀_문제 셋에는 5개가 남아 있습니다.

서론

저번 주에 이월된 문제는
19730번. Sightseeing Tour
28320번. Flip it and Stick it
2209번. 버스 터미널
입니다.
이 중 19730번, 28320번을 해결했습니다.
2209번은 유의미해 보이는 관찰을 했고 풀이를 내서 구현했지만 반례만 확인하고 WA를 받았습니다.

19730번. Sightseeing Tour

월요일에 태그를 깠더니 "2-sat"과 "제곱근 분할법"이 나왔습니다.
2-sat은 어떻게 활용하는지 바로 나왔지만, 제곱근 분할법은 어디에 써야 하는지 모호했습니다.

금요일에 우연히 Leejseo님의 블로그를 보게 되었고 2-sat의 응용을 몇 개 배웠습니다.
그 중 하나를 이 문제에 적용할 수 있었고, 토요일에 구현해서 AC를 받았습니다.

https://leejseo.com/2-sat-applications/

2-SAT 및 그의 응용

여기서 "n개 중 하나만 참인 경우를 O(n)개의 식으로 표현하기"를 배웠습니다.
원래 티어는 D4였지만, 이 문제와 아주 비슷한 19703번이 D5인것을 확인했고 D5로 기여했습니다.
19703번도 이내 구현해서 AC를 받았고 레이팅을 쌀먹했습니다.

28320번. Flip it and Stick it

월요일에 태그를 깠을 때 "애드 혹"과 "많은 조건 분기"가 나왔습니다.
|T| = 1, 2, 3인 경우로 나눠서 구현했는데, 수요일까지 계속 WA를 받았습니다.
목요일에 QOJ에서 해당 문제를 찾아서 제출했는데 백준에는 올라와 있지 않은 서브태스크가 존재한다는 사실을 관찰했습니다.
서브태스크별로 몇 점을 받았는지 보여주기 때문에, 어떤 부분에서 틀렸는지 확인할 수 있었고, 곧 수정해서 AC를 받았습니다.
OI에 이런 구현 원툴 문제가 나온다는 것이 마음에 들지 않아서 문제에 비추를 주고 왔습니다.

풀이는 굳이 서술하지 않겠습니다.

원래 티어는 D5였지만, 서브태스크가 있을 때 P2 / 없을 때 D4라는 의견을 남기고 D4로 기여했습니다.

새로 추가된 문제들

28478번. Ones (미해결)

요일에 28478번. Ones를 뽑았습니다.
이분 탐색으로 해야 할 것 같았지만, 디테일을 떠올리기는 쉽지 않았습니다.
수요일~목요일 사이에 태그를 깠던 걸로 기억합니다. "이분 탐색", "무작위화"가 있었습니다.
아직까지 유의미한 관찰은 하지 못했고, 풀이를 까거나 드랍한다는 생각이 조금씩 들었습니다.

25437번. Connected Towns (AC)

화요일에 25437번. Connected Towns를 뽑았습니다.
화요일 하루를 모두 투자했지만 쿼리를 O(n^2)번 미만으로 사용하는 풀이는 내지 못했습니다.
수요일 오전에 Q = 5N짜리 풀이를 냈고, 오후에 4N으로 줄여서 AC를 받았습니다.

Q = 5N (71.53점)

모든 정점의 쌍 (i,j)에 대해서 "i의 outdegree < 2, j의 outdegree < 2이면 (i,j)를 잇는 간선을 확인한다"를 적용해 줍니다.
모든 (i,j)를 순회했으면, outdegree < 2인 정점들에 대해서 O(N)번 쿼리를 날려 outdegree가 진짜 2인지 확인합니다.
첫 번째 줄은 2N번 이하의 쿼리로 수행할 수 있습니다.

최악의 경우, 세 정점 i,j,k가 존재하여 i -> j, j -> k, k -> i이고 다른 모든 정점들의 outdegree가 2일 수 있습니다. 이 때 3N번 가량의 쿼리를 날려랴 합니다.
네 개 이상의 정점의 outdegree가 2 미만인 경우는 존재하지 않습니다.

pf) 4개의 정점이 있으면 이 정점들을 잇는 간선은 6개이고, 비둘기집의 원리에 의해서 4개의 정점을 살펴보면 하나의 정점은 outdegree가 2여야 합니다.
정점이 4개 초과여도 마찬가지입니다.

따라서 최대 5N번의 쿼리를 사용하면 해결할 수 있습니다.

Q = 4N (100점)

N <= 100이면, 만점을 받기 위한 쿼리의 제한이 8000개이므로 O(n^2)으로 풀립니다.

N > 100이면, 5N짜리 풀이에서 outdegree 제한 2를 1로 바꿔서 돌려줄 것입니다.
그러면 현재 outdegree가 0인 점이 하나 있는데, N번의 쿼리를 날려서 그 점의 최종 outdegree를 구해 줍니다.
위 작업을 2번 반복하면 4N번의 쿼리로 해결할 수 있습니다. 만약 WA를 받는다면, 탐색 순서를 바꿔주는 방법으로 해결할 수 있습니다.

자세한 증명은 하지 않았고, Proof by AC로 대체하였습니다.

기여는 문제 난이도와 같은 D5로 했습니다.

35341번. 균형잡힌 수열 (PAC)

수요일에 35341번. 균형잡힌 수열을 뽑았습니다.
몇 가지 관찰을 하고 만점 풀이를 냈다고 생각했으나, 아직 AC를 받지는 못했습니다.
관찰 1) 모든 균형잡힌 수열의 길이는 2^n - 1 (n은 양의 정수)이다.
관찰 2) 관찰 1에 의해서, 길이 n인 수열이 가질 수 있는 균형잡힌 수열의 최대 개수는 O(n log n)이다.
관찰 3) 수열의 어떤 인덱스를 포함하는 균형잡힌 수열의 최대 개수는 O(log n)이다.

Q <= 10 (52점)

모든 초기화와 쿼리에 대해서 길이 1, 길이 3, 길이 7, ...의 균형잡힌 수열을 순서대로 찾아 줍니다.
O(NQ log N)에 해결할 수 있습니다.

Q <= 100,000 (100점)

아직 AC를 받지 못했으므로 Proposition일 뿐입니다.
각 쿼리에 대해서 a[p] = v로 바꿔주는 쿼리가 있다면 p를 child로 가지는 모든 길이 3의 부분수열들이 균형잡힌 수열인지 판단합니다.
쿼리 전과 결과가 바뀌었으면 그 수열을 child로 가지는 모든 길이 7의 부분수열이 균형잡힌 수열인지 판단합니다...
길이가 2^n-1이고 p가 중앙에 오는 수열들에 대해서도 위 과정을 비슷하게 적용해 줍니다.
BFS를 사용해서 구현하려고 시도했지만, 아직 AC를 받지 못했습니다.

Edit: p가 각각 중앙, 1/4지점, 3/4지점에 오는 길이 2^i-1의 수열들을 큐에 집어넣고 BFS를 돌리는 방식으로 해서 3월 3일에 AC를 받았습니다.

10443번. Mokia (AC)

목요일에 뽑은 문제입니다.
x1-1, y1-1, x2, y2를 기준으로 좌표 압축을 해 주면 20000*20000 크기의 2차원 배열이 나옵니다.
저는 2차원 다이나믹 세그먼트 트리를 사용해서 O(AlogQ + Qlog^2Q)에 해결했습니다. (A는 Add연산의 시행 횟수, Q는 Query연산의 시행 횟수)
메모리 제한이 128MB여서 안 될 것 같아 보였지만, short 자료형을 쓰는 등 온몸비틀기를 해서 AC를 받았습니다.

난이도 기여는 D4로 했습니다.

17975번. Strike Zone (AC)

금요일에 뽑은 문제입니다.
금광세그의 그 금광과 완전히 동일한 문제여서 바로 구현했고 AC를 받았습니다.

난이도 기여는 D5로 했습니다.

주말에 뽑은 문제들은 별다른 관찰 없이 흘렸습니다. 하루에 하나씩 코포 셋을 돌고 나서 다이아 문제 잡기까지 하기는 힘들었습니다.
2월 3주차 월요일부터 2월 4주차 일요일까지 14일동안 랜덤 돌려서 뽑은 9문제를 풀어냈습니다.
제 처음 예상으로는 셋 크기를 3 언저리에서 방어해 낼 줄 알았습니다.
제 자신을 너무 과대평가했거나, 다이아를 너무 과소평가했습니다.

다소 개인적인 생각이지만, ICPC 문제들은 OI 문제에 비해 비슷한 "발상 난이도"를 가지는 문제들의 티어가 두세 단계 더 높습니다.
ICPC 문제들만 놓고 보면 대부분의 플래 문제들을 대회 시간 내에 해결할 수 있지만, OI 문제는 체감상 훨씬 더 빡셌습니다.
따라서 /olympiad *d5 문제들을 이런 식으로 풀어낼 수 있다면, 대회 시간에 낮~중간 다이아까지는 건드려 볼만 하다는게 아닐까요??
가 사실인지는 오는 3월 8일에 아챔셋을 돌고서 확인할 수 있을 것입니다. 높은 확률로 제 머리가 깨질 것 같습니다.

3월 2주차부터 FS라는 훈련이 2주간 예정되어 있습니다. 훈련 기간 동안에는 모종의 사유로 하루에 하나씩 추가되는 다이아 문제들을 풀어낼 자신이 없습니다.
FS 때에는 다이아 풀기를 잠깐 멈추고 코포 셋을 돈다던가 아니면 아예 PS를 쉬고 다른 분야에서 수련을 하는 방식으로 살 것 같습니다.

감사합니다.