KimHwon

https://stackoverflow.com/a/70870535

Netsh로 proxy 연결해주자.

아님 IIS로 proxy server를 구축할 수도 있고...

1. IIS 설치

https://www.google.com/search?q=windows+10+IIS 

IIS는 Proxy server로만 사용할 것이기 때문에 [인터넷 정보 서비스 > World Wide Web > 응용 프로그램 개발 기능] 항목은 전부 선택하지 않는다.

2. SSL 인증서 발급

https://www.google.com/search?q=iis+let%27s+encrypt 

win-acme을 사용하여 Let's Encrypt 에서 SSL 인증서를 발급받는다.

3. IIS Reverse proxy 설정

https://chongkong.github.io/iis-reverse-proxy

3.1. Application Request Routing과 URL Rewrite 모듈 설치

Application Request Routing 링크

URL Rewrite 링크

3.2. Proxy 설정

DESKTOP 홈 > Application Request Routing Cache > Server Proxy Settings

Enable proxy 체크

3.3. Port 설정

3.3.1. IIS 바인딩

Web Site 홈 > 바인딩

외부에 공개할 포트 바인딩을 추가한다.

예시로, Docker container의 8000번 포트가 expose 되어 있고, 내 도메인네임이 my.example.com일 때 외부 포트 8080으로 접속하려면 다음과 같다.

종류:        IP주소:                    포트:
  [https]     [지정하지 않은 모든 IP]      [8080]
호스트 이름:
  [my.example.com]
  [v] 서버 이름 표시 필요

SSL 인증서:
  [Let's Encrypt에서 발급한 인증서]

외부 포트를 도커에서 사용하는 포트와 같은 포트로 하면 충돌하기 때문에 다른 포트를 지정해야 한다. 차후 URL Rewrite로 연결할 것이다.

3.3.2. 방화벽 설정

제어판 > 시스템 및 보안 > Windows Defender 방화벽 > 고급 설정

또는, '고급 보안이 포함된 Windows Defender 방화벽' 검색 후 열기

https://learn.microsoft.com/ko-kr/windows/security/operating-system-security/network-security/windows-firewall/create-an-inbound-port-rule

앞서 바인딩한 포트들에 대해서 방화벽을 연다. TCP 80과 443은 IIS를 설치하면서 인바운드 규칙이 자동으로 등록되지만, Proxy port는 직접 등록해야 한다. 8080 포트에 대한 인바운드 규칙을 추가한다.

3.4. Reverse proxy 설정

Web Site 홈 > URL 재작성 > 규칙 추가 > 역방향 프록시

인바운드 규칙 서버 이름은, 로컬호스트의 docker container port 기입.

아웃바운드 규칙의 HTTP 응답의 링크 도메인 이름 재작성 체크

시작에는 위의 인바운드 규칙 서버 이름을, 끝에는 외부에서 접속할 Domain name을 기입.

인바운드 규칙
  HTTP 요청이 전달되면 서버 이름 또는 IP 주소 입력:
    [localhost:8000]

아웃바운드 규칙
  [v] HTTP 응답의 링크 도메인 이름 재작성
  
  시작:
    [localhost:8000]
  끝:
    [my.example.com]

URL 재작성의 인바운드 규칙과 아웃바운드 규칙이 하나씩 생성된 것을 확인할 수 있다.

추가된 인바운드 규칙 > 편집 > 조건

조건 입력:
  [{SERVER_PORT}]

패턴:
  [8080]

{SERVER_PORT}는 IIS 서버 변수 중 하나로, 요청이 전송된 포트 번호를 저장하고 있다.

URL 검색 패턴으로는 포트 번호를 사용한 proxy 지정을 할 수 없으므로, 기본 패턴으로 그대로 두고 조건 구문을 사용한다.

추가된 아웃바운드 규칙 > 편집 > 작업

작업 속성
  값:
    [http{R:1}//my.example.com:8080/{R:2}]

URL Rewrite할 값을 지정한다. 외부로 나갈 호스트네임에 외부 포트를 추가하였다.

정리하자면,

인바운드 규칙에서, 모든 URL에 대하여 (8080 포트를 사용하는 경우만) localhost:8000으로 재작성했다.

아웃바운드 규칙에서, 8080 포트를 통해 응답을 재작성했다.

더 자세한 설정 사항은 레퍼런스를 참조해볼 수 있다.

4. 서버 재시작

DESKTOP 홈 > 서버 관리 > 다시 시작

요즘 컨디션이 좋다. 실력이 늘은건지 웰노운이 나온건지 잘 모르겠지만 암튼 계속 올라서 좋긴 하다.

A. Balanced Substring

a의 개수와 b의 개수가 같은 substring을 찾는 문제이다. 문자열 "ab" 또는 "ba"는 항상 조건에 맞기 때문에, 그냥 주어진 문자열에서 "ab" 또는 "ba"가 있는지만 판별하면 된다.

놀랍게도 완탐을 돌리다 TLE 맞고 틀렸다. n이 작길래 무지성으로 냈는데 다시 찬찬히 계산해보니 1e9가 넘더라

B. Chess Tournament

참여자들을 정점으로 하는 그래프로 모델링하면 완전 그래프가 만들어진다. 1번 타입의 참가자는 절대 지면 안된다. 따라서 1번 타입 참가자에 연결된 간선들을 모두 지운다. 이제 남은 간선들을 가지고 2번 타입 참가자들을 연결해보자. 2번 타입 참가자들은 최소 1번만 이기면 된다. 즉, outdegree가 1 이상이 되도록 만들어야 한다. 완전 그래프기 때문에, 항상 2번 타입 참가자들을 잇는 단순 사이클이 만들어 질 수 있다. 아래 그림은 세 번째 테스트케이스의 풀이이다.

단순 사이클이 만들어지지 않는 경우는, 2번 타입 참가자가 2명 이하인 경우이다. 한편 2번 타입 참가자가 0명이라면 모든 참가자들이 서로 비기기만 하면 된다.(첫 번째 테스트케이스) 따라서 2번 타입 참가자가 1명이나 2명인 경우만 NO이고 나머지 모든 경우는 YES이다. YES라면, 앞에서 설명한 대로 단순 사이클을 만들고 그 사이클에 포함되는 간선을 제외한 모든 간선을 비기는 경우로 지정하면 된다.

C. Jury Meeting

nice하지 않은 경우를 생각해보자. 문제에 제시된 예시들을 잘 관찰해보면 다음과 같은 규칙을 찾을 수 있다.

• 수열 $a$에서 가장 큰 원소를 $a_k$라고 하자. $a_k$와 값이 같은 원소가 더 있다면, 항상 nice하다.
• 값이 $a_k - 1$인 원소가 하나도 없다면 항상 nice하지 않다.
• $a_k$ 이후에 값이 $a_k - 1$인 원소가 하나도 없다면 항상 nice하지 않다. 즉, $p$에 따라 $a$를 재배열했을 때, 구간 (k, n] 안의 모든 $i$에 대하여 $a_i < a_k - 1$이면 항상 nice하지 않다.

첫 번째 경우는 항상 nice하므로 $n!$이 답이다. 두 번째 경우는 항상 nice하지 않으므로 0이 답이다. 세 번째 경우를 잘 계산해야 하는데, 값이 $a_k - 2$보다 작은 원소가 $l$개라고 하면 다음과 같이 계산할 수 있다. $$ n! - \sum_{i=0}^l (n-i-1)! {k \choose i} i! $$ 팩토리얼은 오프라인으로 미리 계산해 둘 수 있고, combination은 페르마의 소정리와 분할정복을 통해 O(log n)에 계산할 수 있다.

역시 조합론 문제는 어렵다. 예제가 굉장히 잘 나와있어서 겨우 규칙을 관찰해 낼 수 있었다.

D. Inconvenient Pairs

불편한 쌍이 만들어지는 조건은 다음과 같다.

• 교차로 위에 있는 사람은 항상 불편한 쌍을 만들 수 없다.
• 같은 열에 있는 가로 도로에 있으면서 서로 다른 도로에 있는 두 사람은 항상 불편한 쌍이다.
• 같은 행에 있는 세로 도로에 있으면서 서로 다른 도로에 있는 두 사람은 항상 불편한 쌍이다.

먼저, 세로 도로와 사람들을 x좌표에 대하여 정렬한다. 이를 스위핑하면 같은 열에 있는 사람들을 골라낼 수 있다. 예를 들어 두 번째 테스트 케이스에서 1, 6, 7번 사람이 한 그룹, 8번 사람이 다른 한 그룹으로 분류된다. 이 골라낸 그룹을 이번엔 y좌표로 정렬한다. 그러면 한 그룹 내에서 같은 가로 도로에 있는 사람의 수를 찾아낼 수 있다. 현재 그룹의 크기를 $n$이고 같은 도로에 있는 사람이 $k$명이면 $\frac{\sum k(n-k)}{2}$이 불편한 쌍의 개수다.

같은 방식으로 y좌표에 대하여 한 번 더 하면 된다.

역대급 퍼포먼스다. 원래 carrot은 잘라내고 캡쳐해오는데 오늘은 좀 자랑하고 싶어서 다 나오게 찍었다.

A. Domino Disaster

입력된 문자열의 각 문자에 따라 출력할 문자가 1대1로 대응된다. U이면 D, L이면 L, R이면 R로 대응해서 출력하면 된다.

B. MEXor Mixup

MEX 결과가 a라는 것은, [0, a) 범위의 모든 정수가 이미 수열 내에 존재한다는 뜻이다. 오프라인으로 일단 0~3e5 까지 xor한 결과를 저장해 둔다. a-1까지 xor한 결과를 가지고 b와 비교해볼 수 있다. 만약 $xored[a-1] = b$라면 a가 답이다. $xored[a-1] \ne b$ 라면 $xored[a-1] \oplus b$을 추가하면 b가 나오기 때문에 a+1이 답이다. 그런데 $xored[a-1] \oplus b$가 a와 같을 수 있다. 그렇다면 임의의 x에 대하여 $xored[a-1] \oplus b \oplus x$와 $x$를 수열에 추가하면 된다. 이 때 답은 a+2이다.

C. Carrying Conundrum

brute force로 해결될 수도 있을 것 같은데, 그냥 무지성 경우의 수 DP를 사용했다.

$dp[i][bit] = (i\text{번째 자리까지 덧셈을 했을때, 자리올림이 }bit)$으로 정의한다. 자리 올림을 2bit로 들고 다니면서 관리해주고, 1의 자리부터 1e9의 자리까지 처리해주면 된다. 이 때, (0, n), (n, 0)인 순서쌍도 세지므로 dp 결과에 -2를 하면 답이다.

E. Non-Decreasing Dilemma

아주 전형적인 세그먼트 트리 문제이다. 흔히 알려진 테크닉인 금광세그를 풀어봤다면 쉽게 풀이를 떠올렸을 것이다.

세그먼트 트리의 노드를 다음과 같은 6개의 원소를 가진 struct로 정의하자.

• ans : 이 구간에서 단조증가하는 subarray의 개수. 즉, 구간쿼리의 답
• sz : 이 구간의 길이
• lval : 이 구간의 왼쪽 끝 원소의 값
• lsz : 이 구간의 왼쪽 끝 원소를 포함하는 subarray의 길이
• rval : 이 구간의 오른쪽 끝 원소의 값
• rsz : 이 구간의 오른쪽 끝 원소를 포함하는 subarray의 길이

일단 트리의 leaf에서는 ans = 1이고, lval = rval, sz = lsz = rsz이다.

두 서브노드 left와 right가 합쳐질 때 위 그림과 같이 두 가지 경우가 존재할 수 있다. 그림에서 초록색 박스는 left 노드, 파란색 박스는 right 노드이다. 노란색은 각 노드가 커버하는 구간에서 subarray이다.

첫 번째로 $left.rval > right.lval$인 경우이다.(빨강색 박스) 이 때, left의 오른쪽 끝 subarray(노란색 r) 과 right의 왼쪽 끝 subarray(노란색 l)은 그대로 나열된다. 따라서, $ret.ans = left.ans + right.ans$이다.

두 번째로 $left.rval \leq right.lval$인 경우이다.(하늘색 박스) 이 때, left의 오른쪽 끝 subarray(노란색 r) 과 right의 왼쪽 끝 subarray(노란색 l)은 merge된다. 즉, 이전에 존재했던 두 subarray를 제외하고, 새로 생긴 subarray(노란색 r+l)을 계산해야 한다. 따라서, $ret.ans = left.ans + right.ans - \frac{left.rsz(left.rsz+1)}{2} - \frac{right.lsz(right.lsz+1)}{2} + \frac{(left.rsz+right.lsz)(left.rsz+right.lsz+1)}{2}$이다.

단, 여기서 주의해야 할 것은, 서브노드 전체가 하나의 subarray로 존재하는 경우에는 ret.lsz 또는 ret.rsz를 다시 계산해야 한다. 예를 들어 위 그림처럼 $left.lsz = left.sz$인 경우, ret.lsz는 left.lsz가 아니라 left.sz + right.lsz이다. 마찬가지로 $right.lsz = right.sz$인 경우, $ret.rsz = left.rsz + right.sz$이다.

이러한 방식으로 두 서브노드를 합칠 수 있다. 세그먼트 트리를 정의했다면 나머지는 각 쿼리에 맞게 트리에 update 또는 query를 하면 된다.

5등까지 상품이 나가는데, 시작하고서 가벼운 마음으로 대충 문제 훑어보다가 5~10분 정도 날렸다. 만약에 바로 A번 잡고 풀었다면 3솔도 할 수 있었는데 아쉬웠다.

A. permutation making (00:14)

최대한 누적합이 같게 만들어줘야 한다. 누적합을 N으로 나머지 연산을 하므로, N의 배수들은 모두 똑같이 0으로 취급된다. 따라서 누적합이 N의 배수가 나오도록 N, 1, N-1, 2, N-2, ... 이렇게 배치해주면 된다. 그러면 홀수 번째 원소들은 모두 같고, 짝수 번째 원소들은 다 다르므로 조건을 만족한다.

D. 신촌 수열과 쿼리 (01:16)

2번 쿼리를 살펴보면, 구간 [l, i]에서 모든 원소가 j 이상이 되도록 l을 최대한 감소시키고, 구간 [i, r]에서 모든 원소가 j 이상이 되도록 r을 최대한 증가시키면 된다. 최솟값 세그트리를 사용해서 구간 [l, i] 또는 구간 [i, r]에 j보다 작은 원소가 있는지 O(logN) 안에 찾을 수 있다. 이분 탐색을 한 번씩 사용해서 조건을 만족하는 동안 l의 최솟값 그리고 r의 최댓값을 각각 구할 수 있다. 이렇게 하여 O(log log N) 안에 2번 쿼리를 해결할 수 있다.

1번 쿼리는 그냥 세그트리에 update해주면 된다.

문제를 잘못 읽어서 굉장히 헤멨다. 2번 쿼리의 구간에 i가 포함되어야 한다는 조건을 놓쳐서 머지소트트리+금광세그를 짜야 하나 고민했다.

G. 신촌방위본부 (업솔빙)

나무가 불에 타는 조건은, 내분점 공식과 동일하다. 즉, 미사일이 떨어진 좌표를 이어서 만든 도형의 내부(모서리에 걸친 점도 포함)에 있는 모든 나무가 불에 탄다는 뜻이다. 미사일이 떨어진 좌표들의 볼록껍질을 구하고 볼록다각형의 넓이를 구한다. 볼록다각형이 격자점 위에 있으므로 픽의 정리를 이용하면 다각형 내부에 있는 점의 개수를 구할 수 있다. 여기서 볼록다각형의 내부에 있는 보호막의 개수만큼 빼면 답이 된다.

미사일의 수가 2개 이하인 경우는 볼록다각형이 만들어지지 않으므로 예외처리를 해줘야하는데, 다 짜고 이 예외처리 부분을 짜다가 대회가 끝났다. 딱 3분만 더 있었다면 맞을 수 있었는데 매우 아쉽다.