rkm0959

http://codeforces.com/gym/101933 

F 빼고 다 풀었다. 풀이 보고 구현이라도 해보려고 했는데 기하에 4차 방정식 어쩌구 나와서 ㅋㅋㅋ... 

NCPC는 문제가 참 재밌는 것 같다. http://koosaga.com/217 참고.

스포 방지선 

________________________________________________________________________________________________________________________

________________________________________________________________________________________________________________________

B. Baby Bites & C. Code Cleanups & H. House Lawn

셋 다 깡구현인데, C가 조금 기분 나쁜 깡구현이다. 코드 짜면서 너무 헷갈림 ㅋㅋ

K. King's Colors

Vertex가 \(n\)개인 Tree를 \(k\)개의 색깔로 칠하는 방법의 수를 계산할 수 있다면, 포함-배제를 통하여 답을 빠르게 계산할 수 있다. 

Root를 먼저 \(k\)개 색 중 하나로 칠하고, 트리를 내려가면서 색깔을 \(k-1\)개 중 하나로 계속 선택할 수 있다.

그러므로 \(n\)개인 Tree를 \(k\)개의 색깔로 칠하는 방법의 수는 \( k(k-1)^{n-1} \)이다. 시간복잡도는 \( \mathcal{O}(k \log n)\) 

I. Intergalactic Bidding

'2배 이상' 조건 때문에 답이 존재한다면 유일하게 존재하고, greedy한 풀이를 적용할 수 있다. (cf. 2진법)

그래서 greedy하게 넣을 수 있는 가장 큰 값을 더해주면서 원하는 합을 만들 수 있는지 확인하면 된다. 

숫자가 좀 많이 커서 big number를 써야한다. 복붙해서 적당히 비벼주면 AC.

J. Jumbled String

2년 전에 탈탈 털렸던 https://codeforces.com/contest/708/problem/B 문제와 정확히 동일하다. 

\(a=0\)이나 \(d=0\)인 경우를 먼저 적당히 예외처리하고. 이제 \(a, d \neq 0\)인 경우만 고려하자.

\(cnt_0, cnt_1\)을 0과 1의 개수라 하면, \(a=\binom{cnt_0}{2}, d=\binom{cnt_1}{2}, b+c=cnt_0 \cdot cnt_1\)이 성립한다.

이를 통해 \(cnt_0, cnt_1\)의 값을 유일하게 결정할 수 있다. 또한, 위에 있는 \(a, b, c, d\)에 대한 식이 성립하면 string이 존재한다. 

0이 \(cnt_0\)개, 1이 \(cnt_1\)개가 이 순서대로 나열된 string에서 시작해서, 1을 하나씩 왼쪽으로 보내자.

01을 10으로 swap하는 과정에서 b, c의 값은 정확히 1씩 변한다. 또한, 처음에 \(c=0\)이고 최종 상태에선 \(b=0\)이다.

게다가 \(b+c\)가 invariant이니 우리가 원하는 조건을 만족하는 string은 이 과정에서 만들어진다. 

이 과정을 적당히 빠르게 simulate하거나 방정식을 풀어서 대강 \(\mathcal{O}(\sqrt{a+b+c+d})\) 풀이를 만들 수 있다.

E. Explosion Exploit

결국 중요한 것은 내 minion의 체력 집합/상대 minion의 체력 집합/남은 딜량이다. 

생각보다 가능한 state가 몇 개 없음을 알 수 있고, 이를 통해서 동적 계획법을 세우면 된다. 

초기 조건과 transition도 꽤 자명해서 풀이 자체는 쉽게 나온다. 나는 구현에서 좀 삽질했다.

처음에는 내 minion의 체력 집합/상대 minion의 체력 집합을 두 개의 vector로 관리했다. 

즉, State를 vector 2개와 자연수 하나로 설정하여 관리했다. 

vector를 항상 정렬된 상태로 만들고, vector 내부에 0이 없도록 관리하고, dp table을 map으로 만들었다.

map 내부에서 문제가 난 건지 단순 코딩 미스인건지는 잘 모르겠지만 코드가 잘 작동을 못했다.

그 다음에는 내 minion의 체력 집합/상대 minion의 체력 집합을 두 개의 string으로 관리했다. 여전히 망.

결국 내 minion의 체력 집합/상대 minion의 체력 집합을 두 개의 자연수로 관리했다.

체력 집합을 자연수 \( \sum_{i=1}^6 (\text{#number of minions with health }i) \cdot 10^{i-1} \)로 대응시켰다. 

이제 State가 자연수 3개로 표현이 된다. 이제 답이 제대로 나오기 시작했는데, dp table을 map으로 관리하니 TLE가 떴다. 

그래서 State를 큰 자연수 하나로 직접 hash해주고 (\(10^6\)진법), unordered_map을 사용했더니 AC. 힘들었다.

A. Altruistic Amphibians 

코포에서 NCPC 2018 Open 글을 보면, 무게 합이 \(10^8\) 이하라는 조건을 보지 못했다며 댓글로 FUCK을 외치는 분이 있다. 

이미 이 댓글을 본 상태여서 약간 스포일러 당한 상태로 문제를 풀었다. 풀이가 신기했다.

자기보다 가벼운 개구리만 지탱할 수 있으니, 항상 가벼운 개구리가 먼저 나간다고 볼 수 있다.

\( H_w\)를 \(w\)만큼의 무게를 지탱할 수 있는 개구리 탑의 높이의 최댓값이라 정의하자. 

무거운 개구리부터 순서대로 보자. 시간 역순으로, 나중에 나갈 개구리부터 보자. 

일단 \( H_{w_i} + Jump_i > D \)면 \(i\)번째 개구리가 탈출할 수 있다. 

또한, \( H_w = \text{max}(H_w , h_i + H_{w+w_i}) \)로 (단, \(1 \le w \le w_i\)이다) 배열 \(H\)의 값이 update 된다. 

결국 이 과정을 각 개구리에 대해 반복적으로 진행하면 된다. 시간복잡도는 \(\mathcal{O}(n \log n + \sum w_i )\)

D. Delievery Delays

재밌는 문제다. 일단 입력을 받고 다익스트라를 \(n\)번 돌려, 임의의 두 정점 사이의 최단거리를 구하자.

\( dist(i,j)\)를 \(i\)번째 주문이 들어온 지점과 \(j\)번째 주문이 들어온 지점 사이의 거리라 하자. 

편의상 피자 가게는 \(0\)번째 주문이 들어온 지점이라고 하자. 

Claim: \(K_n\)은 \(n\)이 홀수면 \(n\)개의 색으로, \(n\)이 짝수면 \(n-1\)개의 색으로 edge-colorable하다.

Proof of Claim: 사실 이게 tight한데, 증명은 자명하니까 넘어가자. construction만 찾아주면 된다.

Case 1. n 홀수: 각 정점에 \(0, 1, \cdots n-1\)을 두고, \(i+j \equiv k \pmod{n}\)이면 \(edge(i,j)\)를 색 \(k\)로 칠하자. 

Case 2. n 짝수: proof without words. 한 1분 정도 그림 보고 있으면 바로 감이 잡힐 것이다. \(\blacksquare\)

이제 본 문제로 돌아와서, construction을 잡아보자. 각 사람을 (팀, 번호)로 표기하자. index는 적당한 mod를 취해서 보자.

\(n\)이 짝수인 경우에서는 먼저 \(K_n\)의 edge를 \(n-1\)개의 색깔로 칠하자. \(i\)번째 색깔로 칠해진 간선들을 \((u_{i,j}, v_{i,j})\)라 하자.

각 \(1 \le i \le n-1, 1 \le T \le m-1\)에 대해 다음을 반복한다. 

각 \(1 \le k \le m\)에 대하여 \((k,u_{i,j})\)와 \((k+T,v_{i,j})\)가 경기하게 한다.

이를 하나의 round로 만들자. 총 \((n-1)(m-1)\)개의 round를 통해 '자신과 번호가 다른' 사람들과의 경기가 끝난다.  

이제 \(K_m\)의 edge를 \(m\)개의 색깔로 칠하자. \(i\)번째 색깔로 칠해진 간선들을 \((u'_{i,j},v'_{i,j})\)라 하자.

각 \(1 \le i \le m\)에 대하여 다음을 반복한다.

각 \(1 \le k \le n\)에 대하여 \((u'_{i,j},k)\)와 \((v'_{i,j},k)\)가 경기하게 한다.

이를 하나의 round로 만들면, \(m\)개의 round를 추가하여 모든 시합이 끝나게 된다. 총 \((m-1)n+1\)개 round.

\(n\)이 홀수인 경우에서는 \(K_n\)의 edge를 \(n\)개의 색깔로 칠하자. \(i\)번째 색깔로 칠해진 간선들을 \((u_{i,j}, v_{i,j})\)라 하자.

또한, \(K_m\)의 edge를 \(m\)개의 색깔로 칠하자. \(i\)번째 색깔로 칠해진 간선들을 \((u'_{i,j},v'_{i,j})\)라 하자.

각 \(1 \le i \le n, 1 \le T \le m-1\)에 대해 다음을 반복한다. 

각 \(1 \le k \le m\)에 대하여 \((k,u_{i,j})\)와 \((k+T,v_{i,j})\)가 경기하게 한다.

색깔 \(i\)를 가진 간선이 없는 유일한 정점 \(l_i\)를 잡자. \((u'_{T,j},l_i)\)와 \((v'_{T,j}, l_i)\)가 경기하게 한다.

이를 하나의 round로 만들자. 총 \(n(m-1)\)개의 round가 진행된다.

마지막 round에서 각 \(1 \le i \le n\)에 대하여 \((u'_{m,j},i)\)와 \((v'_{m,j},i)\)가 경기하게 한다.

총 \((m-1)n+1\)개의 round를 통해서 모든 시합이 끝나게 된다. AC. 코드는 좀 길다.

문제

(Graham, Pollak 1972) Prove that the edge set of \(K_n\) cannot be partitioned into the edge-disjoint union of less than \(n-1\) complete bipartite subgraphs. Also, prove that this bound is tight.

스포 방지선

________________________________________________________________________________________________________________________

________________________________________________________________________________________________________________________

(증명) \(K_n\)의 각 정점을 \(1, 2, \cdots , n\)이라 하자. 우선 \(n-1\)개의 완전 이분 그래프로 \(K_n\)을 분할하는 것은 쉽다. 

귀류법으로, 완전 이분 그래프 \(B_1 , B_2, \cdots B_m \)이 \(K_n\)을 분할한다고 하자. (단, \(m \le n-2\)다.)

또한, 각 완전 이분 그래프 \(B_k\) 안에서 두 disjoint independent set을 \(L_k, R_k\)라고 부르자.

즉, \(B_k\)의 간선은 \(L_k\)의 정점과 \(R_k\)의 정점 사이를 모두 연결한 것이다.

다음 조건을 만족하도록 \(K_n\)의 정점 \(v\)에 실수 \(x_v\)를 놓자. 

조건 1: 모든 \(1 \le k \le m\)에 대하여, \( \displaystyle \sum_{v \in L_k} x_v = 0 \)이고, \(\displaystyle \sum_{v=1}^n x_v = 0\) 

조건 2: \(\displaystyle \sum_{v=1}^n x^2_v \neq 0 \)이다. 즉, 모든 \(v\)에 대해 \(x_v\)가 전부 \(0\)은 아니다.

이것이 가능함을 보이자. 기초적인 선형대수학을 알면 쉽게 보일 수 있다.

조건 1은 식의 개수가 \(m+1\)개인 하나의 Homogeneous한 연립방정식을 이룬다. 

변수의 개수가 \(n\)개이고 \(m+1 < n\)이므로, 이 연립방정식은 non-trivial 해를 가진다. 

그러므로 조건 1, 2를 만족하도록 정점 \(v\)에 실수 \(x_v\)를 놓을 수 있다. 

이제 \(B_1 , B_2, \cdots B_m \)이 \(K_n\)의 edge set을 완벽하게 분할하므로, 다음 식이 성립한다.

$$ \sum_{1 \le i < j \le n} x_ix_j = \sum_{k=1}^m \left(\displaystyle \sum_{i \in L_k} x_i \right) \cdot  \left(\displaystyle \sum_{j \in R_k} x_j \right) $$

팀: glycine (rkm0959, TAMREF, leejseo) 결과: 8솔브, 4등

스코어보드: https://www.acmicpc.net/contest/scoreboard/346 

입시 공부와 이 대회 참가 사이에서 고민하고 있었는데, 탐레프가 leejseo랑 같이 팀으로 나가자고 해서 나갔다.

결과도 잘 나왔고 대회 자체도 엄청 재밌었다. 물론 3컴에 인터넷도 엄청 썼지만...

각자 코드를 짜서 AC를 받은 문제는 다음과 같다. 문제 순서는 AC 순서.

밑에 문제 이름 옆에 괄호 안에 써놓은 사람은 그 문제를 잡은 사람 목록이다.

rkm0959: G, L, H, F 

TAMREF: J, C, D

leejseo: B

G: 등록 (rkm0959, 1분)

대회 중 풀이: 그냥 출력하면 되는데 팀 계정 기본 언어가 Text여서 한 번 틀렸다. 상큼한 시작.

J: The Chosen Sub Matrix (TAMREF, 28분)

대회 중 풀이: 범위가 작으니, 문제의 조건을 잘 읽고 구현하면 된다. 여러 이유로 3WA.

대회 후 내 풀이: 그냥 구현 문제라 크게 다른 건 없었다. 짜는 방식이 살짝 달랐다.    

L: Weights (rkm0959, 65분)

대회 중 풀이: 생각을 깊게 안하고 코드를 짜고 내다보니 쓸데없이 시간도 오래 걸리고 WA도 2번이나 났다. 

답에 대한 이진탐색이 가능하므로, 이진탐색을 하자. \( x \)개의 weight를 올리는 것이 가능한지 판별하고 싶다면, 당연히 가장 무게가 작은 \(x\)개의 weight들을 올릴 수 있는 지만 확인하면 된다. 이제 그리디하게 weight를 올리자.

durability가 큰 컨테이너 순으로 다음 시행을 한다.

올릴 수 있는 가장 무거운 weight를 컨테이너에 올려주는 것을 반복 

이 방식으로 모든 weight를 올릴 수 없으면, \( x \)개의 weight를 올리는 것은 불가능하다. 

또한, 주어진 배수 조건 때문에 서로 다른 weight 종류 개수는 \(\mathcal{O}(\log W)\)이다. 

이 두 가지 관찰을 하면 문제를 해결하는 것은 간단하다. 주어진 input을 정렬하고 weight의 종류/개수를 전처리를 하자.  

이제 결정문제를 쉽게 \(\mathcal{O}(N \log W)\)에 해결할 수 있고, 전체 문제도 제한 시간 안에 풀 수 있다.

이런 문제가 어떻게 8분 컷이 될까 싶다 ㅋㅋ

C: Cross Spider (TAMREF and leejseo, 68분)

대회 중 풀이: 모든 점이 한 평면 위에 있는지 판별하는 문제다. \( N \le 3 \)일 때는 당연히 참이고, \(N \ge 4\)를 보자. 

일직선 위에 있지 않은 세 점은 한 평면을 이루니까, 이 평면 위에 모든 점이 있으면 충분하다.

네 점의 Coplanarity는 벡터의 외적/내적을 활용하여 \( \mathcal{O}(1)\)시간에 판별할 수 있다. 

이걸로 \(\mathcal{O}(N) \) 풀이가 완성된다. overflow에 주의할 필요가 있다. 어쩌다보니 7WA;;

대회 후 내 풀이: '일직선 위에 있지 않은'을 빼먹어서 한 3WA 정도 한 것 같다. 극혐.    

D: Gophers (TAMREF and leejseo, 152분)

대회 중 풀이: 각 CD가 영향을 줄 수 있는 길이가 동일하므로, 각 CD가 '독점적으로 영향력을 발휘하는 영역'은 선분이다. 

그래서 이 구간을 구해주면서 그 구간에 속하는 구멍의 개수를 더하고 빼면서 쿼리에 답하면 된다. 

대회 중에는 OSRank와 펜윅을 써서 2928ms 뚝딱 AC. 사실 펜윅을 쓸 필요는 없다. (OSRank도 쓸 필요 없다. ㅋㅋ!)

대회 후 내 풀이: 독점구간 및 그 구간에 속하는 구멍 개수는 set을 사용하면 쉽게 계산 가능. lower/upper bound 쓰자.

H: Store-Keeper (rkm0959, 221분)

대회 중 풀이: http://www.usaco.org/index.php?page=viewproblem2&cpid=769 이 문제가 상당한 도움이 된다.

bfs를 돌려야 할 것 같은 문제인데, 상태를 (내 위치, 박스 위치)로 두면 상태 개수가 저세상으로 간다. 

그러니까 상태를 (박스 위치, 박스 기준으로 내가 있는 방향 - U/D/L/R)로 두자. 이러면 상태 개수가 \( \mathcal{O} (NM) \)이다.  

가능한 행동은 둘 중 하나다. 내가 있는 곳에서 박스를 밀어 움직이거나, 다른 방향에서 박스를 밀기 위해 내가 움직이는 것이다. 첫 번째 행동은 박스를 밀 수 있는지를 판별하는 게 \( \mathcal{O}(1)\)에 되니 문제 없다.

두 번째 행동은 조금 까다로운데, 내가 한 위치에서 다른 위치로 움직일 수 있는지를 판별해야 하기 때문이다.

이 과정에서 flood-fill을 하는 등의 방법을 쓰면 \( \mathcal{O}(N^2M^2)\) 풀이가 나온다. 

잘 짜여진 \( \mathcal{O}(N^2M^2)\)는 실제로 AC를 받았지만, 그렇지 않으면 TLE가 뜬다고 한다. 

시간을 줄이려면 두 번째 행동이 가능한지 여부를 빠르게 판별할 수 있는 방법을 찾아야 한다.

여기서 biconnected component를 떠올릴 수 있다. grid를 그래프로 보고, biconnected component를 구하자. 

grid의 각 칸이 (즉 그래프의 각 노드) 속한 biconnected component를 set 등으로 모두 저장하자.

각 칸이 속한 biconnected component의 개수는 최대 4개니까 (why?) set을 써도 큰 문제는 없다. 

이제 처음 위치와 끝 위치가 같은 biconnected component에 속하는 지 여부를 확인하여, 두 번째 행동이 가능한 지 불가능한 지 판별할 수 있다. 이 판별은 앞선 관찰에 의해 \( \mathcal{O}(1) \)에 가능하다. 이제 bfs를 그대로 돌리면 문제가 \( \mathcal{O}(NM) \)에 풀린다. 

Tarjan BCC를 처음 써봤다. 많은 것을 배울 수 있었던 문제. 위에 저 USACO 문제도 풀어봐야 할 듯.

F: Laundry (rkm0959, 244분)

대회 중 풀이: \(i\)번째 오는 사람은 \(2d_i\)개 양말용 빨래집게, \(3d_i\)개 셔츠용 빨래집게가 필요하다. 

이 문제는 그리디로 풀 수 있는 문제다. \(d_i\)가 큰 사람 순서로, 다음과 같이 집게 색깔을 고르자.

1. 집게가 \(5d_i\)개 이상 있는 색깔이 있으면, 그 중 집게 개수가 가장 작은 색깔을 골라 양말/셔츠용으로 한다.

2. 1이 실패했다면, 집게가 \(3d_i\)개 이상 있는 색깔 중 집게 개수가 가장 작은 색깔을 골라 셔츠용으로 한다.

3. 1이 실패했다면, 집게가 \(2d_i\)개 이상 있는 색깔 중 집게 개수가 가장 작은 색깔을 골라 양말용으로 한다.

이렇게 해서 색깔 분배가 가능한 지 확인하면 된다. set과 lower/upper bound를 쓰면 쉽게 구현할 수 있다. \( \mathcal{O}(N \log N) \).

B: Bytean Road Race (leejseo, rkm0959, 283분)

대회 중 풀이: leejseo와 내가 각자 맞는 풀이를 발견했고, 각자 짜서 냈다. 내 코드는 틀렸고, leejseo가 맞았다. 갓...

leejseo의 풀이는 https://en.wikipedia.org/wiki/Reachability#Kameda's_Algorithm을 쓴다. 

간단하게 설명하면, 주어진 그래프에서 reachability는 하나의 partial order와 같다. 

그런데 dfs를 2번 '잘' 하면, dfs에서 정점이 label된 순서를 통하여 reachability의 partial order를 얻을 수 있다!   

https://www.sciencedirect.com/science/article/pii/0020019075900198?via%3Dihub 참고. 

알고리즘이 선형이라서 진짜 개빠르다 ㄹㅇ;;; 대신 대회장에서 생각하기는 좀 어려운 풀이인듯 싶다.

대회 중 풀이/대회 후 내 풀이: 풀이를 설명하기 위해 먼저 정의를 하나 내리자.

Definition: 정점 \(v\)에 대하여, 경로 \(DP(v)\)와 \(RP(v)\)를 다음과 같이 정의하자. 

\(DP(v)\): \(v\)에서 시작해 아래쪽으로 갈 수 있을 때는 아래쪽으로 이동하고, 아니면 오른쪽으로 이동하여 \(n\)에 도착하는 경로. 

\(RP(v)\): \(v\)에서 시작해 오른쪽으로 갈 수 있을 때는 오른쪽으로 이동하고, 아니면 아래쪽으로 이동하여 \(n\)에 도착하는 경로. 

또한, 정점 \(v\)에 대하여, 정점 \(DPnext(v)\)와 \(RPnext(v)\)를 다음과 같이 정의하자. 

\(DPnext(v)\): 경로 \(DP(v)\)에서 \(v\) 다음으로 방문하는 정점. 편의상 \(DPnext(n)=n\)으로 둔다.

\(RPnext(v)\): 경로 \(RP(v)\)에서 \(v\) 다음으로 방문하는 정점. 편의상 \(RPnext(n)=n\)으로 둔다.

풀이의 핵심은 다음 관찰이다. 

Claim 1: 두 정점 \(u, v\)가 있다. 이때, 다음 두 명제는 동치다.

명제 1: \(u\)에서 \(v\)로 갈 수 있는 경로가 존재한다. 

명제 2: \(v\)는 \(DP(u)\)와 \(RP(u)\) 사이에 존재한다.

이 Claim은 \(1\)번 정점에서 모든 점에 도달할 수 있고, 모든 점에서 \(n\)번 정점에 도달할 수 있다는 문제 조건에 의해 성립한다. 

직관적으로 이해하기 쉬운 Claim으로, 그 증명 자체도 크게 어렵지 않을 것으로 예상한다. 

이제 명제 2가 참인지 거짓인지를 어떻게 빠르게 판별할 지 생각해보자. 다시 두 가지 관찰을 해야 한다.

Claim 2: 앞선 Claim 1에서의 명제 2는 다음 명제 3와 동치다. 

명제 3: \(DP(u)\)에서 처음으로 \(y\)좌표가 \(v\)의 \(y\)좌표보다 작거나 같은 점을 \(w_1\)이라 하자.

또한, \(RP(u)\)에서 처음으로 \(x\)좌표가 \(v\)의 \(x\)좌표보다 크거나 같은 점을 \(w_2\)이라 하자.

이때, \(w_1\)의 \(x\)좌표는 \(v\)의 \(x\)좌표보다 작거나 같고, \(w_2\)의 \(y\)좌표는 \(v\)의 \(y\)좌표보다 크거나 같다. 

Claim 3: \(DP(u)\)는 \(u\) 뒤에 \(DP(DPnext(u))\)를 붙인 것이다. \(RP(u)\)도 마찬가지.

두 Claim 다 직관적으로 이해하기 쉽고 자명하다. 경로 위에서 \(x, y\) 좌표는 모두 단조적이므로, Claim 2와 이진탐색을 섞으면 명제 2가 참인지 거짓인지를 판별할 수 있을 것 같다! 실제로 이는 가능하다.

이진탐색을 떠올리면 남은 것은 \(DP(u)\)에서 \(k\)번째 정점을 빠르게 구하는 방법을 찾는 것이다.

Claim 3에서 나온 관찰에서, Sparse Table을 사용할 수 있음을 파악할 수 있다.

자세한 설명은 고려대학교 2017 경시 Line Friends 참고. http://koosaga.com/206에 잘 설명되어 있다.

이제 이진탐색 대신 LCA를 구하는 방법처럼 binary lifting을 하여 명제 3이 성립하는지 확인할 수 있다. 

대회에서는 binary lifting 부분에서 케이스 하나를 놓쳐서 틀렸다. 시간복잡도는 \( \mathcal{O}((N+Q)\log N)\)이다.

http://codeforces.com/gym/101915/standings 버추얼 1등 꿀꺽 ㅋㅋ

딱히 어려운 문제가 없어서 그런지 운 좋게 빨리 밀었다. 인예보다 훨씬 쉬운 셋인듯 싶음.

엄청 어렵지는 않으면서도 생각해야 하는 문제가 많고 자료구조 연습도 되는 셋을 찾고 싶다. 추천 좀...

스포 방지선

________________________________________________________________________________________________________________________

________________________________________________________________________________________________________________________

F (0:01) C (00:03)

너무 대놓고 주는 문제.

A (0:09)

숫자의 개수를 빠르게 세는 방법을 알고 있으면, 거기에 이진탐색을 끼얹으면 된다.

H (0:15) +1

simple dp인데 구현 실수로 +1 당함 ㅋㅋ...

K (0:29)

부분합 먼저 구해주고, 각 연속된 구간에 대해 그 구간을 sumindrome으로 분할하는 경우의 수를 dp로 구한다.

sumindrome의 길이가 짝수인 경우 처리가 약간 헷갈렸는데 어떻게 잘 했다. 

D (0:42) +1

각 남자가 알고 있는 여자의 집합을 bitmask로 만든 뒤, 각 남자의 집합을 돌면서 그 집합에 속한 남자들의 bitmask를 and한 값을 구하자. \( \mathcal{O}(P 2^P) \)로 풀었더니 TLE가 나고, \( \mathcal{O}(2^P) \)로 줄이면 AC. highest bit를 빠르게 구하면 시간복잡도가 줄어든다. 

E (1:14)

사람들이 다 고전하던 문제. 재귀 돌리면 된다. \( r \)개의 줄을 차례대로 채워나가자. 만약 현재 \( i+2 \)번째 줄을 채우고 있다면 \( 1, 2, \cdots i \)번째 줄에 속한 칸들은 주어진 조건을 다 만족해야 한다. 이걸 기반으로 잘 커팅해주면 빠르게 결과가 나온다. 

J (1:34)

연결되어 있는 구멍들을 하나의 컴포넌트로 보자. 양쪽 벽에 모두 붙어있는 컴포넌트의 개수를 세면 된다. 

원 연결 판별은 쉽고, 벽 붙어있는 거 판별도 쉽고, 컴포넌트 관리는 union-find로 쉽게 할 수 있다.

G (2:15) +1

각 정점 \( v \)에 대하여, \( I_v \)를 "\( v\)에서 로봇이 멈추게 하는 \( x_i \)의 집합"이라고 하자. 

핵심은, \( I_v \)가 공집합이거나 하나의 구간을 이룬다는 사실을 파악하는 것이다. 이 구간들은 dfs를 한 번 돌려서 구해줄 수 있다. 이 구간들을 다 구해주면, 각 쿼리마다 답을 로그 시간에 계산할 수 있다. 구현이 조금 힘들었다. 

B (2:54) +1

이 셋에서 그나마 가장 아이디어 문제인 것 같다. 핵심은 Ali가 선정해야 할 점의 후보군을 줄이는 것이다.

각 원 사이의 교점과, 각 원의 중심만 봐도 충분하다. 직관적으로 자명하고 증명도 크게 어렵지 않을 듯. 

점의 후보가 \( \mathcal{O}(N^2) \)개로 줄었고, 각 점마다 최대 wifi 속도를 \( \mathcal{O}(N \log N) \)에 구하면 \( \mathcal{O}(N^3 \log N ) \)에 문제가 풀린다. 

TLE가 한 번 났는데, Priority_Queue를 한 번만 선언하고 쓸모없는 vector 연산을 줄였더니 아주 빠르게 AC가 떴다.

I (3:17)

string 순서로 sort하고, 순서대로 보면서 BIT로 답을 구할 수 있다. 너무 전형적인 문제.

L (4:00) +4

부호 뒤집고 max를 구하면 min이 튀어나오니까 max만 구할 줄 알면 충분하다. 

1차원 배열에서 가능한 모든 연속한 구간의 최댓값을 다 더한 값을 \( \mathcal{O}(N) \)에 구하는 방법이 있다.

stack을 활용하여, 각 원소마다 "자신 왼쪽/오른쪽에서 자신 초과/이상인 값이 처음 등장하는 위치"를 구하면 된다. 

이를 그대로 활용하면, 이 문제를 \( \mathcal{O}(N^3) \)에 해결할 수 있다.

TLE가 엄청 많이 나서 좀 피곤했다. stack을 STL에서 배열 구현으로 바꾸고, long long을 다 int로 바꾸고, 입력도 scanf 대신 cin + 최적화로 바꿨다. 그랬더니 아슬아슬하게 AC. 딱히 좋은 문제는 아닌듯...

https://www.acmicpc.net/problem/13407

문제

\( 2 \le x_{bb}, y_{bb} \le 10^9 \)를 만족하는 자연수 \( x_{bb}, y_{bb} \)가 주어진다. 다음 조건을 만족하는 다각형을 하나 찾아 출력하라.

1. 다각형의 vertex 개수는 3 또는 4이다. 

2. 다각형의 변들은 변의 끝점을 제외한 점에서 서로 만나지 않는다. (self-intersecting polygon이 아니다.)

3. 다각형의 각 vertex의 \(x, y\) 좌표는 모두 정수다. 또한, \( x\) 좌표는 \( 0 \)과 \(x_{bb}\) 사이, \(y\) 좌표는 \(0\)과 \(y_{bb}\) 사이이다.

4. 적어도 한 vertex는 \( x\) 좌표가 \( 0 \)이다. 적어도 한 vertex는 \(x\) 좌표가 \(x_{bb}\)다.

5. 적어도 한 vertex는 \( y\) 좌표가 \( 0 \)이다. 적어도 한 vertex는 \(y\) 좌표가 \(y_{bb}\)다.

6. 이 다각형의 넓이는 \(25000\) 이하이다. 

7. 이 다각형은 볼록다각형일 필요는 없다. 즉, 오목 다각형도 허용한다. 

TC 문제로, 한 문제 당 test case가 최대 \(10^5\)개 들어온다. 시간 제한은 3초. 

스포 방지선 

________________________________________________________________________________________________________________________

________________________________________________________________________________________________________________________

일본 문제답게 아주 신기한 문제. ksun48이 팀연습에서 이 문제를 풀고 Harvard-MIT Math Tournament에 그대로 냈다. AGC 문제도 하나 HMMT에 냈던데 수학 경시랑 정보 경시랑 연관관계가 커지는 것 같기도 하다 ㅋㅋㅋ

나는 https://www.acmicpc.net/workbook/view/1629 여기서 이 문제를 접했다. 

이 문제 이야기하다가 ksun한테 이 문제집도 소개함... zigui님 문제집에서 이 문제 봤어요~ 했더니 링크 달라더라 흠

일단 \( x, y\) 좌표에 대한 제한조건이 상당히 강하게 들어가 있으니, 여기서부터 construction을 잡아보자. 

또한, 우리가 원하는 다각형은 삼각형이나 사각형이므로, 각각의 경우에서 넓이를 줄일 수 있는 방법을 고안하자.

이제부터 편의상 \(x_{bb}, y_{bb}\)를 \(X, Y\)로 쓴다.

다각형이 \( (0,0), (X, Y) \)를 정점으로 가진다고 하자. 그러면 조건 4, 5가 바로 충족된다.

남은 한 점 \( (a,b) \)를 잘 잡아서 삼각형을 만든다고 하면, shoelace formula에 의해 \( |aY-bX| \)를 최소화하는 문제가 된다. 

이는 크게 어렵지 않다. \(|aY-bX| \)는 \(0\)이 아니라면 무조건 \(\text{gcd}(X,Y) \) 이상이다. 

또한, \( |aY-bX| = \text{gcd}(X,Y) \)가 되는 \(a, b\)를 modular inverse를 사용해 구할 수 있다. 넓이는 \( \frac{1}{2} \text{gcd}(X,Y) \).

결국 우리는 \( \text{gcd}(X,Y) \)가 \(50000 \) 이하일 때 이 문제를 해결했다.

삼각형을 한 번 사용했으니, 사각형을 사용할 필요가 느껴진다. 또한, \( \text{gcd}(X,Y) \)가 큰 걸 활용할 필요가 느껴진다. 

핵심 아이디어는 오목사각형을 만드는 것이다. \( \frac{y}{Y} = \frac{x}{X} \)를 중심축으로 하여 찌부러진 팩맨 모양을 만들어보자. 

즉, \( (0,0), (X-1,Y), (X,Y-1) \)을 잡고, \( (0,0)\)과 \( (X,Y) \)를 이은 직선 위에 점을 하나 잡아서 연결하자. 

\( \left( \frac{X}{\text{gcd}(X,Y)}, \frac{Y}{\text{gcd}(X,Y)} \right) \)를 사용하여 오목사각형을 만들면, shoelace formula에 의해 넓이가 \( \frac{X+Y}{2\text{gcd}(X,Y)} \)임을 알 수 있다. 

\( X, Y \le 10^9 \)이므로 \( \text{gcd}(X,Y) \ge 50000 \)이면 이 값은 \(25000\) 이하이다. 

결국 우리는 \( \text{gcd}(X,Y) \)가 \(50000 \) 이상일 때도 이 문제를 해결했다.

두 아이디어를 합치면 AC. 시간복잡도는 \( \mathcal{O} (TC \log XY) \)임을 쉽게 알 수 있다. 

문제

\( a_1, a_2, \cdots a_n \)은 \( a_1 a_2 \cdots a_n = 1 \)과 \( 0<a_1 \le a_2 \cdots \le a_n \)을 만족하는 실수들이다.

각 \( 1 \le k \le n \)에 대하여, \( b_k = 2^k (1+a^{2^k}_k) \)라고 정의하자. 이때 다음 부등식이 성립함을 보여라.

$$ \sum_{i=1}^n \frac{1}{b_i} \ge \frac{1}{2} - \frac{1}{2^{n+1}} $$

스포 방지선

_______________________________________________________________________________________________________________________

________________________________________________________________________________________________________________________

많은 학생들이 삽질을 했고, 일부가 아주 복잡한 테크닉을 활용해서 힘겹게 푼 문제다. 준-보스 문제.

나는 이 문제를 당시에 아주 깔끔하게 풀었는데, 지금 생각해보면 이거 덕분에 점수를 좀 딴 것 같다.

(증명) 일단 다음 Lemma를 먼저 증명한다. 

(Lemma) \( x, y \)는 \( 0< x \le 1, y>0 \)을 만족하는 실수들이다. 이때 다음 부등식이 성립한다.

$$ \frac{1}{2(1+x)} + \frac{1}{4(1+y)} \ge \frac{1}{4} + \frac{1}{4(1+x^2y)} $$

(Proof of Lemma) 항을 적당히 묶어주면서 계산하자. 

$$ \frac{1}{2(1+x)} + \frac{1}{4(1+y)} \ge \frac{1}{4} + \frac{1}{4(1+x^2y)} $$

$$ \iff \frac{1}{2(1+x)} - \frac{1}{4} \ge \frac{1}{4(1+x^2y)} - \frac{1}{4(1+y)} $$

$$ \iff \frac{1-x}{1+x} \ge \frac{(1-x^2)y}{(1+y)(1+x^2y)} \iff (1+y)(1+x^2y) \ge (1+x)^2y$$

$$ \iff 1+x^2y + y+x^2y^2 \ge y+2xy+x^2y \iff (xy-1)^2 \ge 0$$

등호 성립은 보다시피 \( x=1 \) 또는 \( xy=1 \)에서 이루어진다. 

본 문제로 돌아오자. \(n \)에 대한 귀납법으로 문제를 해결한다. \( n=1 \)은 자명.

\( n=2 \)인 경우는 Lemma에 \( x=a^2_1, y=a^4_2 \)를 넣어주면 바로 성립함을 확인할 수 있다.

이때, 등호 성립 조건은 Lemma와 문제에서 주어진 조건에 의해 \( a_1 = a_2 = 1 \)이다. 

이제 귀납법을 적용해보자. 엄밀한 귀납 서술은 생략한다. 

\( a_1 a_2 \cdots a_n = 1 \)과 \( 0<a_1 \le a_2 \cdots \le a_n \)를 만족하는 \( a_1, a_2, \cdots a_n \)를 잡자. 

이제, \( c_1=a^2_1a^2_2 \), \(c_2=a^2_3 \), \(c_3 = a^2_4 , \cdots ,c_{n-1} = a^2_n \)로 새로운 변수를 두자.

Fact. \( 0<c_1 \le c_2 \le \cdots \le c_{n-1} \)이고, \( c_1c_2 \cdots c_{n-1} = 1 \)이다. 

첫 번째 사실은 \( a_1 \le 1\)과 \(a_i \le a_{i+1} \)에서 자명하고, 두 번째 사실은 자명하다.

즉, \( c_i\)들을 가지고 (\(n\)이 하나 줄었으니) 귀납 가정을 사용할 수 있다. 여기서 우리는 

$$ \frac{1}{2(1+a^4_1a^4_2)} + \frac{1}{4(1+a^8_3)} + \cdots \frac{1}{2^{n-1}(1+a^{2^n}_n)} = \sum_{k=1}^{n-1} \frac{1}{2^k(1+c^{2^k}_k)} \ge \frac{1}{2}-\frac{1}{2^n} $$를 얻는다. 이제 \( x= a^2_1, y=a^4_2 \)에 대하여 Lemma를 적용시켜주면, 

$$ \sum_{i=1}^n \frac{1}{b_i} = \frac{1}{2(1+a^2_1)} + \frac{1}{4(1+a^4_2)} + \sum_{k=3}^n \frac{1}{2^k(1+a^{2^k}_k)} $$

$$ \ge \frac{1}{4} + \frac{1}{4(1+a^4_1a^4_2)} + \sum_{k=3}^n \frac{1}{2^k(1+a^{2^k}_k)} \ge \frac{1}{4} + \frac{1}{2} \left( \frac{1}{2} - \frac{1}{2^n} \right) = \frac{1}{2} - \frac{1}{2^{n+1}} $$

등호 성립 조건은 \( a_1 = a_2 = \cdots a_n = 1 \)인 경우이고, 이 경우 밖에 없음을 귀납적으로 보일 수 있다.

스케치만 하자면, \( (a_1, a_2, \cdots a_n) \)에서 등호가 성립하면 \( (a^2_1a^2_2, a^2_3, \cdots a^2_n) \)에서도 등호가 성립하고, 귀납적으로 \( a_1a_2=a_3= \cdots = a_n=1 \)임을 알 수 있다. 이제 Lemma에서의 등호 성립 조건에 의하여 \( a_1=a_2=1 \)를 얻는다. 

초기 조건은 (\(n=1,2\)) 앞에서 했으니 증명이 끝난다. 이에 이 문제에 대한 증명이 끝난다. \( \blacksquare \) 

\( \LaTeX \) 테스트를 먼저 조금 해보려고 한다.

사실 미리보기에서만 잘 나오고 글을 쓰면 잘 안 나와서 멘탈이 터졌는데, king god @subinium님이 해결해주셨다.

$$ \sum_{i=1}^n \tau (n) = \sum_{a \le \sqrt{n}} \sum_{b \le \frac{n}{a}} 1 + \sum_{b \le \sqrt{n}} \sum_{a \le \frac{n}{b}} 1 -\sum_{a \le \sqrt{n} } \sum_{b \le \sqrt{n}} 1$$

$$= 2\sum_{a \le \sqrt{n}} (\frac{n}{a} + O(1)) - (\sum_{a \le \sqrt{n}} 1)^2= 2n \sum_{a \le \sqrt{n}} \frac{1}{a} + O(\sum_{a \le \sqrt{n}} 1) - (\sqrt{n}+O(1))^2$$

$$= 2n(\log \sqrt{n} + \gamma + O(\frac{1}{\sqrt{n}})) + O(\sqrt{n}) - n-O(\sqrt{n})+O(1) = n\log n +(2\gamma -1)n + O(\sqrt{n})$$

TODO

이 블로그에서 하고 싶은 거를 먼저 간단하게 정리한다. 

1. 경시 수학 - KMO 하면서 풀었던 진짜 좋은 문제들, 최근에 나온 좋은 문제 등등을 소개하고자 함

2. 해석학 - 입시 끝나고 Rudin (PMA) 해석학을 돌 생각인데, 내용 정리/연습문제 풀이를 진행하고자 함

3. 기타 재밌는 것들 - 재밌는 정리들을 소개하고자 함. 위 두 항목에 들어오지 않는 수학 포스트는 다 여기에 넣을 듯 싶음

4. 수학 계열 PS - PS에서 가끔 나오는 수학과 (특히 정수론) 관련된 다양한 알고리즘을 소개하고 이를 활용해 문제를 풀고자 함.

여기서는 Project Euler 문제, BOJ 문제, Codeforces 문제 등 다양한 곳에서 출제된 수학 알고리즘 문제를 풀고자 함.

5. Problem Solving - "진짜" PS를 여기서 하고자 함. 내가 자료구조를 진짜 더럽게 못하니까 자료구조 공부도 좀 하고...

6. 대회 후기 - 대회를 치거나 대회를 검수하거나 대회를 출제하거나 등등 일이 있을 때 여기서 후기를 쓰고자 함.

7. 기타 - 게임 얘기, 잡담, 여행 얘기, 테스트 글 등등을 넣으려고 한다. 

특히 지금 쓰고 싶은 글은

1. 피타고라스 쌍 (BOJ 16123) - 레시테이션 (BOJ 16141) - Mobius Madness (BOJ 16164) 설명

2. 정사각형 만들기 (BOJ 10803) 증명, Szemeredi-Trotter 정리 관련 포스트 다시 깔끔하게 쓰기

3. 좋은 수올 문제 몇 개 가져오고 풀이

4. 지금까지 동아리에 낸 모의면접 문제 소개 및 풀이

5. Project Euler 문제 어려운 거 몇 개 풀이

정도인데, 이걸 보면 내가 "진짜" PS를 얼마나 안 했는지 볼 수 있다. ㅋㅋ 백준은 꽤 한 것 같은데 다 수학이냐 ㅋㅋ 에휴...