読者です 読者をやめる 読者になる 読者になる

らての精進日記

修行をします

World Code Sprint #4 1/2

www.hackerrank.com

出ました。今回も無事賞金を得られたのでうれしい。今後も毎月開催してくれると財布が潤うので、よろしくお願いします。

Minimum Distances

自明

#include<bits/stdc++.h>
using namespace std;

#define int long long
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
template<class T,class U>inline void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>inline void chmax(T &t,U f){if(t<f)t=f;}

signed main(){
    int n;cin>>n;
    vint a(n);rep(i,n)cin>>a[i];
    int ans=1001001001;
    rep(i,n)reps(j,i+1,n){
        if(a[i]==a[j])chmin(ans,j-i);
    }

    if(ans==1001001001)cout<<-1<<endl;
    else cout<<ans<<endl;
    return 0;
}

Equal Stacks

ある時点で各stackの高さがh1,h2,h3だったとする。一般性を失わずh1>=h2,h3と仮定できる(言い方がかっこいいから一回書いてみたかった)
h1=h2=h3なら、完成。そうでないなら、もう答えをh1にできる見込みがないので、積極的にstack1のtopをpopしていける。
上記の操作をh1=h2=h3となるまで続ければok。

#include<bits/stdc++.h>
using namespace std;

#define int long long
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
template<class T,class U>inline void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>inline void chmax(T &t,U f){if(t<f)t=f;}

signed main(){
    int n[3];rep(i,3)cin>>n[i];
    vint a[3];
    int s[3];
    rep(i,3){
        a[i].resize(n[i]);
        rep(j,n[i])cin>>a[i][j];
        reverse(all(a[i]));
        s[i]=accumulate(all(a[i]),0ll);
    }

    while(true){
        if(s[0]==s[1]&&s[1]==s[2]){
            cout<<s[0]<<endl;
            return 0;
        }

        int i=max(pint(s[0],0),max(pint(s[1],1),pint(s[2],2))).se;
        s[i]-=a[i].back();
        a[i].pop_back();
    }
    return 0;
}

A or B

とりあえず、A|B=Cとなるように操作をする(まだA,Bを最小にしようとはしない)。
ある桁iを見てるとき、A[i]|B[i]=C[i]ならok。
そうでないとき、C[i]=0ならA[i]=B[i]=0となるように操作する。C[i]=1ならB[i]=1とする。(A[i]=1としてもいいけど闇が生えるのでB[i]=1とする)

この時点で操作回数が足りなくなったら不可能。そうでないならとりあえず可能なので、A,Bを最小化していく。
できるだけ上の桁を0にしたいので、上の桁から変更していく。
ある桁iを見る。C[i]=0ならA[i]=B[i]=0となっているので、これ以上何もしなくてもいい。
C[i]=1だとする。A[i]=0,B[i]=1なら何もしない。A[i]=1,B[i]=0なら、A[i]=0,B[i]=1とする。A[i]=1,B[i]=1ならA[i]=0とする。(もちろん、操作回数が許容範囲なら)

まあ操作partは自明だけど、16進と2進の変換とかいろいろめんどくさかったので最初からbit列を渡してくれと思った。

#include<bits/stdc++.h>
using namespace std;

#define int long long
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
template<class T,class U>inline void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>inline void chmax(T &t,U f){if(t<f)t=f;}

string L="0123456789ABCDEF";

void convert(vint &A,string &a){
    reverse(all(a));
    rep(i,a.size()){
        int t=find(all(L),a[i])-L.begin();
        rep(j,4)A[i*4+j]=t>>j&1;
    }
    reverse(all(A));
}

void inverse_convert(string &a,vint &A){
    reverse(all(A));
    a="";
    bool flag=false;
    for(int i=A.size()/4-1;i>=0;i--){
        int t=0;
        rep(j,4)t+=A[i*4+j]<<j;
        if(t||(!t&&(flag||!i))){
            flag=true;
            a.pb(L[t]);
        }
    }
}

int N,K;

void solve(){
    cin>>K;
    string a,b,c;
    cin>>a>>b>>c;
    N=max(a.size(),max(b.size(),c.size()))*4;
    vint A(N),B(N),C(N);

    convert(A,a);
    convert(B,b);
    convert(C,c);

    rep(i,N){
        if((A[i]|B[i])==C[i])continue;
        if(C[i]){
            B[i]=1;K--;
        }
        else{
            if(A[i]){
                A[i]=0;K--;
            }
            if(B[i]){
                B[i]=0;K--;
            }
        }
    }

    if(K<0){
        cout<<-1<<endl;
        return;
    }

    rep(i,N){
        if(C[i]==0)continue;
        if(A[i]==1&&B[i]==1&&K){
            A[i]=0;K--;
        }
        else if(A[i]==1&&B[i]==0&&K>1){
            A[i]=0;B[i]=1;K-=2;
        }
    }


    inverse_convert(a,A);
    inverse_convert(b,B);
    cout<<a<<endl;
    cout<<b<<endl;
}

signed main(){
    int Q;
    scanf("%lld",&Q);
    while(Q--)solve();
    return 0;
}

Roads in HackerLand

任意の非負整数nに対して、2^n>2^0+2^1+...+2^(n-1)であるから、できるだけ指数部の小さい辺だけを通っていきたい。
グラフの最小全域木を取ると、最小全域木に含まれない辺は使う必要がないことがわかる。クラスカル法の過程である辺iを見ているとき、すでにu_iとv_i(辺iの両端)が連結なら、i未満の辺のみを使ってu_iからv_iに到達できる。冒頭の不等式より、辺iを使うよりお得なので、辺iは不要。

入力が木の場合は自明に解けるので、終了。

#include<bits/stdc++.h>
using namespace std;

#define int long long
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
template<class T,class U>inline void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>inline void chmax(T &t,U f){if(t<f)t=f;}

struct UF{
    vint par;
    void init(int n){
        par.resize(n);
        rep(i,n)par[i]=i;
    }
    int find(int x){
        return x==par[x]?x:par[x]=find(par[x]);
    }
    void unite(int x,int y){
        x=find(x);y=find(y);
        par[y]=x;
    }
};

int N,M;
vpint G[100000];
int ans[10000000];

int sz[100000];
void dfs(int v,int p){
    sz[v]=1;
    rep(i,G[v].size()){
        int u,j;
        tie(u,j)=G[v][i];
        if(u==p)continue;
        dfs(u,v);
        sz[v]+=sz[u];
        int tmp=sz[u]*(N-sz[u]);
        while(tmp){
            ans[j]+=tmp&1;
            tmp>>=1;
            j++;
        }
    }
}

signed main(){
    scanf("%lld%lld",&N,&M);
    vector<tuple<int,int,int>>es;
    rep(i,M){
        int a,b,c;
        scanf("%lld%lld%lld",&a,&b,&c);
        a--;b--;
        es.pb(make_tuple(c,a,b));
    }
    sort(all(es));
    UF uf;uf.init(N);
    rep(i,M){
        int a,b,c;
        tie(c,a,b)=es[i];
        if(uf.find(a)==uf.find(b))continue;
        uf.unite(a,b);
        G[a].pb(pint(b,c));
        G[b].pb(pint(a,c));
    }

    dfs(0,-1);
    int u=0;
    rep(i,1000000){
        if(ans[i]>1){
            ans[i+1]+=ans[i]>>1;
            ans[i]&=1;
        }
        if(ans[i])u=i;
    }
    for(int i=u;i>=0;i--){
        printf("%lld",ans[i]);
    }
    puts("");
    return 0;
}

Roads in HackerLandがそこそこ好き。