AtCoder Beginner Contest 199（Sponsored by Panasonic）

A. Square Inequality

$A^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

$1 ≤ i ≤ N$인 모든 $i$에 대해 $A_i ≤ x ≤ B_i$인 $x$의 개수를 구하는 문제이다.

$x$의 개수가 0이 되는 조건은 left와 right가 초기값이거나 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

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

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

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

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

이렇게하면 시간 복잡도를 $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;
}