solve G5~G1 (1)

G5~G1 문제를 각각 1개씩 랜덤으로 풀어보기로 했다.

아래에 나오는 체감 티어는 주관이므로 신뢰하지 말자.

(티어 옆에 +는 보통 그 티어의 난이도보다 어려웠단 뜻이고, -는 쉬웠단 뜻이다.)

Gold 5 : Ordinary Ordinals (BOJ 24930)

풀이 : 수학(+분할정복 거듭제곱)

풀이 시간 : 약 10분

체감 티어 : Gold 5

 

문제를 이쁘게 정리하면 $$ A_{n} = 2A_{n-1} + 1 $$

이 나온다. (단, A_0 = 2, A_1 = 4)

이제 점화식을 일반식으로 바꾸면 $$ A_{n} = 2^{n-1} A_{1} + 2^{n-1} - 1 $$ 

이다. 2^(n-1)은 분할정복으로 O(logN)에 빠르게 구할 수 있으므로 O(logN)에 답을 구할 수 있다.

using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 998244353
typedef long long ll;
ll n, m;
ll POW(ll x, ll y){
    if(y==0)return 1;
    if(y==1)return x;
    if(y&1){
        return POW(x, y-1)%m*x%m;
    }
    else{
        ll P = POW(x, y>>1)%m;
        return P*P%m;
    }
}
int main(){
    fast;
    cin>>n>>m;
    if(n==0)return cout<<(2%m), 0;
    if(n==1)return cout<<(4%m), 0;
    cout<<(POW(2, n-1)%m*4+POW(2, n-1)%m-1)%m;
}

 

Gold 4 : 프랙탈 (BOJ 28294)

풀이 : 수학(등비수열의 합) + 분할정복 거듭제곱 + mod inverse

풀이 시간 : 약 26분

체감 티어 : ? (정해 아닌것으로 추정)

 

이런 문제를 볼때마다 일단 한숨부터 나온다. 변의 길이가 N^a부터 시작해서 N^0까지 간다는 사실을 알 수 있다.

일단 N^0은 논외로 하고, N^a->N^1까지 총 a번 진행했을 때 각각 도형의 둘레를 구한다고 생각해보자.

한 변이 N^x일때를 x단계라고 하자. a단계에서 구해야 하는 둘레의 길이는 N^a * (N - 1)이다. N^a 길이의 선이 N-1개 있다는 것으로 해석할 수 있다.(실제로는 N개이고, 구멍 뚫린 길이를 빼면 N-1개랑 같다.)

비슷하게 a-1단계에서는 N^(a-1) * (N*(N-1)-(N-1))이다. 이는 N^(a-1) 길이의 선이 N*(N-1)-(N-1)개 있다는 것으로 해석할 수 있다. 이 또한 실제로는 N*N-1개이고, 뚫린 길이를 빼면 N*(N-1)-(N-1)이다.

 

위 과정을 직접 해보면서 우리가 구해야 하는 식의 값을 찾아보면

 

$$ \sum_{i=1}^{a}n^{i}(n*(n-1)^{a-i}-(n-1)^{a-i}) $$

$$ = \sum_{i=1}^{a}n^{i}(n-1)^{a-i+1} $$ (n-1)을 묶은 것이다.

위 식은 n^a*(n-1) + n^(a-1)*(n-1)^2 + n^(a-2)*(n-1)^3 + ... 으로, n의 지수는 1씩 감소하고, n-1의 지수는 1씩 증가한다는 것을 알 수 있다. 이 말은, n이 계속 나눠지고, n-1이 계속 곱해진다는 뜻이다. 이는 위 값이 등비수열이 합이라는 뜻이다. (초항:n^a*(n-1), 공비 : (n-1)/n)

따라서 A=n^a*(n-1), R = (n-1)/n이라 하면, 등비수열의 합 공식을 이용하여

$$ \frac{A(R^{a}-1)}{R-1} $$

을 계산하면 된다는 것을 알 수 있다. 나눗셈 연산이 있는데 나머지 연산도 취해야 하므로, mod 10^9+7에서 R-1의 mod inverse를 구하여 곱해주면 된다.

아직 빠진게 있는데, 위 식은 1~a단계까지를 계산한것이다. 0단계는 그냥 n*(n-1)^a이므로 얘까지 더하면 답이 된다.

using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
typedef long long ll;
ll n, a;
ll POW(ll x, ll y){
    if(y==0)return 1;
    if(y==1)return x;
    if(y&1)return POW(x, y-1)%MOD*x%MOD;
    ll p = POW(x, y>>1)%MOD;
    return p%MOD*p%MOD;
}
ll mod_inverse(ll x){
    return POW(x, MOD-2)%MOD;
}
int main(){
    fast;
    cin>>n>>a;
    ll A = POW(n,a)%MOD*(n-1)%MOD;
    ll R = (n-1)%MOD*mod_inverse(n)%MOD;
    cout<<((A*(POW(R,a)%MOD-1)%MOD * mod_inverse(R-1))%MOD + (n%MOD*POW(n-1, a)%MOD))%MOD;
}

 

Gold 3 : 벽 부수고 이동하기 2 (BOJ 14442)

풀이 : BFS

풀이 시간 : 약 10분

체감 티어 : Gold 3

 

일반적인 BFS에서 벽 부순 개수에 따라 차원을 하나 늘려주면 된다.

유명한 테크닉이므로 설명은 생략한다.

using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
typedef long long ll;
ll n, m, K;
bool visited[1010][1010][11];
bool chk[1010][1010];
struct asdf{
    ll x, y, k, d;
};
queue<asdf> q;
ll dx[] = {-1,1,0,0}, dy[] = {0,0,-1,1};
int main(){
    fast;
    cin>>n>>m>>K;
    for(int i = 1 ; i <= n ; i++){
        string s; cin>>s;
        for(int j = 1 ; j <= m ; j++)if(s[j-1]=='1')chk[i][j]=1;
    }
    visited[1][1][0]=1;
    q.push({1,1,0,0});
    ll ans = 1e18;
    while(q.size()){
        auto [x,y,k,d] = q.front();
        q.pop();
        if(x==n and y==m){
            ans = min(ans, d);
            continue;
        }
        for(int i = 0 ; i < 4 ; i++){
            ll nx = x+dx[i], ny = y+dy[i];
            if(nx<1 or ny<1 or nx>n or ny>m)continue;
            if(chk[nx][ny]){
                if(k==K)continue;
                if(visited[nx][ny][k+1])continue;
                visited[nx][ny][k+1]=1;
                q.push({nx,ny,k+1,d+1});
            }
            else{
                if(visited[nx][ny][k])continue;
                visited[nx][ny][k]=1;
                q.push({nx,ny,k,d+1});
            }
        }
    }
    cout<<(ans==1e18?-1:ans+1);
}

Gold 2 : Po (BOJ 20960)

풀이 : Stack (+ lazy segment tree & binary search)

풀이 시간 : 스택 풀이 5분, 레이지 풀이 30분

체감 티어 : Gold 2-

 

1) 스택 풀이

어떤 구간에 일정한 수를 더했다면 구간의 시작점에서 값이 바뀌고, 끝점 다음점에서 값이 바뀐다. 이를 잘 정리해보면 결국 앞에서부터 봤을 때 값이 증가하는 부분, 감소하는 부분에서만 잘 카운트를 해주면 된다. 구체적으로, 스택 내부 원소를 증가하게 유지하면 된다. 그렇게 해서 빠지는 원소 개수만큼 더해주면 된다. 0은 예외이니 조심하자.

using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
typedef long long ll;
ll n;
stack<ll> s;
int main(){
    fast;
    cin>>n;
    ll cnt = 0;
    while(n--){
        ll a; cin>>a;
        if(s.empty()){
            if(a==0)continue;
            s.push(a);
        }
        else{
            while(s.size() and s.top()>a)s.pop(), cnt++;
            if(a==0)continue;
            if(s.size() and s.top()==a)continue;
            s.push(a);
        }
    }
    cout<<cnt+s.size();
}

 

2)레이지 세그 + 이분탐색 풀이

이 풀이는, 주어진 배열에서 실제로 초기 상태인 0, 0, 0, 0, ..., 0을 만드는 풀이이다. 따라서 다음과 같은 과정을 반복하면 된다.

 

인덱스를 앞에서부터 보자. 현재 인덱스를 i라 할때, i가 0이면 그냥 넘기고, 아닐 경우, i 뒤쪽에 있는 가장 앞의 0을 찾는다. 

예를 들어, {1 0 4 0} 에서 1번 뒤에 있는 가장 앞의 0은 2번이며, 3번 뒤에 있는 가장 앞의 0은 4번이다. 이는 세그먼트 트리의 최솟값 쿼리와 이분 탐색으로 O(log^2N)에 구할 수 있다.

이를 구했다면, 0이 아닌 연속된 구간을 얻을 수 있을 것이다. 여기서 값이 0이 되게 최대로 빼야 최적이므로, 이 구간에서의 최솟값을 구간 전체에 빼준다. 이 과정을 반복하면 된다.

using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
typedef long long ll;
ll n;
ll arr[101010];
struct lazyseg{
    struct node{
        ll diff=0, lazy=0;
    };
    vector<node> tree;
    lazyseg(): tree(404040) {}
    void propagate(ll node, ll s, ll e){
        auto &[diff, lazy] = tree[node];
        if(!lazy)return;
        diff += lazy;
        if(s!=e)tree[node*2].lazy += lazy, tree[node*2+1].lazy += lazy;
        lazy=0;
    }
    void upd(ll node, ll l, ll r, ll diff, ll s=1, ll e=n){
        propagate(node,s,e);
        if(e<l or r<s)return;
        if(l<=s and e<=r){
            tree[node].diff += diff;
            if(s==e)return;
            tree[node*2].lazy += diff, tree[node*2+1].lazy += diff;
            return;
        }
        ll mid = s+e>>1;
        upd(node*2,l,r,diff,s,mid); upd(node*2+1,l,r,diff,mid+1,e);
        tree[node].diff = min(tree[node*2].diff, tree[node*2+1].diff);
    }
    ll query(ll node, ll l, ll r, ll s=1, ll e=n){
        propagate(node,s,e);
        if(e<l or r<s)return 1e18;
        if(l<=s and e<=r)return tree[node].diff;
        ll mid = s+e>>1;
        return min(query(node*2,l,r,s,mid), query(node*2+1,l,r,mid+1,e));
    }
} seg1;
int main(){
    fast;
    cin>>n;
    for(int i = 1 ; i <= n ; i++){
        cin>>arr[i];
        seg1.upd(1,i,i,arr[i]);
    }
    ll cnt = 0;
    for(int i = 1 ; i <= n ; i++){
        while(seg1.query(1,i,i) > 0){
            ll l = i, r = n+1;
            while(l+1 < r){
                ll mid = l+r>>1;
                if(seg1.query(1,i,mid) == 0)r = mid;
                else l = mid;
            }
            ll idx = r;
            idx--;
            ll diff = seg1.query(1,i,idx);
            seg1.upd(1,i,idx,-diff);
            cnt++;
        }
    }
    cout<<cnt;
}

 

구현 미스로 시간을 많이 버렸다.

 

Gold 1 : 출근 기록 2 (BOJ 14243)

풀이 : Greedy, Case Work 

풀이 시간 : 56분

체감 티어 : Gold 1++

 

골드1인데 푼 사람수가 적으면 적어도 골드1 이상의 난이도임을 각오해야 한다. 필자의 기여로 인해 이 문제는 P5가 되었다.

어쨌든, 일반적으로는 C->B->A 순으로 출근 순서를 먼저 매기는 것이 좋음을 알 수 있다. 그런데 아닌 경우가 있다.

C->B->A 순으로 주다 보면, C또는 B가 무조건 우선되어야 하는 경우가 생긴다. (A는 당연히 안생긴다) 그 경우는 바로,

....CXXCXXCXXC 또는 ....BXBXBXBXBXB 형태이다. (각각 경우에서 X는 A,B / A,C)

앞에서부터 채우다가 C,B의 개수를 봤을 때 저런 형태가 될 수 밖에 없게 되었을 때, 저렇게 놔주면 된다.

그걸 확인하는 방법은, 0-index 기준으로

C의 경우 : (전체 길이-현재 인덱스-1) = (남은 C개수-1)*3

B의 경우 : (전체 길이-현재 인덱스-1) = (남은 B개수-1)*2

따라서 C의 우선되어야 하는 경우->B의 우선되어야 하는 경우->C->B->A 순으로 배치하면 된다. 그러다가 불가능하면 -1이다.

using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
typedef long long ll;
ll a,b,c;
string s;
int main(){
    fast;
    cin>>s;
    for(auto i : s){
        if(i=='A')a++;
        if(i=='B')b++;
        if(i=='C')c++;
    }
    vector<char> res(s.size(),'#');
    for(ll idx=0 ; idx<s.size() ; idx++){
        if((c-1)*3==s.size()-idx-1){
            bool f=1;
            if(idx>0 and res[idx-1]=='C')f=0;
            if(idx>1 and res[idx-2]=='C')f=0;
            if(idx<s.size()-1 and res[idx+1]=='C')f=0;
            if(idx<s.size()-2 and res[idx+2]=='C')f=0;
            if(f){
                res[idx]='C';
                c--;
                continue;
            }
        }
        if((b-1)*2==s.size()-idx-1){
            bool f=1;
            if(idx>0 and res[idx-1]=='B')f=0;
            if(idx<s.size()-1 and res[idx+1]=='B')f=0;
            if(f){
                res[idx]='B';
                b--;
                continue;
            }
        }
        if(c>0){
            bool f=1;
            if(idx>0 and res[idx-1]=='C')f=0;
            if(idx>1 and res[idx-2]=='C')f=0;
            if(idx<s.size()-1 and res[idx+1]=='C')f=0;
            if(idx<s.size()-2 and res[idx+2]=='C')f=0;
            if(f){
                res[idx]='C';
                c--;
                continue;
            }
        }
        if(b>0){
            bool f=1;
            if(idx>0 and res[idx-1]=='B')f=0;
            if(idx<s.size()-1 and res[idx+1]=='B')f=0;
            if(f){
                res[idx]='B';
                b--;
                continue;
            }
        }
        if(a){
            res[idx]='A';
            a--;
            continue;
        }
        return cout<<-1, 0;
    }
    for(auto i : res){
        cout<<i;
    }
}

 

case work 그리디는 사람이 할 짓이 아닌 것 같다.