AtCoder Beginner Contest 199(Sponsored by Panasonic)

emeraldgoose·2021년 4월 25일
0

AtCoder

목록 보기
7/17
post-thumbnail

A. Square Inequality


A2+B2<C2A^2+B^2<C^2이 성립하는지 확인하는 문제이다.

#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);
  ll a,b,c;
  cin>>a>>b>>c;
  if(a*a+b*b<c*c) {
    cout<<"Yes";
  }
  else cout<<"No";
  return 0;
}

B. Intersection


1iN1 ≤ i ≤ N인 모든 ii에 대해 AixBiA_i ≤ x ≤ B_ixx의 개수를 구하는 문제이다.

xx의 개수가 0이 되는 조건은 leftright가 초기값이거나 left>right인 경우만 예외처리하면 된다.

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#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<int> a(n),b(n);
  for(int i=0;i<n;i++) cin>>a[i];
  for(int i=0;i<n;i++) cin>>b[i];
  int left=-1,right=1001;
  for(int i=0;i<n;i++) {
    if(left<=a[i]) left=a[i];
    if(right>=b[i]) right=b[i];
  }
  if(left==-1 || right==1001 || left>right) {
    cout<<0;
    return 0;
  }
  cout<<right-left+1;
  return 0;
}

C. IPFL


길이 2N2N인 문자열 S가 주어지는데 다음의 쿼리를 실행한 후의 문자열을 출력하는 문제이다.

  1. T=1, S의 AiA_i번째와 BiB_i번째 문자를 교환
  2. T=2, S의 처음 NN길이의 부분문자열과 뒤의 NN길이의 부분문자열을 교환
    • FLIP -> IPFL

NN의 범위는 1N2×1051≤N≤2×10^5이고 쿼리 QQ의 범위는 1Q3×1051≤Q≤3×10^5이기 때문에 O(QN)O(QN)의 시간 복잡도를 가져서는 안된다.

flip이라는 조건을 넣어서 flip이 되어있지 않으면 입력된 s[a], s[b]를 교환하면 된다.
flip이 되어있다면 xxx<Nx < N인경우, 문자 위치는 x+Nx+N에 있고 반대의 경우 xNx-N에 위치한 것을 이용하면 된다.

이렇게하면 시간 복잡도를 O(N+Q)O(N+Q)를 가지게 된다.

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#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, q;
  string s;
  cin>>n>>s>>q;
  int flip=0;
  while(q--) {
    int t,a,b;
    cin>>t>>a>>b;
    a--,b--;
    if(t==1) {
      if(flip) {
        if(a<n) a+=n;
        else a-=n;
        if(b<n) b+=n;
        else b-=n;      
      }
      swap(s[a],s[b]);
    }
    else flip^=1;
  }
  if(flip) {
    cout<<s.substr(n)<<s.substr(0,n);
  }
  else cout<<s;
  return 0;
}

다른 방법으로는 처음부터 절반의 부분문자열로 나누어 계산하는 방식이 있다.
2번 조건에서 substr함수를 쿼리문에서 사용하지 않기만 해도 AC를 받을 수 있다.

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#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,q;
  string s;
  cin>>n>>s>>q;
  string s1=s.substr(0,n);
  string s2=s.substr(n);
  while(q--) {
    int t,a,b;
    cin>>t>>a>>b;
    a--,b--;
    if(t==1) {
      if(a<n) {
        if(b<n) swap(s1[a],s1[b]);
        else swap(s1[a],s2[b-n]);
      }
      else {
        swap(s2[a-n],s2[b-n]);
      }
    }
    else swap(s1,s2);
  }
  cout<<s1<<s2;
  return 0;
}
profile
https://emeraldgoose.github.io/

0개의 댓글