AtCoder Regular Contest 063 풀이

AtCoder Regular Contest 063 풀이

http://arc063.contest.atcoder.jp/assignments

대회에서 C,D를 풀었고, 대회가 끝난 후에 E를 풀었다.

제출하는 소스 중에 exit(1)을하면 런타임 에러가 뜨고 ,exit(0)을 해야지 런타임이 안 뜬다.

이거 때문에 E를 풀 때 1시간을 허비 했다.

C. 一次元リバーシ / 1D Reversi

C는 간단히 같은 색인 덩어리를 갯수만 구해서 -1하면 된다.

#include <bits/stdc++.h>

using namespace std;

char a[100010];

int cnt;

int main()

{

    scanf("%s",&a[1]);

    int i,n=strlen(&a[1]);

    for(i=1;i<=n;i++)

        if(a[i]!=a[i-1])

            cnt++;

    printf("%d",cnt-1);

}

D. 高橋君と見えざる手 / An Invisible Hand

D도 걍 O(n)에 할 수 있는 쉬운 문제

#include <bits/stdc++.h>

#define INF 2000000000

using namespace std;

int n,a[100010],ans,mn,dap,t;

int main()

{

 //   freopen("input.txt","r",stdin);

    scanf("%d%d",&n,&t);

   int i;

    for(i=1;i<=n;i++)

        scanf("%d",&a[i]);

    mn=INF;

    for(i=1;i<=n;i++){

        ans=max(ans,a[i]-mn);

        mn=min(mn,a[i]);

    }

    mn=INF;

    for(i=1;i<=n;i++){

        if(ans==a[i]-mn)

        dap++;

        mn=min(mn,a[i]);

    }

    printf("%d",dap);

}

E. 木と整数 / Integers on a Tree

자식들의 숫자 홀짝성이 모두 같아야 하므로 홀짝성이 모두 같은 지 판별하고, 어떤 자식에서 가능한 구간 [ lef , rig ](이 정점에 쓸 수 있는 숫자는 lef부터 rig다.)이 있으면 부모는 [ lef-1 , rig+1] 구간의 가능성이 있다. 이 구간들의 교집합을 구하여 부모의 구간으로 정한다. 

처음 구간 초기화는 [-oo,oo]로 해준다.

yes일 때 출력은 정점 1의 가능한 구간 [lef,rig]에서 rig로 시작하여 자식에게 rig-1,rig+1 중 자식의 구간안에 들어오는 숫자를 내려 보내준다. 자식이 받은 숫자(rig-1,rig+1 )를 또 +-해서 가능한 숫자를 자식의 자식에게 준다.

O(n+m)

///exit(0)으로 할 것, 코딩적 습관 보다는 논리를 따라 갈 것 

///  아는 문제는 빨리 풀 수 있도록 노력 할 것

#include<bits/stdc++.h>

#define INF 987654321

#define N 1000050

using namespace std;

struct A{

    int num,lef,rig;

} s[N];

vector<int> V[N];

int n,m,ai[N],bi[N],visit[N],visit2[N];

void dfs(int from)

{

    int to,i,st,ed;

    st=-INF;

    ed=INF;

    visit[from]=1;

    for(i=0;i<V[from].size();i++){

        to=V[from][i];

        if(visit[to]==1)

            continue;

        dfs(to);

        if(s[to].rig!=INF){

            if(ed!=INF && (st-s[to].rig)%2==0){///홀짝성 판별

                printf("No");exit(0);

            }

            if((ed<s[to].lef-1 || s[to].rig+1<st)){///안 겹칠 때

                printf("No");exit(0);

            }

            st=max(st,s[to].lef-1);/// 교집합만들기

            ed=min(ed,s[to].rig+1);

        }

    }

    if(s[from].num!=INF){

        if(st<=s[from].num && s[from].num<=ed){/// 교집합 안에 들어오는가?

            s[from].lef=s[from].rig=s[from].num;

        }

        else{

            printf("No");exit(0);

        }

    }

    else{

        s[from].lef=st;

        s[from].rig=ed;

    }

}

void dfs2(int from,int num)

{

    int i,to;

    visit2[from]=1;

    if(s[from].lef<=num-1 && num-1<=s[from].rig) s[from].num=num-1;

    else s[from].num=num+1;

    for(i=0;i<V[from].size();i++){

        to=V[from][i];

        if(visit2[to]==0) dfs2(to,s[from].num);

    }

}

int main(){

    freopen("input.txt","r",stdin);

    scanf("%d",&n);

    int i,v,p;

    for(i=1;i<n;i++){

        scanf("%d%d",&ai[i],&bi[i]);

        s[i].lef=-INF;

        s[i].rig=s[i].num=INF;

        V[ai[i]].push_back(bi[i]);

        V[bi[i]].push_back(ai[i]);

    }

    s[n].lef=-INF;

    s[n].rig=s[n].num=INF;

    scanf("%d",&m);

    for(i=1;i<=m;i++){

        scanf("%d%d",&v,&p);

        s[v].lef=s[v].rig=s[v].num=p;

    }

    dfs(1);

    dfs2(1,s[1].rig==INF ? 0: s[1].rig+1);

    printf("Yes\n");

    for(i=1;i<=n;i++) printf("%d\n",s[i].num);

}