AtCoder Beginner Contest 270

## [A - 1-2-4 Test](https://atcoder.jp/contests/abc270/tasks/abc270_a)

O(1)
それぞれの問題の配点は 1 点、2 点、4 点。
2^0 = 1
2^1 = 2
2^2 = 4
また、どちらかが正解している問題をすぬけ君は正解しています。
よって、or演算を使用します。

```
101 | 100 = 101
000 | 001 = 001
000 | 000 = 000
```

高橋君は A 点、青木君は B 点をor演算して、1~3bitの各ビットが1になっている問題を判定します。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; 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() {
    int a, b;
    cin >> a >> b;
    cout << (a | b) << endl;
    return 0;
} 
```

## [B - Hammer](https://atcoder.jp/contests/abc270/tasks/abc270_b)

O(1)
0, X, Y, Zを並び替えるパターンは、2^4なので32パターンあります。
しかし、（0 < X && X < Y）はZを考慮しなくて良いです。
考察すると９パターンを記載して、後は全部−１でよさそうです。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; 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() {
    int X, Y, Z;
    cin >> X >> Y >> Z;

    if(0 < Z && Z < Y && Y < X){
        cout << abs(X) << endl;
    }else if(0 > Z && 0 < Y && Y < X){
        cout << abs(X) + abs(Z) * 2 << endl;
    }else if(0 < X && Y > X){
        cout << abs(X) << endl;
    }else if(0 < X && Y < 0){
         cout << abs(X) << endl;
    }else if(0 > X && Y < X){
        cout << abs(X) << endl;
    }else if(0 > X && 0 < Y){
        cout << abs(X) << endl;
    }else if(0 > X && Y > X && Z > Y && Z < 0){
        cout << abs(X) << endl;
    }else if(0 > X && Y > X && Z > Y && 0 < Z){
        cout << abs(X) + abs(Z) * 2 << endl;
    }else{
        cout << -1 << endl;
    }

    return 0;
}
```

## [C - Simple path](https://atcoder.jp/contests/abc270/tasks/abc270_c)

O(N)
全探索の問題です。
dfsかbfsで解答しましょう。
この問題の鍵は、経路復元にあります。
経路を文字列で保持すると、TLEになります。
また全てのN点に対して、配列で経路を保持する（２次元配列で保持）のもメモリの最大値を超えます。
下記のようにして対応します。

```C++:C++
    // ゴールからXまでの経路を復元
    int current = Y;
    vector<int> res;
    while (current != 0) {
        res.push_back(current);
        current = previous[current];
    }
```

この問題は1次元配列で経路を保持することが鍵となります。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; 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,string>;
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 previous[200010];

int main() {
    int N, X, Y;
    cin >> N >> X >> Y;

    // 経路を保持のする配列を-1で初期化
    rep(i, N+1) previous[i] = -1;
    // 無向グラフの作成
    vector<vector<int>> graph(N+1);
    rep(i, N-1){
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    // bfs
    queue<int> que;
    que.push(X);
    previous[X] = 0;
    while(que.size()){
        int p = que.front();
        que.pop();
        //処理に適した繰り返し処理
        for(auto g:graph[p]){
            //キューに追加する条件
            if(previous[g] >= 0) continue;
            //どの経路をきたか保持
            previous[g] = p;
            //キューに追加
            que.push(g);
        }
    }
    // ゴールからXまでの経路を復元
    int current = Y;
    vector<int> res;
    while (current != 0) {
        res.push_back(current);
        current = previous[current];
    }
    reverse(res.begin(), res.end());
    // 解答を出力
    for(int i=0; i<res.size(); i++){
        cout << res[i];
        if(res.size()-1 > i) cout << ' ';
    }
    cout << endl;

    return 0;
} 
```