RUPC2016 day1

http://judge.u-aizu.ac.jp/onlinejudge/contest_problem.jsp?id=RitsCamp16Day1

出た　6位　やったぜ

A:Steelyard

座標が1(または-1)のところに不足分を付ければいいですね

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

#define int long long

typedef long long ll;
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>void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>void chmax(T &t,U f){if(t<f)t=f;}

int L,N;

signed main(){
    int p=0,q=0;
    cin>>L>>N;
    rep(i,N){
        int x,w;
        cin>>x>>w;
        if(x>0)p+=x*w;
        else q+=(-x)*w;
    }

    if(p==q)puts("0");
    else{
        puts("1");
        if(p<q)printf("1 %lld\n",q-p);
        else printf("-1 %lld\n",p-q);
    }
    return 0;
}

B:Hamming Distance

出来るだけ上の桁を0->1して、その後できるだけ下の桁を1->0にする。0->1した桁を1->0しないように気を付ける

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

#define int long long

typedef long long ll;
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>void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>void chmax(T &t,U f){if(t<f)t=f;}

int N,D;
string S;
string T;
signed main(){
    cin>>N>>S>>D;
    T=S;
    int cnt=0;
    for(int i=0;i<T.size()&&cnt<D;i++){
        if(S[i]=='0'){
            cnt++;
            T[i]='1';
        }
    }

    for(int i=T.size()-1;i>=0&&cnt<D;i--){
        if(S[i]=='1'){
            T[i]='0';
            cnt++;
        }
    }

    cout<<T<<endl;
    return 0;
}

C:AddMul

係数が同じやつはまとめた方がいいと分かるのでやる。係数が違うやつをgcdとかでまとめる必要は手元でやった感じだとないっぽいので考えなかった。

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

#define int long long

typedef long long ll;
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>void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>void chmax(T &t,U f){if(t<f)t=f;}

int N;
string S;
int cnt[26];
signed main(){
    cin>>N>>S;
    rep(i,N)if(isalpha(S[i]))cnt[S[i]-'a']++;

    bool f=false;
    int ans=0;

    reps(i,1,10){
        int hoge=count(cnt,cnt+26,i);
        if(hoge==0)continue;
        if(f)ans++;
        else f=true;
        ans+=2*hoge-1;
        if(i!=1){
            if(hoge==1)ans+=2;
            else ans+=4;
        }
    }
    cout<<ans<<endl;
    return 0;
}

D:Scanner

bool値dpする。dp[i+1][j][k][l]:=i番目まで処理して、3台のscannerの仕事量がそれぞれj,k,lという状態にできるかどうか(true or false)、とやりたくなったが、i,j,kが決まればlは一意なので、dp[i+1][j][k]でいい。

#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;}

int N,T[55];
bool dp[2][1050][1050];

signed main(){
    cin>>N;
    rep(i,N)cin>>T[i];

    dp[0][0][0]=true;
    int sum=0;
    rep(i,N){
        rep(j,1000)rep(k,1000){
            if(!dp[i&1][j][k])continue;
            int l=sum-j-k;
            dp[(i+1)&1][j+T[i]][k]=true;
            dp[(i+1)&1][j][k+T[i]]=true;
            dp[(i+1)&1][j][k]=true;
            dp[i&1][j][k]=false;
        }
        sum+=T[i];
    }


    int mi=1<<25;
    rep(i,1000)rep(j,1000)if(dp[N&1][i][j]){
        int k=sum-i-j;
        chmin(mi,max(max(i,j),k));
    }
    cout<<mi<<endl;

    return 0;
}

E:28

まず28数を列挙して、そのあとdp[i+1][j]:=i番目までの28数の積でN/jを表すときの最大の積の数、としてやった。dpの添え字に結構でかい数をいれないといけない感じなのでdp配列にmapを使いました。mapのノード数は高々Nの約数の個数程度で、それは(多分)多くないので行けます。ただ、10^18以下の28数は結構多くて、普通に上記のことをやるとTLEします(28数を降順でソートした場合を除いて)。ので、10^9くらいまでの28数でdpしたあとに少しエイってやると安心できます。

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

#define int long long

typedef long long ll;
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>void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>void chmax(T &t,U f){if(t<f)t=f;}

int N;

vint vec;
void dfs(int n,int d){
    if(d>1000000000ll)return;
    if(n){
        vec.pb(d);
    }
    dfs(n+1,d*10+2);
    dfs(n+1,d*10+8);
}

bool C(int d){
    if(d==1)return true;
    stringstream ss;ss<<d;
    string s=ss.str();
    rep(i,s.size())if(s[i]!='2'&&s[i]!='8')return false;
    return true;
}

signed main(){
    cin>>N;
    if(N==1){
        puts("-1");
        return 0;
    }
    dfs(0,0);
    sort(all(vec));
    reverse(all(vec));

    map<int,int>prev;prev[N]=0;
    for(int i=0;i<vec.size();i++){
        map<int,int>next;
        each(it,prev){
            chmax(next[it->fi],it->se);
            int tmp=it->fi,hoge=0;
            while(tmp%vec[i]==0){
                tmp/=vec[i];hoge++;
                chmax(next[tmp],it->se+hoge);
            }
        }
        prev=next;
    }

    int ans=-1;
    each(it,prev){
        if(C(it->fi))chmax(ans,it->se+(it->fi!=1));
    }
    cout<<ans<<endl;
    return 0;
}

F:Relay

難しかったです・・・

まず、オイラーツアーテクニックをやって、例の列を作っておきます。
木を、頂点0を根とした根つき木として見ます。

任意の頂点vを根とした部分木について、(直径+直径に含まれない辺の中で最長のやつ)をやればいいような気がします。実験なり考察なりをすると上記以外のケースでもっといい解を得られることが分かります。ですが、おおよそ上記の方針でやりました。

ある部分木を見ているとき、その部分木の外にある辺の中で最長のやつは自由に持ってこれます。これは、オイラーツアーの列に辺のコストを載せて、segtreeでやればいいです。(ある頂点がオイラーツア―の列に最初に現れるindexをtin[v],最後に現れるindexをtout[v]とすると、区間[0,tin[v]+1)と区間[tout[v],N)を見ればいい)。この辺を持ってくる場合は、直径にくっつければいいですね。

あとは、下に伸びるパスの中で長いものを3つくらい取ってきて、(2つ選んだやつ+そのパスに含まれない辺の中で最長のやつ)のmaxを取れば大体okな感じだと思います。

(僕の方針だと)あと一つやることがあって、上の方針だけだと、例えば以下のケースで1-6と1-2-5をくっつけて直径とし、直径に含まれていない長さ2の辺3-4をくっつけて長さ18のサイクルを作る感じになると思います。しかし、直径ではないパス6-1-2-3-4に辺2-5をくっつけると長さ19にできます。よって、(根からある葉までのパスの長さ,そのパスに使用していない辺の中で最長の長さ)のpairのなかで、first+secondが最大のやつも計算していかないとつらいです。

一応これでACしましたが、テストケースが弱いらしいので落ちるかもしれません。

#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>void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>void chmax(T &t,U f){if(t<f)t=f;}

struct segtree{
    static const int SEG=1<<17;
    vint dat;
    segtree():dat(SEG*2){}
    void update(int k,int x){
        k+=SEG-1;
        dat[k]=x;
        while(k){
            k=(k-1)/2;
            dat[k]=max(dat[k*2+1],dat[k*2+2]);
        }
    }
    int get(int a,int b,int k=0,int l=0,int r=SEG){
        if(r<=a||b<=l)return 0;
        if(a<=l&&r<=b)return dat[k];
        return max(get(a,b,k*2+1,l,(l+r)/2),get(a,b,k*2+2,(l+r)/2,r));
    }
};

struct edge{
    int to,cost;
    edge(int to,int cost):to(to),cost(cost){}
};

const int SIZE=100000;
int N;
vector<edge>G[SIZE];

int tt,tin[SIZE],tout[SIZE];
segtree seg;
int ans;

struct data{
    int len,cost,id;
    data(int len,int cost,int id):len(len),cost(cost),id(id){}
    bool operator<(const data &d)const{
        return len<d.len;
    }
};

int maxlen[SIZE],maxcost[SIZE];
pint maxpair[SIZE];

inline bool comp(const pint &a,const pint &b){
    return a.fi+a.se>b.fi+b.se;
}

void solve(int v,int p){
    int hoge=max(seg.get(0,tin[v]+1),seg.get(tout[v],segtree::SEG));
    vector<data>vec(3,data(0,0,-1));
    for(auto &e:G[v]){
        if(e.to==p)continue;
        maxlen[e.to]+=e.cost;
        chmax(maxcost[e.to],e.cost);
        maxpair[e.to].fi+=e.cost;
        vec.pb(data(maxlen[e.to],maxcost[e.to],e.to));
    }

    sort(all(vec));reverse(all(vec));
    chmax(ans,vec[0].len+vec[1].len+hoge);
    chmax(ans,vec[1].len+vec[2].len+vec[0].cost);
    chmax(ans,vec[0].len+vec[2].len+vec[1].cost);
    for(int i=2;i<vec.size();i++)chmax(ans,vec[0].len+vec[1].len+vec[i].cost);
    for(auto &e:G[v]){
        if(e.to==p)continue;
        int tmp=vec[0].len;
        if(e.to==vec[0].id)tmp=vec[1].len;
        chmax(ans,tmp+maxpair[e.to].fi+maxpair[e.to].se);

        chmax(maxcost[v],maxcost[e.to]);
        if(comp(maxpair[e.to],maxpair[v]))maxpair[v]=maxpair[e.to];
    }

    vint maxl(vec.size(),0),maxr(vec.size(),0);
    for(int i=0;i<vec.size()-1;i++){
        chmax(maxl[i+1],max(maxl[i],vec[i].cost));
    }
    for(int i=vec.size()-1;i>0;i--){
        chmax(maxr[i-1],max(maxr[i],vec[i].cost));
    }
    rep(i,vec.size()){
        int tmp=max(maxl[i],maxr[i]);
        pint p(vec[i].len,tmp);
        if(comp(p,maxpair[v]))maxpair[v]=p;
    }
    maxlen[v]=vec[0].len;
}

void dfs(){
    stack<int>v,p;
    vint sz(N,1);
    v.push(0);p.push(-1);
    while(v.size()){
        int vv=v.top();v.pop();
        int pp=p.top();p.pop();
        tin[vv]=tt++;
        for(auto &e:G[vv]){
            if(e.to==pp)continue;
            seg.update(tt,e.cost);
            v.push(e.to);
            p.push(vv);
        }
    }

    vint vec,par;
    vec.pb(0);par.pb(-1);
    rep(i,N){
        for(auto &e:G[vec[i]]){
            if(e.to==par[i])continue;
            vec.pb(e.to);
            par.pb(vec[i]);
        }
    }
    for(int i=N-1;i>0;i--){
        sz[par[i]]+=sz[vec[i]];
    }

    rep(i,N)tout[i]=tin[i]+sz[i];

    for(int i=N-1;i>=0;i--){
        solve(vec[i],par[i]);
    }
}



signed main(){
    scanf("%lld",&N);
    reps(i,1,N){
        int a,b;
        scanf("%lld%lld",&a,&b);
        G[i].pb(edge(a,b));
        G[a].pb(edge(i,b));
    }

    dfs();
    printf("%lld\n",ans);
    return 0;
}

G:Paint

頭がいい人じゃないと解けなさそう(適当)

まとめ

去年のRUPC day1はABCEの4完とかだったので若干成長したと思います。