ML-Agents를 이용해서 환경을 만들고 이를 학습시키보던 중 신기한(?) 현상을 발견했다.모든 hyperparameter가 같음에도 불구하고 ML-Agents 알고리즘과 SB3(Stable-Baselines3) 알고리즘의 성능 차이가 너무 크게 났던 것이다. (ML-Agents PPO가 SB3 PPO보다 훨씬 우세했다.)ML-Agents와 SB3의 PPO 코드를 엄청 뜯어보고 고친 결과 SB3 PPO를 이용해 Crawler환경에서 ML-Agents PPO의 성능을 동일하게 재현할 수 있었다.따라서 이 글에서는 SB3 PPO로 ML-Agents PPO의 성능을 재현하는 방법을 써보려고 한다. ML-Agents Crawler 환경본론에 들어가기에 앞서, 테스트에 사용된 Crawler환경에 대해서 간략히 ..

문제 다음과 같이 dp를 정의하자.$\text{dp}[n,k]$ : $n$번 진행했을때 가장 오른쪽 위치가 $k$일 확률 $n$번의 이동은 ($1$번의 이동) + ($n-1$번의 이동)으로 나눌 수 있다.이 아이디어를 적용해 다음과 같이 점화식을 구성할 수 있다.$$ \text{dp}[n,k] =p_\text{left} \cdot \text{dp}[n-1,k+1] +p_\text{stay} \cdot \text{dp}[n-1,k] +p_\text{right} \cdot \text{dp}[n-1,k-1] $$그런데, 가장 오른쪽의 위치가 $0$인 경우는 특별히 고려해 줄게 더 있다.이유는 설명하지 않겠지만 결과를 이야기 하자면, $\text{dp}[n,0]$를 계산할때 $p_\text{left} \cdot..

문제  이 문제의 dp 점화식은 어렵지 않게 구할 수 있다.$\text{dp}[i]$ : i번째 정점에서 1번 정점까지 메시지를 전하는데 걸리는 최소 시간$\text{dp}[i] = \min_j \left( \text{dp}[p_j] - v_i d_{p_j} \right) + s_i + v_i d_i$$p_j$ : 현재 정점의 $j$번째 parent$d_i$ : 1번 정점부터 i번째 정점 까지의 거리위 점화식의 $ \text{dp}[p_j] - v_i d_{p_j} $ 는 $ - d_{p_j} $와 $ \text{dp}[p_j] $ 를 각각 기울기와 y절편 으로 하는 직선에 대해 $x=v_i$ 일때의 값으로 볼 수 있으니까 CHT를 이용할 수 있다. 풀이 1 (내 풀이)DFS로 1번 노드부터 순서대로 d..

문제무한한 격자판이 있다고 하자.각 셀은 0 또는 1의 상태를 가질 수 있다.각 셀은 단위 시간 마다 다음 규칙에 따라서 상태가 바뀐다.$t$ 시간에 어떤 셀의 위치를 $(r,c)$ 라고 할 때 $(r+1,c)$와 $(r,c+1)$ 위치의 셀이 모두 $1$ 이면 $t+1$시간에 $(r,c)$ 셀의 상태는 1이다.$t$ 시간에 어떤 셀의 위치를 $(r,c)$ 라고 할 때 $(r+1,c)$ 또는 $(r,c+1)$ 위치의 셀이 $0$ 이면 $t+1$시간에 $(r,c)$ 셀의 상태는 0이다.초기에 상태가 1인 셀들이 유한하다고 할 때, 시간이 충분히 흐른다면 모든 셀들의 상태가 0이 됨을 보이시오.증명$t$ 시간에 1인 셀의 개수를 $n_t$, 초기에 1인 셀의 개수를 $m=n_0$, 각 셀의 상태를 $s(r,..

문제 가장 먼저 문제에서 다음을 관찰해야 한다 :어떤 수열이 최종적으로 k개의 그룹으로 나누고, 이 각 그룹의 합이 인덱스 순서대로 $s_1,s_2,\cdots,s_k$ 라고 하자.그러면 처음 수열에서 어떠한 순서로 나누든간에 점수는 $\sum_{1 \leqslant i 즉, 우리는 이제 어떤 수열을 적절하게 m번 나누기만 하면 된다. (위의 관찰 이전에는 그룹을 나누는 순서도 고려했어야 되지만, 이제는 순서는 고려할 필요가 없게 되었다.) $\text{dp}[k][i]$를 "수열의 1~i 까지의 구간에 대해서 k번 나눌때 얻을 수 있는 최대 점수"로 정의하고 점화식을 구해보자.$$\begin{align}\text{dp}[k][i]&= \max_{1 \leqslant k &= \max_{1 \leqsla..

문제 먼저 사탕의 개수를 최대화 하는 문제는 $k$번째 사탕을 $t_k$시간에 먹었다고 할때 $t_k$ 합을 최소화 하는 문제와 동치라는것을 알 수 있다. (문제를 좀더 쉽게 하기 위해 일단 $t_k \leqslant m$이라는 가정을 하자.) 그리고 나서 가장 먼저 $\text{dp}[l][r]$을 사탕의 구간 $l \sim r$ 에 대해서 $t_k$합의 최솟값으로 정의하려고 시도해 볼 수 있다. 하지만 이렇게 하면 적절한 점화식을 구할 수 없다. $k$번째로 먹은 사탕을 시간 $t_k$때 먹었다고 하자. ($t_k$의 정의가 이전과 다음에 주의하자.)우리는 최소화 하려는 대상은 $t_1 + t_2 + \cdots + t_n$ 이다. 그런데 잘 생각해보면 $t_2,t_3,\cdots,t_n$에는 모두 ..

문제 먼저 $w_i \geqslant w_j, h_i \geqslant h_j$ 인 모든 $(i,j)$ 쌍에 대해서 $j$번 직사각형을 제거할 수 있다.이를 통해 $i 그러면 $O(N^2)$ dp로 문제를 풀 수 있다.$\text{dp}[i]$ : 1~i 까지의 직사각형들만 사용해서 문제를 풀 때의 최소 비용$\text{dp}[0] = 0$$\text{dp}[i] = \min_{0 \leqslant j  이제 CHT를 이용해서 $O(N)$ 으로 문제를 풀면 된다.

문제이 문제는 BarkingDog 님의 블로그를 참고했습니다. N개의 정점을 가진 트리에 대해 색깔의 개수가 bound되어 있다고 가정하고 계산해 봅시다. 먼저 다음과 같이 수열을 정의합시다.$S_k$ : k개의 색깔로 최소 비용을 만들수 있는 트리의 정점 개수의 최솟값 수열을 이렇게 정의하는 이유는 다음과 같습니다.$S_k=n$이면 1~n개의 정점을 가진 트리는 색깔을 $k$개 이하만 사용해서 최솟값을 만들 수 있습니다.즉, 우리는 $S_k \geqslant 100,000$ 인 $k$를 찾으면 됩니다. 이제 k개의 색깔로 최소 비용을 만들수 있고, 정점 개수가 최소인 트리에 대해 생각해 봅시다.색깔이 k인 정점이 항상 존재하므로 root를 색깔이 k인 임의의 정점으로 정합시다.root의 색깔이 k이기 ..

문제 문제에서 다음의 조건중 하나가 성립하면 i번 퀘스트를 깰수 있었다.1. STR $\leqslant$ STR[i] 2. INT $\leqslant$ INT [i]  게임 중간의 어떤 상태에 대해 생각해보자.조건 1에 의해 가장 마지막으로 깬 게임을 i번 게임, 조건 2에 의해 가장 마지막으로 깬 게임을 j번 게임이라고 하면, $\text{STR[k]} \leqslant \text{STR}[i]$ 인 k번 게임들과 $\text{ INT [k]} \leqslant \text{INT}[i]$ 인 k번 게임들은 모두 깨져 있거나 깰 수 있다. STR에 의해 정렬된 퀘스트 배열 a와 INT에 의해 정렬된 퀘스트 배열 b가 있다고 하자. 우리가 방금 한 관찰에 따르면 게임을 플레이 하는 도중 퀘스트들의 상태는 ..

문제 이 문제를 풀기 위해서는 가장 먼저 다음과 같은 관찰을 해야된다 :가로등을 위치 순서대로 나타내면 가로등의 상태는 항상 켜짐, 켜짐, ... , 켜짐, 꺼짐, ... , 꺼짐, 켜짐, ... , 켜짐 형태이다. 그 다음으로 해볼수 있는 시도는 $\text{dp}[i][j]$를 i ~ j 번 가로등들에 대한 문제의 답으로 정의하고 점화식을 만드는 것이다. 하지만 이렇게 하면 점화식이 잘 만들어지지 않는다. 그 다음으로 시도해볼수 있는 것은 $\text{dp}[i][j]$를 1 ~ i, j ~ N 번 가로등을에 대한 문제의 답으로 정의하는 것이다. 실제로 이렇게 정의하면 점화식을 어렵지 않게 만들 수 있다. (다만 디테일한 부분이 구현을 어렵게 한다.) 끝