PS Diary #1

 

 

 

 

 

 

 

Codeforces Round 179 Div. 1.  Greg And Array

 prefix sum

 아무 생각없이 각 쿼리마다 게속 업데이트 해주려고 하면 $O(mk + mn)$이 걸려서 $m,n,k \leq 10^5$인 범위에서 시간초과가 남. 따라서 연산이 사용되는 개수를 구하는 것과 연산을 통해 숫자를 변화시키는 것  각각 $O(m+k), O(m+n)$과 같이 바꿔줘야함. 이때 먼저 구간의 시작과 $($끝+1$)$에 각각 원하는 값을 미리 더해주고 나중에 누적 합을 해주어 처리하면 가능해짐.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int nmax = 1e5, mmax = 1e5;
 
struct operation{
    ll l,r,d;
};
 
ll n,m,k;
ll arr[nmax + 10];
vector<operation> operations;
vector<pii> Querys;
ll applyNum[mmax + 10], add[nmax+1];
 
void solve(){
    for(pii &query : Querys){
        int x = query.first - 1;
        int y = query.second - 1;
        applyNum[x] ++;
        applyNum[y+1] --;
    }
    for(int i=1;i<m;i++){
        applyNum[i] += applyNum[i-1];
    }
    
    for(int i=0;i<m;i++){
        operation o = operations[i];
        add[o.l - 1] += applyNum[i] * o.d;
        add[o.r] -= applyNum[i] * o.d;
    }
    for(int i=1;i<n;i++){
        add[i] += add[i-1];
    }
    
    for(int i=0;i<n;i++){
        cout<<arr[i]+add[i]<<" ";
    }
}
 
int main(){
    cin.tie(0)->ios::sync_with_stdio(0);
    cin>>n>>m>>k;
    for(int i=0;i<n;i++) cin>>arr[i];
    for(int i=0;i<m;i++){
        ll l,r,d; cin>>l>>r>>d;
        operations.push_back({l,r,d});
    }
    for(int i=0;i<k;i++){
        ll x,y; cin>>x>>y;
        Querys.push_back({x,y});
    }
    solve();
}

 

USACO 2020 December. Rectangular Pasture

 sweeping, coordinate-compression

$N \leq 2500$이라서 $O(N^2)$풀이가 가능함. 한 행이나 열에는 소가 최대 1개 밖에 없고, 소 끼리의 상대적인 위치 관계만 중요하기에 룩 배열처럼 좌표 압축해서 생각해도 동일함. 편의상 각 소들이 속한 열들을 기준으로 $0, ... , N-1$까지 번호를 부여하자. 이때 $i$번 소와 $j$번 소를 반드시 포함하면서 $i+1$부터 $j-1$도 포함할 수도 있는 영역 분할의 가짓수는 그림상에서는 $((i$번 소 위에 존재하는 소들의 개수$) + 1)$ $\times$ $((j$번 소 위에 존재하는 소들의 개수$) + 1)$로 표현됨. 따라서 이 값들을 미리 저장해둔다면 $O(1)$만에 구간 $[i,j]$ 사이 소들에 대한 개수를 처리할 수 있고, sweeping을 해주며 모든 $i,j$에 대해 더해주면 결과적으로 $O(N^2)$이 걸림. 값들은 2차원 prefix sum으로 쉽게 구해짐.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int NMAX = 3000;

int N;
vector<pii> cows;
ll arr1[NMAX][NMAX], arr2[NMAX][NMAX];

void input(){
    cin>>N;
    for(int i=0;i<N;i++){
        ll x,y; cin>>x>>y;
        cows.push_back(make_pair(x,y));
    }
}

void solve(){
    sort(cows.begin(),cows.end());
    for(int i=0;i<N;i++){
        for(int j=i-1;j>=0;j--){
            if(cows[j].second > cows[i].second){
                arr1[i][j] = arr1[i][j+1] + 1;
                arr2[i][j] = arr2[i][j+1];
            } else {
                arr1[i][j] = arr1[i][j+1];
                arr2[i][j] = arr2[i][j+1] + 1;
            }
        }
    }
    for(int i=0;i<N;i++){
        for(int j=i+1;j<N;j++){
            if(cows[j].second < cows[i].second){
                arr2[i][j] = arr2[i][j-1] + 1;
                arr1[i][j] = arr1[i][j-1];
            } else {
                arr2[i][j] = arr2[i][j-1];
                arr1[i][j] = arr1[i][j-1] + 1;
            }
        }
    }
    
    ll ans = N + 1;
    for(int i=0;i<N;i++){
        for(int j=i+1;j<N;j++){
            if(cows[i].second < cows[j].second) {
                ans += (arr2[i][j]+1)*(arr1[j][i]+1);
            } else {
                ans += (arr2[j][i]+1)*(arr1[i][j]+1);
            }
            
        }
    }
    cout<<ans;
}

int main(){
    cin.tie(0)->ios::sync_with_stdio(0);
    input();
    solve();
}

 

 

BOJ 1086. 박성원

 bitmask, dp, Euclidean algorithm

$N \leq 15$라서 단순한 brute-forcing은 안되고 bitmasking을 생각할 수 있음. 각 수들의 포함관계를 이진수 형태로 저장하고 나머지를 이용해 dp를 해주면 나머지가 0이고 모두 포함할 때의 경우가 정답이 됨.  나머지를 처리하는 부분이 조금 헷갈리는데 이전 나머지로 가능한 수를 계산하기보다는 다음 나머지로 가능한 수를 계산해서 미리 더해주는 편이 훨씬 나았음. 또 원래는 dp 배열에 지금까지 포함한 숫자들의 개수도 저장해서 구현했었는데 그럴 경우 MLE가 나서 다른 방식으로 처리했어야함. 결과적으로는 $O(K\times 2^N)$임.

#include <bits/stdc++.h>
#define fastio cin.tie(0)->ios::sync_with_stdio(0);
using namespace std;
typedef long long ll;

ll remainder(string num, ll MOD){
    ll rtv = 0, bef = 0;
    for(int i=0;i<num.size();i++){
        rtv = (ll) (num[i]-'0') + 10*bef;
        rtv %= MOD;
        bef = rtv;
    }
    return rtv;
}

ll factorial(int n){
    ll rtv = 1;
    for(int i=1;i<=n;i++){
        rtv *= i;
    }
    return rtv;
}

ll gcd(ll n1, ll n2){
    if(n1 < n2) swap(n1,n2);
    while(1){
        ll r = n1%n2;
        if(r==0) return n2;
		
        n1 = n2;
        n2 = r;
    }
}

ll N,MOD;
vector<ll> remainders, num_length;
vector<string> nums_string;
ll dp[100][1 << 15]{};

void input(){
    cin>>N;
    for(int i=0;i<N;i++){
        string num; cin>>num;
        nums_string.push_back(num);
        num_length.push_back(num.size());
    }
    cin>>MOD;
}

void solve(){
    for(int i=0;i<N;i++){
        ll r = remainder(nums_string[i],MOD);
        remainders.push_back(r);
    }
    
    ll power10[51];
    power10[0] = 1;
    for(int i=1;i<=50;i++){
        power10[i] = 10*power10[i-1];
        power10[i] %= MOD;
    }
    
    for(int i=0;i<N;i++) dp[remainders[i]][1<<i] = 1;

    for (int mask = 1; mask < (1 << N); mask++) {
        for (int r = 0; r < MOD; r++) {
            if (dp[r][mask] == 0) continue;
            for (int i = 0; i < N; i++) {
                if (mask & (1 << i)) continue;
                int next_mask = mask | (1 << i);
                ll next_r = (r * power10[num_length[i]] + remainders[i]) % MOD;
                dp[next_r][next_mask] += dp[r][mask];
            }
        }
    }
    
    ll correctAns = dp[0][(1<<N)-1];
    if(correctAns == 0) cout<<0<<"/"<<1;
    else {
        ll totalAns = factorial(N);
        ll g = gcd(totalAns,correctAns);
        cout<<correctAns/g<<"/"<<totalAns/g;
    }
}

int main(){
    fastio;
    input();
    solve();
}

 

Codeforces. Static Range Queries

 prefix sum, coordinate compression

 좌표 압축, 누적합 문제 치고는 상당히 구현하기 까다로웠던 문제임. 원래 같았으면 위의 Rectangular Pasture 문제 처럼 구간 앞 뒤로 값 더해주고 나중에 prefix sum하는 방식으로 하면 $O(N+Q)$만에 가능해야하는데 0부터 $10^9$까지가 범위라서 MLE일 수밖에 없음. 그래서 쓰지 않는 칸들은 버리고 최소한의 정보만 저장해서 좌표압축을 해주어야하는데 어디를 버리고 어디를 포함할지 헷갈렸음.  숫자를 더해주는 구간들의 시작과 끝, 묻는 쿼리의 시작과 끝들만 남겨두고 사이의 원래 길이도 width로 저장하여 해결했음. 이렇게 되면 최대 $2\times (N+Q)$개의 지점만 저장할 수 있고, $N,Q \leq 10^5$라서 넉넉함. 묻는 쿼리의 시작, 끝을 저장할 생각을 하는게 어려웠음. 이후는 prefix sum으로 잘 처리해줘서 $O(N+Q)$로 구현함.

#include <bits/stdc++.h>
#define fastio cin.tie(0)->ios::sync_with_stdio(0);
using namespace std;
typedef long long ll;
typedef pair<ll,ll> query;
typedef pair<pair<ll,ll>,ll> update;
const int NMAX = 1e5;

ll N,Q;
vector<ll> origin;
vector<query> Querys;
vector<update> Updates;
ll prefix_sum[4*NMAX + 10], width[4*NMAX + 10], value[4*NMAX + 10];

int coordCompressedIdx(ll a){
    return lower_bound(origin.begin(),origin.end(),a) - origin.begin();
}

void solve(){
    sort(origin.begin(),origin.end());
    auto last = unique(origin.begin(), origin.end());
    origin.erase(last, origin.end());
    
    for(int i=1;i<origin.size();i++){
        int idx1 = coordCompressedIdx(origin[i-1]);
        int idx2 = coordCompressedIdx(origin[i]);
        width[idx1] = origin[i] - origin[i-1];
    }
    
    for(update u : Updates){
        ll l = u.first.first;
        ll r = u.first.second;
        ll v = u.second;
        int idxl = coordCompressedIdx(l);
        int idxr = coordCompressedIdx(r);
        value[idxl] += v;
        value[idxr] -= v;
    }
    for(int i=1;i<=2*(N+Q);i++) value[i] += value[i-1];
    
    for(int i=1;i<=2*(N+Q);i++){
        prefix_sum[i] = prefix_sum[i-1] + value[i-1]*width[i-1];
    }
    
    for(query q : Querys){
        int idxl = coordCompressedIdx(q.first);
        int idxr = coordCompressedIdx(q.second);
        cout<<prefix_sum[idxr] - prefix_sum[idxl]<<"\n";
    }
}

int main(){
    fastio;
    cin>>N>>Q;
    for(int i=0;i<N;i++){
        ll l,r,v; cin>>l>>r>>v;
        update u = {{l,r},v};
        Updates.push_back(u);
        origin.push_back(l);
        origin.push_back(r);
    }
    for(int i=0;i<Q;i++){
        ll l,r; cin>>l>>r;
        query q = {l,r};
        Querys.push_back(q);
        origin.push_back(l);
        origin.push_back(r);
    }
    solve();
}