AtCoder Beginner Contest 197

##[A - Rotate](https://atcoder.jp/contests/abc197/tasks/abc197_a)

O(1)

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
 
int main() {
    string s;
    cin >> s;
 
    cout << s[1] << s[2] << s[0] << endl;
 
    return 0;
}
```

##[B - Visibility](https://atcoder.jp/contests/abc197/tasks/abc197_b)

O(HW)
久しぶりに幅優先探索をしたくてqueueを使いました。
下記コードは謝った回答方法です。

AtCoderの解説を参考にした方が良いです。
分かりやすのはループ４つほど用意し全方向をチェックするのが良いです。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
 
char field[100][100];
int done[100][100];
int dx[2] = {1, -1};
int dy[2] = {1, -1};
 
int main() {
    int H, W, X, Y;
    cin >> H >> W >> X >> Y;
 
    for(int x=0; x<H; x++){
        string s;
        cin >> s;
 
        for(int y=0; y<W; y++){
            field[x][y] = s[y];
        }
    }
 
    queue<P> que;
    que.push(P(Y-1, X-1));
 
    int res=0;
    if(field[X-1][Y-1] == '.'){
        done[X-1][Y-1] = 1;
        res++;
    }
    
    while(que.size()>0){
        P p = que.front();
        que.pop();
 
        for(int i=0; i<2; i++){
            int dxx = p.first + dx[i];
            int dyy = p.second;
 
            if(dxx < 0 || dxx >= W) continue;
 
            if(field[dyy][dxx] == '.' && done[dyy][dxx] == 0){
                res++;
                done[dyy][dxx] = 1;
                que.push(P(dxx, dyy));
            }
        }
    }
 
    que.push(P(Y-1, X-1));
    while(que.size()>0){
        P p = que.front();
        que.pop();
 
        for(int i=0; i<2; i++){
            int dxx = p.first;
            int dyy = p.second + dy[i];
 
            if(dyy < 0 || dyy >= W) continue;
 
            if(field[dyy][dxx] == '.' && done[dyy][dxx] == 0){
                res++;
                done[dyy][dxx] = 1;
                que.push(P(dxx, dyy));
            }
        }
    }
 
    cout << res << endl;
 
    return 0;
}
```

模範解答は下記のようになるかと思います。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

char field[100][100];

int main() {
    int H, W, X, Y;
    cin >> H >> W >> Y >> X;

    for(int x=0; x<H; x++){
        string s;
        cin >> s;
        for(int y=0; y<W; y++) field[x][y] = s[y];
    }

    int res=0;
    if(field[Y-1][X-1] == '.') res++;

    for(int x=X; x<W&&field[Y-1][x] == '.'; x++) res++;
    for(int x=X-2; x>=0&&field[Y-1][x] == '.'; x--) res++;
    for(int y=Y; y<H&&field[y][X-1] == '.'; y++) res++;
    for(int y=Y-2; y>=0&&field[y][X-1] == '.'; y--) res++;

    cout << res << endl;

    return 0;
}
```

##[C - ORXOR](https://atcoder.jp/contests/abc197/tasks/abc197_c)

O(2^N)

OR演算とは別名、論理和と呼ばれる論理演算です。
高校数学では数学Aの分野になります。
また基本情報、応用情報では必須知識になる為、エンジニアを目指す、エンジニアの方にとって必須知識となります。

```txt:論理和
C = A | B
0111 = 0011 | 0101
```

```txt:排他的論理和
C = A ^ B
0110 = 0011 | 0101
```

2^Nの問題を回答する際、bit全探索かdfsと呼ばれる深さ優先探索を使用します。
とちらでも回答できますが、今回はdfsを使います。
分岐の条件は、
・任意の区間として現在の区間に追加する。
・任意の区間に追加せず、新しい区間として扱う。
要素数がNになった際、２次元配列の全ての要素に対して論理和、排他的論理和の処理を行います。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
 
ll N;
ll A[20];
 
ll dfs(int n, vector<vector<ll>> v){
    if(n == N){
        ll res = 0;
        for(int i=0; i<v.size(); i++){
            ll sum=0;
            for(int j=0; j<v[i].size(); j++){
                sum = sum | v[i][j];
            }
            res = res ^ sum;
        }
        return res;
    }
 
    vector<vector<ll>> c;
    copy(v.begin(), v.end(), back_inserter(c));
    vector<ll> t;
    t.push_back(A[n]);
    c.push_back(t);
    ll res = dfs(n+1, c);
 
    if(v.size()>0){
        int l = v.size()-1;
        v[l].push_back(A[n]);
        res = min(res, dfs(n+1, v));
    }
 
    return res;
}
 
int main() {
    
    cin >> N;
    rep(i, N) cin >> A[i]; 
    ll res = dfs(0, vector<vector<ll>>());
    cout << res << endl;
 
    return 0;
}
```

綺麗に記載すると下記のコードになります。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

ll N;
ll A[20];

ll dfs(int n, ll orred, ll xorred){

    if(n == N) return xorred ^ orred;

    return min(dfs(n+1, orred | A[n], xorred), dfs(n+1, A[n], xorred ^ orred));
}

int main() {
    
    cin >> N;
    rep(i, N) cin >> A[i]; 

    ll res = dfs(0, 0, 0);

    cout << res << endl;

    return 0;
}
```

##[D - Opposite](https://atcoder.jp/contests/abc197/tasks/abc197_d)

O(1)
回転行列の問題です。
数学２B、数学3Cの分野になります。

```txt:2点の中間の点P
px = (x0 + xn) / 2
py = (y0 + yn) / 2
```

```txt:正N角形の中心角が表す角度をラジアンへ変換
degree = 360.0 / N;
radian = degree * pai / 180.0;
```

x0, y0をそのままdegreeほど回転行列にて計算すると、P点を基準にしないといけないのに原点Oを基準に回転するので計算結果が会わなくなります。
点Pを原点へ移動させます。

```txt:x0,y0を原点基準の座標へ移動
x = x0 - px;
y = y0 - py;
```

これで回転行列にて計算できます。

```txt:回転行列にてdegreeだけ回転させる
x1 = x * cos(radian) - y * sin(radian);
y1 = x * sin(radian) + y * cos(radian);
```

x1, y1は原点を基準にするように移動しています。
点Pが基準になるように再度移動させます。

```txt:x1,y1を原点基準の座標へ変換
x1 = x1 + px
y1 = y1 + py
```

答えが出せました！
プログラムをしましょう！！
ただ実際のコンテストでは残り8分でACする事態で大変焦っていました。
頭では上記のように考察しましたがコードは雑です。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    double N, x0, y0, xN2, yN2;
    cin >> N;
    cin >> x0 >> y0;
    cin >> xN2 >> yN2;

    double px = (xN2 - x0) / 2.0 + x0;
    double py = (yN2 - y0) / 2.0 + y0;
    double degree = 360.0 / N;
    double radian = degree * pai / 180.0;

    double x = x0 - px;
    double y = y0 - py;

    double xx = x * cos(radian) - y * sin(radian);
    double yy = x * sin(radian) + y * cos(radian);

    double dxx = (double)(int)( ceil( xx * pow(10.0,5) ) ) * pow(10.0, -5);
    double dyy = (double)(int)( ceil( yy * pow(10.0,5) ) ) * pow(10.0, -5);
    cout << fixed_setprecision(5) << dxx + px << " " << dyy + py << endl;

    return 0;
}
```

綺麗に記載すると下記のコードになります。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    double N, x0, y0, xn, yn;
    cin >> N;
    cin >> x0 >> y0;
    cin >> xn >> yn;

    double px = (xn + x0) / 2.0;
    double py = (yn + y0) / 2.0;
    double degree = 360.0 / N;
    double radian = degree * pai / 180.0;
    double x = x0 - px;
    double y = y0 - py;
    double x1 = x * cos(radian) - y * sin(radian);
    double y1 = x * sin(radian) + y * cos(radian);

    cout << fixed_setprecision(5) << x1 + px << " " << y1 + py << endl;

    return 0;
}
```

##感想
1120パフォーマンスで最高記録です。
半年間かけて数学１A、数学２B、数学３Cを勉強してきた成果が出ました。
ありがとう、AtCoder。
4月から大学生になる為、今まで通りコンテストに出れる分かりません。
時間があえば参加して緑コーダーを目指していきます。