Codeforces Round #378 (Div. 2)

Codeforces Round #378 (Div. 2)              
 D번까지 풀어서 다 맞았다.

A : Grasshopper And the String
메뚜기가 뛰어 넘는 최대 길이를 구하는 문제
O(N)
처음과 끝부분에 대한 코너 케이스를 잘처리해야 통과된다.
+3 hack

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char a[110];
int n,pos,mx;
int main(){
    int i;
    scanf("%s",&a[1]);
    n=strlen(&a[1]);
    for(i=1;i<=n;i++){
        if(a[i]=='A' ||a[i]=='E' ||a[i]=='I' || a[i]=='O' || a[i]=='U'||a[i]=='Y'){
            mx=max(i-pos,mx);
            pos=i;
        }
    }
    mx=max(mx,n+1-pos);
    printf("%d",mx);
}

B : Parade
sumation으로 처리하면 바로 끝나는 문제 !

#include <bits/stdc++.h>
#define N 100010
using namespace std;
typedef long long ll;
ll a[N],b[N],suma,sumb,mx,v,n;
int main()
{
    scanf("%lld",&n);
    ll i;
    for(i=1;i<=n;i++){
        scanf("%lld %lld",&a[i],&b[i]);
        suma+=a[i];
        sumb+=b[i];
    }
    mx=abs(suma-sumb);
    v=0;
    for(i=1;i<=n;i++){
        suma+=-a[i]+b[i];
        sumb+=a[i]-b[i];
        if(mx<abs(suma-sumb)){
            v=i;
            mx=abs(suma-sumb);
        }
        suma-=-a[i]+b[i];
        sumb-=a[i]-b[i];
    }
    printf("%lld",v);
}

시간복잡도 : O(n);

C : Epidemic in Monstropolis
여기서 많이들 틀렸다.

크기에 대한 제약 조건을 생각하지 않을 때 뒤에서부터 순서대로 sum을 계산하면서 b 배열의 숫자가 가능성이 있는지 판단해야한다.

이웃한 숫자만 먹을 수 있기 때문에 a 배열의 연속한 숫자가 b배열의 하나의 숫자가 된다.
b배열의 하나의 숫자는 t라하고 t가 되는 a 배열의 연속한 숫자들의 수열을 S라하자

이후 판단할 것은 S중 최댓값이 다른 것들을 먹음으로써 t가 될 수 있는지를 판단해야한다.
다른 것을 먹지 못하는 경우는 S의 최댓값의 양 옆 모두 값이 같은 숫자가 있는 경우이다.
S의 값이 같은 모든 최댓값들 중 하나라도 양옆을 먹을 수 있으면  t를 만들 수 있다.

corner case : S의 크기가 1일 때

#include <bits/stdc++.h>
#define N 505
using namespace std;
typedef long long ll;
ll cnt,a[N],b[N],na,nb;
vector<ll> c,ans1;
vector<char> cc;
void input()
{
    scanf("%lld",&na);
    ll i;
    for(i=1;i<=na;i++)
        scanf("%lld",&a[i]);
    scanf("%lld",&nb);
    for(i=1;i<=nb;i++)
        scanf("%lld",&b[i]);
}
void process()
{
    ll i,v=nb,sum=0,k,j,ck;
    c.push_back(na+1);
    for(i=na;i>=1;i--){
        sum+=a[i];
        if(sum==b[v]){
            c.push_back(i);
            v--;
            sum=0;
        }
        else if(sum>b[v]){
            printf("NO");
            return;
        }
    }
    if(v!=0){
        printf("NO");
        return;
    }
    for(i=1;i<c.size();i++){
        ll mx=0;
        if(c[i-1]-c[i]==1)
           continue;
        for(k=c[i];k<=c[i-1]-1;k++){
            mx=max(a[k],mx);
        }
        ck=0;
        for(k=c[i];k<=c[i-1]-1;k++){
            if(a[k]==mx){
                if(!((c[i]<=k-1 && a[k-1]!=mx) || (k+1<=c[i-1]-1 && a[k+1]!=mx))){
                    continue;
                }
                ck=1;
                if(k+1<=c[i-1]-1 && a[k+1]!=mx){
                    for(j=k;j<c[i-1]-1;j++){
                        ans1.push_back(k);
                        cc.push_back('R');
                    }
                    for(j=k;j>=c[i]+1;j--){
                        ans1.push_back(j);
                        cc.push_back('L');
                    }
                }
                else{
                    for(j=k;j>=c[i]+1;j--){
                        ans1.push_back(j);
                        cc.push_back('L');
                    }
                    for(j=1;j<=c[i-1]-1-k;j++){
                        ans1.push_back(c[i]);
                        cc.push_back('R');
                    }
                }
                break;
            }
        }
        if(ck==0){
            printf("NO");
            return;
        }
    }
    printf("YES\n");
    for(i=0;i<ans1.size();i++){
        printf("%lld %c\n",ans1[i],cc[i]);
    }
}
int main()
{
    input();
    process();
}


D : Kostya the Sculptor

vector v;
붙이려는 한 면을 S라하고 그 면의 작은 변을 a, 큰 변을 b라 한다.그리고 나머지 한 변을 c라고 한다.

v. first. first = a
v. first. second = b
v. second. first =  c
v. second. second = i번째
이걸 정렬한 상태에서 같은 a,b 상태 중 가장 큰 거 두 개를 더해주면 된다.
v에 넣어 줄 때 주의 할 점은 a,b,c 중 같은 길이의 변이 있으면 중복되지 않도록 넣어 줘야 한다는 것이다.

#include <bits/stdc++.h>
#define N 100010
#define INF 2000000000
using namespace std;
typedef long long ll;
vector<pair<pair<int,int> ,pair<int,int> > > v;
set<pair<int,int> > S;
vector<int> a[N];
int n,mx=-1,ck,f1,f2,v1,v2;
void in(int x,int y,int z,int w)
{
    v.push_back(make_pair(make_pair(x,y),make_pair(z,w)));
    S.insert(make_pair(x,y));
}
void input()
{
    int n;
    scanf("%d",&n);
    int i,x,y,z;
    for(i=1;i<=n;i++){
        scanf("%d%d%d",&x,&y,&z);
        a[i].push_back(x);
        a[i].push_back(y);
        a[i].push_back(z);
        sort(a[i].begin(),a[i].end());
        if(a[i][0]==a[i][1] && a[i][1]==a[i][2]){
            in(a[i][0],a[i][1],a[i][2],i);
        }
        else if(a[i][0]==a[i][1]){
            in(a[i][0],a[i][1],a[i][2],i);
            in(a[i][0],a[i][2],a[i][1],i);
        }
        else if(a[i][1]==a[i][2]){
            in(a[i][0],a[i][2],a[i][1],i);
            in(a[i][1],a[i][2],a[i][0],i);
        }
        else{
            in(a[i][0],a[i][1],a[i][2],i);
            in(a[i][0],a[i][2],a[i][1],i);
            in(a[i][1],a[i][2],a[i][0],i);
        }
        if(mx<a[i][0]){
            mx=a[i][0];
            ck=0;
            v1=i;
        }
    }
}
void process()
{
    int i,j,p1,p2,mn;
    pair<int,int> tmp;
    pair<pair<int,int>,pair<int,int> > tt;
    sort(v.begin(),v.end());
    set<pair<int,int> > ::iterator it;
    for(it=S.begin();it!=S.end();it++){
        tmp=(*it);
        tt.first.first=tmp.first;
        tt.first.second=tmp.second;
        tt.second.first=-INF;
        p1=lower_bound(v.begin(),v.end(),tt)-v.begin();
        tt.first.first=tmp.first;
        tt.first.second=tmp.second;
        tt.second.first=INF;
        p2=upper_bound(v.begin(),v.end(),tt)-v.begin();
        if(p2-p1>=2){
            mn=min(v[p2-2].second.first+v[p2-1].second.first,min(tmp.first,tmp.second));
            if(mx<mn){
                mx=mn;
                ck=1;
                v1=v[p2-2].second.second;
                v2=v[p2-1].second.second;
            }
        }
    }
}
void output()
{
    int i;
    if(ck==0)
        printf("1\n%d",v1);
    else
        printf("2\n%d %d",v1,v2);
}
int main()
{
    input();
    process();
    output();
}


대회 중에사실 왜 set을 이용하여 짰는지 모르겠지만 더 쉬운 풀이가 있다.
v 소트 이후 연속한 두개가 a,b가 같은지 판단하고 연속한 v의 c의 합 중 최댓값을 구하면 정답이다.