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

らての精進日記

修行をします

joi2016予選

よせんでました。とてもたのしかったです。

1問目

適当にやる。やるだけ。

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

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
typedef vector<int>vint;
typedef pair<int,int>pint;

int get(int n){
    vint v(n);
    rep(i,n)cin>>v[i];
    sort(v.rbegin(),v.rend());
    return accumulate(v.begin(),v.begin()+n-1,0);
}

signed main(){
    int a=get(4);
    int b=get(2);
    cout<<a+b<<endl;
    return 0;
}

2問目

バトンのやつ。やるだけ。

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

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
typedef vector<int>vint;
typedef pair<int,int>pint;

int N,M;
int a[100];

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

    for(int k=1;k<=M;k++){
        rep(i,N-1){
            if(a[i]%k>a[i+1]%k)swap(a[i],a[i+1]);
        }
    }

    rep(i,N)cout<<a[i]<<endl;
    return 0;
}

3問目

ロシアの旗のやつ。全探索。

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

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
typedef vector<int>vint;
typedef pair<int,int>pint;

int H,W;
int a[50][50];

signed main(){
    cin>>H>>W;
    rep(i,H)rep(j,W){
        char c;
        cin>>c;
        if(c=='W')a[i][j]=0;
        else if(c=='B')a[i][j]=1;
        else a[i][j]=2;
    }

    int ans=114514;

    for(int i=1;i<H-1;i++){
        for(int j=i+1;j<H;j++){
            int cnt=0;
            for(int y=0;y<i;y++)rep(x,W)if(a[y][x]!=0)cnt++;
            for(int y=i;y<j;y++)rep(x,W)if(a[y][x]!=1)cnt++;
            for(int y=j;y<H;y++)rep(x,W)if(a[y][x]!=2)cnt++;
            ans=min(ans,cnt);
        }
    }

    cout<<ans<<endl;
    return 0;
}

4問目

散歩のやつ。つらら的dp。

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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
typedef vector<int>vint;
typedef pair<int,int>pint;

const int SIZE=100000;


int N,T,Q;
int A[SIZE],D[SIZE];

int dp[SIZE];

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

    rep(i,N){
        if(D[i]!=2)continue;
        if(i==0)dp[i]=A[i]-T;
        else if(D[i-1]==1)dp[i]=max(A[i]-T,A[i]-(A[i]-A[i-1])/2);
        else dp[i]=max(A[i]-T,dp[i-1]);
    }

    for(int i=N-1;i>=0;i--){
        if(D[i]!=1)continue;
        if(i==N-1)dp[i]=A[i]+T;
        else if(D[i+1]==2)dp[i]=min(A[i]+T,A[i]+(A[i+1]-A[i])/2);
        else dp[i]=min(A[i]+T,dp[i+1]);
    }

    while(Q--){
        int x;cin>>x;x--;
        cout<<dp[x]<<endl;
    }
    return 0;
}

5問目

ゾンビのやつ。タクシーみたいに幅やってdijkstraやる。

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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
typedef vector<int>vint;
typedef pair<int,int>pint;

const int SIZE=100000;
const int INF=1001001001001001001LL;

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

int N,M,K,S;
int P,Q;
int C[SIZE];
vector<edge>G[SIZE];
int dist[SIZE];

void bfs(){
    fill_n(dist,N,INF);
    queue<int>que;

    rep(i,K){
        dist[C[i]]=0;
        que.push(C[i]);
    }

    while(que.size()){
        int v=que.front();que.pop();
        rep(i,G[v].size()){
            int to=G[v][i].to;
            if(dist[to]<=dist[v]+1)continue;
            dist[to]=dist[v]+1;
            que.push(to);
        }
    }
}

void build(){
    rep(i,N){
        vector<edge>vec;
        rep(j,G[i].size()){
            int to=G[i][j].to;
            if(dist[to]==0)continue;
            if(to==N-1)vec.pb(edge(to,0));
            else if(dist[to]<=S)vec.pb(edge(to,Q));
            else vec.pb(edge(to,P));
        }
        G[i]=vec;
    }
}

void dijkstra(){
    fill_n(dist,N,INF);
    dist[0]=0;

    priority_queue<pint,vector<pint>,greater<pint> >que;
    que.push(pint(0,0));

    while(que.size()){
        pint p=que.top();que.pop();
        if(dist[p.second]<p.first)continue;
        rep(i,G[p.second].size()){
            edge &e=G[p.second][i];
            if(dist[e.to]<=p.first+e.cost)continue;
            dist[e.to]=p.first+e.cost;
            que.push(pint(dist[e.to],e.to));
        }
    }
}

signed main(){
    cin>>N>>M>>K>>S;
    cin>>P>>Q;
    rep(i,K)cin>>C[i],C[i]--;
    rep(i,M){
        int a,b;cin>>a>>b;a--;b--;
        G[a].pb(edge(b,1));
        G[b].pb(edge(a,1));
    }

    bfs();
    build();
    dijkstra();

    cout<<dist[N-1]<<endl;
    return 0;
}

6問目

お菓子買うやつ。お土産みたいなbitDPを気合で書く。

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

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
typedef vector<int>vint;
typedef pair<int,int>pint;

const int dy[]={0,-1,0,1};
const int dx[]={-1,0,1,0};

int H,W;
int a[1000][1000];

int memo[1000][1000][1<<4];

int dfs(int y,int x,int s){
    if(~memo[y][x][s])return memo[y][x][s];
    if(y+1==H&&x+1==W)return 0;



    int ret=1145141919;

    int lis[4]={0},sum=0;
    rep(i,4){
        int ny=y+dy[i],nx=x+dx[i];
        if(ny<0||ny>=H||nx<0||nx>=W||!a[ny][nx])continue;
        if(i==0&&(s>>1&1))continue;
        if(i==1&&(s>>2&1))continue;
        lis[i]=a[ny][nx];
        sum+=lis[i];
    }

    if(y+1!=H){
        if(sum==0){
            ret=min(ret,dfs(y+1,x,(s&1)*2+4));
        }
        else if(sum==lis[3]){
            ret=min(ret,dfs(y+1,x,(s&1)*2+4)+sum);
        }
        else{
            if(lis[0]){
                ret=min(ret,dfs(y+1,x,(s&1)*2+12)+sum-lis[0]);
            }
            if(lis[1]){
                ret=min(ret,dfs(y+1,x,(s&1)*2+12)+sum-lis[1]);
            }
            if(lis[2]){
                ret=min(ret,dfs(y+1,x,(s&1)*2+4)+sum-lis[2]);
            }
        }
    }
    if(x+1!=W){
        if(sum==0){
            ret=min(ret,dfs(y,x+1,(s>>3&1)*4+2));
        }
        else if(sum==lis[2]){
            ret=min(ret,dfs(y,x+1,(s>>3&1)*4+2)+sum);
        }
        else{
            if(lis[0]){
                ret=min(ret,dfs(y,x+1,(s>>3&1)*4+3)+sum-lis[0]);
            }
            if(lis[1]){
                ret=min(ret,dfs(y,x+1,(s>>3&1)*4+3)+sum-lis[1]);
            }
            if(lis[3]){
                ret=min(ret,dfs(y,x+1,(s>>3&1)*4+2)+sum-lis[3]);
            }
        }
    }
    return memo[y][x][s]=ret;
}

signed main(){

    scanf("%d%d",&H,&W);
    rep(i,H)rep(j,W){
        char c;scanf(" %c",&c);
        if(isdigit(c))a[i][j]=c-'0';
    }

    memset(memo,-1,sizeof(memo));
    printf("%d\n",dfs(0,0,0));

    return 0;
}

まとめ

たのしかった。

広告を非表示にする