AtCoder Beginner Contest 197（Sponsored by Panasonic)

A. Rotate

입력되는 문자열 S의 길이가 3일 때, S의 첫번째 글자를 S의 맨 뒤로 보낸 문자열 S’을 출력하는 문제이다.

#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;
    cout<<s.substr(1)<<s[0]<<endl;
    return 0;
}

---

B. Visibility

row H, col W인 크기를 가진 배열이 주어지는데, visible square의 개수를 찾는 문제이다.

visible square는 같은 행, 같은 열에서 장애물 #이 없는 공간을 의미한다.

그냥 4방향 돌면서 장애물을 만났을 때 멈추면 된다.

#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;
 
char map[100][100];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("input.txt","r",stdin);
    int h,w,x,y;
    cin>>h>>w>>x>>y;
    for(int i=0;i<h;i++) {
      string s;
      cin>>s;
      for(int j=0;j<w;j++) map[i][j]=s[j];
    }
    x--, y--;
    int ans=0;
    for(int i=x-1;i>=0;i--) {
      if(map[i][y]=='.') ans++;
      else break;
    }
    for(int i=x+1;i<h;i++) {
      if(map[i][y]=='.') ans++;
      else break;
    }
    for(int j=y-1;j>=0;j--) {
      if(map[x][j]=='.') ans++;
      else break;
    }
    for(int j=y+1;j<w;j++) {
      if(map[x][j]=='.') ans++;
      else break;
    }
    cout<<ans+1;
    return 0;
}

---

C. ORXOR

입력되는 a배열을 여러개의 연속된 구간으로 나눈 후에 구간안의 원소들은 OR연산, 구간끼리는 XOR연산을 하여 계산된 최솟값을 구하는 문제이다.

완전탐색으로 해결할 수 있는 문제이다. editorial에서는 비트를 사용하여 구간을 나눠주고 있다. 비트를 가지고 완전탐색하는 좋은 문제라고 생각한다.

#include <iostream>
#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);
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++) cin>>a[i];
    int ans=2e9;
    for(int i=0;i<1<<(n-1);i++) {
        int res=0;
        int ored=0;
        for(int j=0;j<=n;j++) {
            if(j<n) ored|=a[j];
            if(j==n || (i>>j & 1)) res^=ored, ored=0;
        }
        ans=min(ans,res);
    }
    cout<<ans;
    return 0;
}

---

D. Opposite

짝수개의 점 $n$을 가지고 있는 정다각형의 $p_0$와 $p_{\frac{n}{2}}$가 주어졌을 때, $p_1$를 구하는 문제이다.

어떠한 다각형에 외접하는 원을 그리게 되면 다음의 그림을 생각할 수 있다.

그러면 원의 중심을 $q$라 하면 $\angle p_0qp_1$의 각도를 알 수 있는데 $p_0$를 계산한 각도로 회전시키면 $p_1$을 구할 수 있다.

다음의 회전 공식을 사용하여 $p_1$을 구하면 문제를 해결할 수 있다.

• $\left\lgroup \matrix{x1 \cr x2} \right\rgroup = \left\lgroup \begin{matrix} \cos\theta & -\sin\theta \cr \sin\theta & \cos\theta \end{matrix} \right\rgroup \left\lgroup \begin{matrix} x1 \cr y1 \end{matrix} \right\rgroup$

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#define PI 3.141592
#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;
    double x0,y0,x2,y2;
    cin>>x0>>y0;
    cin>>x2>>y2;
    double cx=(x0+x2)/2, cy=(y0+y2)/2; // center 좌표
    double theta=PI*2/n;
    double dx=x0-cx, dy=y0-cy; // 좌표를 (0,0)으로 옮겨서 변환 후 다시 복구
    double x=cx+dx*cos(theta)-dy*sin(theta);
    double y=cy+dx*sin(theta)+dy*cos(theta);
    cout<<x<<' '<<y<<endl;
    return 0;
}