2016-2017 ACM-ICPC Asia-Bangkok Regional Contest

Date : 2020.02.03 - 2020.02.04

PM 10:40 ~ AM 3:40

Participants : L0TUS, _Karuna, dillon0108

Codeforces URL

Baekjoon URL

PDF

Scoreboard

Scoreboard (Virtual)

코드포스 버추얼 68위, 7문제 중에서는 2등으로 마감했다.

Result

7 solved : L -> B - > I -> D -> G -> C -> H (penalty: 838)

 

A. WSI Extreme

 

B. Average (solved at. 42 min)

문제

버추얼에서는 3번째, 리저널에서 4번째로 많이 풀린 쉬운 문제이다. 당시에는 dillon이 한번에 AC를 받았다. 정수론적인 방법을 이용해 빠르게 푸는 코드가 백준 상위권에 위치해 있는데 나중에 공부해봐야겠다.

풀이

문제의 조건 중, 평균이 여러 명 있으면 각각 카운팅된다는 내용이 있으므로 어떤 사람 A가 평균과 일치하는 점수를 몇번 매겼는지 세준 다음 사람의 수 N을 곱해준 것이 답이 된다. 사람 A가 점수 X를 매겼을 때 나머지 N-1명의 점수의 합이 총 (N-1)*X이 되도록 하는 가짓수를 X에 대해 모두 구해주면 되고 이는 다음과 같이 나타낼 수 있다. $$DP(사람의 수,점수의 합) = DP[N][X] = \sum_{K=0}^{min(X,M)}DP[N-1][X-K] $$

DP를 빠르게 계산하기 위해 다음과 같이 변환해 준다. M은 매길 수 있는 점수의 최댓값이다.

\[D[N][X] = \left\{\begin{matrix}D[N][X-1] + D[N-1][X] - D[N-1][X-M-1]\quad(X>=M+1) \\ D[N][X-1] + D[N-1][X]\quad(X<=M) \end{matrix}\right.\]

만약 이대로 DP값을 구해 각 테스트 케이스마다 답을 계산해준다면 시간복잡도는 $O(TN^{2}K)$이고,

위 DP식을 구할 때 M을 1부터 200까지 바꿔가면서 입력이 N,K일 때의 답인 ans[N][K]을 전처리한 후 각 테스트 케이스마다 미리 저장된 값을 출력한다면 시간복잡도는 $O(N^{2}K^{2})$이다.

단순 계산으로는 5배 차이가 나게 되지만 실제 대회 데이터가 널널한 편이라 두 방법 모두 AC를 받을 수 있다.

코드 $O(TN^{2}K)$

#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MOD = 1e9+7;
int N,K;
ll D[60][12000],ans;
int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0);
    while(1){
        cin >> N >> K;
        if(!N&&!K) break;
        for(int n=1; n<N; n++) D[n][0] = 1;
        for(int k=0; k<=K; k++) D[1][k] = 1;
        for(int n=2; n<N; n++){
            for(int k=1; k<=(N-1)*K; k++){
                if(k>=K+1) D[n][k] = (D[n][k-1]+D[n-1][k]-D[n-1][k-K-1]+MOD)%MOD;
                else D[n][k] = (D[n][k-1]+D[n-1][k])%MOD;
            }
        }
        for(int i=0; i<=K; i++){
            ans = (ans+D[N-1][(N-1)*i]*N)%MOD;
        }
        cout << ans << '\n';
        ans = 0;
        for(int n=0; n<N; n++)
            for(int k=0; k<=(N-1)*K; k++) D[n][k] = 0;
    }
}

코드 $O(N^{2}K^{2})$

#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MOD = 1e9+7;
int N,K;
ll D[60][12000],ans[60][201];
int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0);
    for(int n=1; n<60; n++) D[n][0] = 1;
    for(int m=1; m<=200; m++){
        for(int n=1; n<60; n++){
            for(int k=1; k<=n*m; k++){
                if(k>=m+1) D[n][k] = (D[n][k-1]+D[n-1][k]-D[n-1][k-m-1]+MOD)%MOD;
                else D[n][k] = (D[n][k-1]+D[n-1][k])%MOD;
            }
            for(int i=0; i<=m; i++) ans[n][m] = (ans[n][m]+D[n][n*i])%MOD;
        }
    }
    while(1){
        cin >> N >> K;
        if(!N&&!K) break;
        cout << ans[N-1][K]*N%MOD << '\n';
    }
}

 

C. Big Bang (solved at. 171 min)

 

D. Find C (solved at. 88 min)

 

E. ACM Tax

 

F. Dictionary Game

 

G. Binary Strings (solved at. 162 min)

문제

버추얼에서는 4번째, 리저널에서 5번째로 많이 풀린 문제로, Solved.ac 기준 D5에 등록된 것과는 달리 높은 정답률을 보인다. 당시에는 dillon이 문제를 보고 관찰한 내용을 들려주었는데 karuna랑 내가 알고 있던 내용이라 dillon에게 관련 지식을 알려주자 그대로 구현에 들어가서 맞았다.

 

풀이

1이 연속하지 않는 binary string의 개수 $D[L]$은 , string의 길이를 L로 두고 (string의 시작이 '10'인 경우) + (string의 시작이 '0'인 경우)로 나누어서 생각하면 $D[L] = D[L-1] + D[L-2], D[1] = 2, D[2] =3$ 이라는 피보나치 꼴의 점화식을 얻을 수 있다. $D[X]=F_{X+1}$ 이고, X번째 피보나치 수는 아래 행렬의 1행 1열의 값과 같다.

$$F_{X} = \begin{pmatrix} 1&1 \\\ 1&0 \end{pmatrix}^X  = \boldsymbol{F}^X$$

편의상 행렬의 1행 1열의 값 대신 행렬을 이용해 주어진 식을 변환하면 다음과 같다. 이때 KA와 KB는 주어진 조건을 만족하는 최소, 최대 수이다.

\[\sum_{X=A}^{B}D[KX] = \sum_{X=A}^{B}F_{KX+1} = \sum_{X=A}^{B}\boldsymbol{F}^{KX+1} = \boldsymbol{F}^{AX+1}\sum_{X=0}^{B-A}\boldsymbol{F}^{KX}\]

 

이처럼 거듭제곱이 연속된 항을 정리하는 방법은 항등원을 1대신 $\boldsymbol{E}$로 사용해주면 기존과 다를 바가 없다.

$$\sum_{X=0}^{B-A}\boldsymbol{F}^{KX}=(\boldsymbol{F}^{K}-\boldsymbol{E})^{-1}(\boldsymbol{F}^{K}-\boldsymbol{E})\sum_{X=0}^{B-A}\boldsymbol{F}^{KX}=(\boldsymbol{F}^{K}-\boldsymbol{E})^{-1}(\boldsymbol{F}^{K(B-A+1)}-\boldsymbol{E})$$

띠라서 다음 값을 로그 스케일 시간 복잡도 안에 구해주면 된다.

$$\boldsymbol{F}^{AX+1}(\boldsymbol{F}^{K}-\boldsymbol{E})^{-1}(\boldsymbol{F}^{K(B-A+1)}-\boldsymbol{E})$$

코드

행렬을 다루는 법과 모듈러 연산 때문에 구현에 애를 먹을 수 있는데 각각 구조체와 함수를 통해 관리해 주면 실수를 줄일 수 있다.

#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long ll;
const int MOD = 1e9+7;
struct Mat{
    ll a,b,c,d;
};
Mat A = {1,1,1,0}, E = {1,0,0,1};

ll mul(ll X, ll Y)
{
    return (X*Y%MOD+MOD)%MOD;
}

ll add(ll X, ll Y)
{
    return ((X+Y)%MOD+MOD)%MOD;
}

ll inv(ll X)
{
    ll T = X, R = 1, K = MOD-2;
    while(K){
        if(K%2) R = mul(R,T);
        T = mul(T,T);
        K/=2;
    }
    return R;
}

Mat mulM(Mat X, Mat Y)
{
    Mat M;
    M.a = add(mul(X.a,Y.a),mul(X.b,Y.c));
    M.b = add(mul(X.a,Y.b),mul(X.b,Y.d));
    M.c = add(mul(X.c,Y.a),mul(X.d,Y.c));
    M.d = add(mul(X.c,Y.b),mul(X.d,Y.d));
    return M;
}

Mat subM(Mat X, Mat Y)
{
    Mat R;
    R.a = add(X.a,-Y.a);
    R.b = add(X.b,-Y.b);
    R.c = add(X.c,-Y.c);
    R.d = add(X.d,-Y.d);
    return R;
}

Mat powM(Mat M, ll K)
{
    Mat T = M, R = E;
    while(K){
        if(K%2) R = mulM(R,T);
        T = mulM(T,T);
        K/=2;
    }
    return R;
}

Mat invM(Mat M)
{
    Mat R;
    ll X = inv(add(mul(M.a,M.d),-mul(M.b,M.c)));
    R.a = mul(X,M.d);
    R.b = mul(X,-M.b);
    R.c = mul(X,-M.c);
    R.d = mul(X,M.a);
    return R;
}

int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0);
    int T;
    cin >> T;
    ll L, R, K;
    for(int i=1; i<=T; i++){
        cin >> L >> R >> K;
        L = (L+K-1)/K;
        R = R/K;
        Mat X = subM(powM(A,(R-L+1)*K),E);
        Mat Y = invM(subM(powM(A,K),E));
        Mat Z = powM(A,L*K+1);
        cout << "Case " << i << ": " << mulM(mulM(X,Y),Z).a << '\n';
    }
}

 

H. Witcher Potion (solved at. 192 min)

문제

버추얼에서는 5번째로 많이 풀린 문제, 리저널에서는 3번째로 많이 풀린 문제였다.

Solved.ac 난이도 기준 P5에 해당하는 난이도 답게 별 무리없이 풀어낼 수 있는 문제였으나...

사소한 코딩 실수로 첫 제출 86분, 맞은 제출 192분으로 패널티에 큰 기여를 하고 말았다.

풀이

 $N\le8$ 에서 지금까지 먹은 포션을 2^8가지 상태를 통해 표현하는 bit DP를 바로 떠올릴 수 있다. 또한 $K\ge10$ 이라는 조건 때문에 잡을 수 있는 몬스터의 수가 최대 90마리이므로 (먹은 포션, 현재 에너지, 잡은 몬스터의 수)를 상태로 잡고 DP값을 '주어진 상태에서 가능한 최소 독성'으로 정하면 $DP[x][e][cnt]$에서 $DP[x+(1<<i)][e'][cnt+1]$와 $DP[x][e'][cnt+1]$로 전파하면서 계산해주면 된다. 물론 현재 독성을 상태로 잡고 DP값은 최대 에너지로 정해도 무방하다.

 가능한 상태의 수는 2^N*(최대 에너지)*(잡을 수 있는 몬스터의 최대값)이고 먹을 수 있는 포션의 종류가 N개이므로 한 항을 계산할 때는 $O(N)$만큼의 시간이 든다. 따라서 총 시간복잡도는 $O(N*2^N*100*90)$

코드

for(i=0; i<N; i++)에서 N 대신 8을 집어넣는 실수를 찾지 못해 제출이 2시간 가량 늦어졌다.

#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MN = 1e5+5;
int C,K,M,N,E[8],P[8],t,D[500][200][100],nexte,nextt,cnt;
bool ch;

int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0);
    cin >> C;
    while(C--){
        cin >> K >> M >> N;
        for(int i=0; i<N; i++) cin >> E[i];
        for(int i=0; i<N; i++) cin >> P[i];
        for(int cnt=0; cnt<100; cnt++)
            for(int x=0; x<(1<<N); x++)
                for(int e=1; e<=100; e++)
                    D[x][e][cnt] = 100;
        D[0][100][0] = 0;
        cnt = -1;
        ch = 1;
        while(ch){
            cnt++;
            ch = 0;
            for(int x=0; x<(1<<N); x++){
                for(int e=1; e<=100; e++){
                    if(D[x][e][cnt]==100) continue;
                    t = D[x][e][cnt];
                    for(int i=0; i<N; i++){
                        if(x&(1<<i)) continue;
                        if(t+P[i]>=100||e+E[i]<=K) continue;
                        ch = 1;
                        nexte = min(100,e+E[i])-K;
                        nextt = max(0,t+P[i]-M);
                        D[x+(1<<i)][nexte][cnt+1] = min(D[x+(1<<i)][nexte][cnt+1],nextt);
                    }
                    if(e>K){
                        ch = 1;
                        nexte = e-K;
                        nextt = max(0,t-M);
                        D[x][nexte][cnt+1] = min(D[x][nexte][cnt+1],nextt);
                    }
                }
            }
        }
        cout << cnt << '\n';
    }
}

 

I. Sky Tax (solved at. 47 min)

 

J. Printing Press

 

K. Expected Number of Connected Components 

 

L. Coordinates (solved at. 16 min)