ZONe Energy Programming Contest

A. UFO Invasion

길이 12인 문자열 S가 주어질 때, ZONe문자열이 몇번 들어가 있는지 확인하는 문제

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF=1e10+1;

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  //freopen("input.txt","r",stdin);
  string s;
  cin>>s;
  int ans=0;
  for(int i=0;i<9;i++) {
    string t=s.substr(i,4);
    if(t=="ZONe") ans++;
  }
  cout<<ans;
  return 0;
}

---

B. Sign of Friendship

타워에서 UFO를 보기위해 얼마나 높이 올라가야 하는지 계산하는 문제이다. 사다리꼴 닮음을 이용하여 계산할 수 있다.

장애물이 존재하므로 장애물마다 올라가야 하는 높이를 계산하고 그 중 최댓값을 출력하면 된다.

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#define endl '\n'
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF=1e10+1;

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  //freopen("input.txt","r",stdin);
  int n;
  double D,H;
  cin>>n>>D>>H;
  double ans=0;
  for(int i=0;i<n;i++) {
    double d,h;
    cin>>d>>h;
    ans=max(ans,(D*h-d*H)/(D-d));
  }
  cout.precision(4);
  cout<<fixed;
  cout<<ans;
  return 0;
}

---

C. MAD TEAM

이 문제는 어려워서 다른 해설을 참고했다. 링크

어떤 값 x가 팀의 능력치가 되려면 선택한 3명의 능력치의 최댓값들 중 최소값이어야 한다.

또한, 어떤 사람의 능력치의 값이 x보다 크다면 1, 작다면 0으로 표현할 수 있다.

• x=3, ap={4, 2, 1, 3, 5} -> {1, 0, 0, 1, 1}로 표현할 수 있다.

만약 x가 팀의 능력치라고 한다면, 위와 같이 변환된 3명의 능력치를 모두 OR연산한 값이 {1, 1, 1, 1, 1}이어야한다.

왜냐하면, 3명의 능력치 중 한명이라도 x보다 크다면 최댓값은 그 값이 되기 때문이다. 팀의 능력치는 최댓값들 중 최솟값이 x면 된다.

예를들어, 아래와 같은 입력이 들어왔다고 가정하자.

3
3 9 6 4 6
6 9 3 1 1
8 8 9 3 7

x는 3이라고 가정하고 1과 0으로 표현하면 다음과 같다.

1 1 1 1 1
1 1 1 0 0
1 1 1 1 1

3명을 OR한 값이 {1, 1, 1, 1, 1}이므로 팀의 능력치는 x=3이 될 수 있다.

반면에 x가 5라고 가정하자.

0 1 1 0 1
1 1 0 0 0
1 1 1 0 0

3명을 OR한 값이 {1, 1, 1, 0, 1}이므로 팀의 능력치는 5가 될 수 없다. 이 값은 최솟값이 5보다 작다는 의미를 가지고 있다.

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#define endl '\n'
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF=1e10+1;

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  //freopen("input.txt","r",stdin);
  int n;
  cin>>n;
  vector<vector<int> > ap(n,vector<int>(5,0));
  for(int i=0;i<n;i++) {
    for(int j=0;j<5;j++) cin>>ap[i][j];
  }
  int l=0, r=1e9+1;
  while(l+1<r) {
    int mid=(l+r)/2;
    vector<int> v;
    for(int i=0;i<n;i++) {
      int x=0;
      for(int j=0;j<5;j++) {
        if(ap[i][j]>=mid) x|=1<<j;
      }
      v.push_back(x);
    }
    // 배열 v 중복제거
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    bool ok=false;
    // 3명을 골라야 하므로
    for(int i=0;i<v.size();i++) {
      for(int j=0;j<=i;j++) {
        for(int k=0;k<=j;k++) {
          if((v[i]|v[j]|v[k])==(1<<5)-1) ok=true;
        }
      }
    }
    if(ok) l=mid;
    else r=mid;
  }
  cout<<l;
  return 0;
}

---

D. Message from Aliens

주어진 문자열에서 R이 나오는 경우 뒤집는 조건이 존재한다.
문자열의 길이가 $ 5 \times 10^5$의 범위이므로 최악의 경우 $O(|S|^2)$의 시간 복잡도를 가지게 된다.
이전 문제에서 flip이라는 변수를 사용하여 구현하는 것을 이용했다.

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#define endl '\n'
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF=1e10+1;

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  //freopen("input.txt","r",stdin);
  string s;
  cin>>s;
  string T;
  int flip=0;
  for(char c : s) {
    if(c=='R') {
      flip^=1;
    }
    else {
      if(!flip) {
        if(c==T.back()) T.pop_back();
        else T.push_back(c);
      }
      else {
        if(c==T.front()) T=T.substr(1);
        else T=c+T;
      }
    }
  }
  if(!flip) cout<<T;
  else {
    reverse(T.begin(),T.end());
    cout<<T;
  }
  return 0;
}