9/22 PS

G3~P3 랜디 2개 + 코포 div2 C + 앳코더 민트 1문제

 

(1) 랜디

https://www.acmicpc.net/problem/2694

2694번: 합이 같은 구간

Gold 3.

사용 알고리즘

브루트포스 + O(sqrt(n)) 약수 순회 

 

풀이

O(M)에 합이 x가 되게 분할할 수 있는지를 판별할 수 있다.

또한 배열 전체의 합을 s라 할 때, 분할할 수 있는 값의 후보로는 s의 약수가 가능하다.

따라서 s의 모든 약수에 대하여 O(M)에 판별해줘서 최솟값을 구하면 된다.

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())
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define MOD 1000000007
typedef long long ll;
bool chk(vector<ll> &v, ll p, ll q){
    ll n = v.size();
    ll cur=0,cnt=0;
    for(int i = 0 ; i < v.size() ; i++){
        cur += v[i];
        if(cur>q)return 0;
        if(cur==q)cnt++,cur=0;
    }
    return (cnt==p);
}
void solve(){
    ll n; cin>>n;
    vector<ll> v(n);
    for(auto &i : v)cin>>i;
    ll s = accumulate(all(v),0LL);
    ll ans = 1e18;
    for(ll i = 1 ; i*i <= s ; i++){
        if(s%i==0){
            ll p = i, q = s/i;
            if(chk(v,p,q))ans = min(ans,q);
            if(chk(v,q,p))ans = min(ans,p);
        }
    }
    cout<<ans<<"\n";
}
int main(){
    fast;
    ll t; cin>>t;
    while(t--)solve();
}

 

https://www.acmicpc.net/problem/1754

1754번: 진영 순열

Platinum 3.

사용 알고리즘

dp (bitfield)

 

풀이

배열 A는 중요하지 않고 B가 중요하다.

배열 B를 채울건데, 1부터 시작해서 N-1까지 채운다고 하자. (A0 = F이므로 B_F = 0이다. 얘는 미리 채워놨다고 가정)

i를 채울 때, i 미만의 값들은 이미 B에 존재할 것이다. 채워져 있다면 어차피 i미만이므로 몇인지가 중요하지 않다.

따라서 비트마스킹으로 배열 B의 상태를 표현할 수 있다.

dp[k][bit] := k-진영 순열의 조건을 만족하며 현재 배열 B의 상태는 bit일 때 경우의 수

현재 상태에서 0~n-1 칸 중 비어있는 칸에 아무데나 채워주면 되는데, 이 때 오른쪽 값이 1이면 k도 1 증가한다.

이를 정리하여 dp를 짜면 다음과 같다.

typedef long long ll;
ll dp[21][(1<<20)+1];
ll n,k,F;
ll f(ll K, ll bit){
    if(K>k)return 0;
    if(__builtin_popcount(bit)==n)return (K==k);
    ll &ret = dp[K][bit];
    if(~ret)return ret; ret=0;
    for(int i = 0 ; i < n ; i++){
        if(bit&(1<<i))continue;
        ll w = (i<n-1 and bit&(1<<i+1));
        ret += f(K+w,bit|(1<<i));
    }
    return ret;
}

여기까진 좋은데, 얘를 내면 MLE가 난다. (128MB 양심없다...)

그래서 재귀로 짜면 안되고, 반복문으로 토글링을 해줘야 한다.

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())
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define MOD 1000000007
typedef long long ll;
ll dp[2][(1<<20)+1];
ll n,k,F;
int main(){
    fast;
    cin>>n>>k>>F;
    dp[k&1][(1<<n)-1]=1;
    for(int K = k ; K >= 0 ; K--){
        if(K!=k)dp[K&1][(1<<n)-1]=0;
        for(int bit = (1<<n)-2 ; bit >= 0 ; bit--){
            dp[K&1][bit]=0;
            for(int i = 0 ; i < n ; i++){
                if(bit&(1<<i))continue;
                ll w = (i<n-1 and bit&(1<<i+1));
                dp[K&1][bit] += dp[K+w&1][bit|(1<<i)];
            }
        }
    }
    cout<<dp[0][1<<F];
}

 

(2) Codeforces Div2 C - Another Permutation Problem

Problem - C - Codeforces

사용 알고리즘

Greedy (+구현의 편의를 위한 union find)

 

풀이

최댓값이 1~250^2 사이이므로 최댓값의 상한을 고정하여 생각할 수 있다. (어차피 최댓값이 마지막에 빠질것이므로)

최댓값이 k일때, P_i*i <=k여야 하므로 P_i <= floor(k/i)이다. 그래서 이에 따라 큰 i부터 P_i를 넣어주면 된다. 이 때 수를 중복해서 넣어줄 수 없으므로, union find를 이용해 인접한 수를 union하면서 x 이하의 사용하지 않은 가장 큰 수를 빠르게 찾아준다.

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())
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define MOD 1000000007
typedef long long ll;
struct UF{
    vector<ll> p;
    UF(): p(505,-1){}
    ll find(ll x){
        if(p[x]<0)return x;
        return p[x] = find(p[x]);
    }
    void merge(ll x, ll y){
        x = find(x), y = find(y);
        if(x==y)return;
        p[y]=x;
    }
};
void solve(){
    ll n; cin>>n;
    ll ans=0;
    for(int i = 1 ; i <= n*n ; i++){
        UF uf;
        ll tmp=0,M=0;
        for(int j = n ; j >= 1 ; j--){
            ll x = i/j;
            ll res = uf.find(min(n,x));
            if(!res)continue;
            tmp += res*j;
            M = max(M,res*j);
            uf.merge(res-1,res);
        }
        ans = max(ans,tmp-M);
    }
    cout<<ans<<"\n";
}
int main(){
    fast;
    ll t; cin>>t;
    while(t--)solve();
}

 

(3) ABC251 D - At most 3 (Constestant ver.)

D - At Most 3 (Contestant ver.)

1년 4개월만에 하는 업솔빙

사용 알고리즘

Constructive? Math?

 

풀이

직감이다(?). 대충 300 = 100+100+100에다가 10^6의 세제곱근이 10^2이므로 1, 10^2, 10^4를 각각 100개씩 넣어주면 된다. 뭔소리냐면, 1,2,3,4,5,6,7,....,99,100,200,300,400,...,9900,10000,20000,30000,....,990000,1000000을 채우면 된다. 그러면 100만을 제외하면 6자리 abcdef로 표현이 되고, ab, cd, ef를 각각 표현할 수 있으므로 모든 수를 표현할 수 있다.

    cout<<"300\n";
    for(int i = 1 ; i <= 100 ; i++){
        cout<<i<<" "<<i*100<<" "<<i*10000<<" ";
    }