AtCoder Beginner Contest 368

## [A - Cut](https://atcoder.jp/contests/abc368/tasks/abc368_a)

O(1)
シミュレート

```
1 2 3 4 5 → 3 4 5 1 2 
```

コンテスト中はdequeを使用しました。

```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 N, K;
    cin >> N >> K;
    deque<int> deq;
    for(int i=0; i < N; i++){
        int a;
        cin >> a;
        deq.push_back(a);
    }

    for(int i=0; i < K; i++){
        int a = deq.back();
        deq.pop_back();
        deq.push_front(a);
    }

    for(int i=0; i < N; i++){
        int a = deq.front();
        deq.pop_front();
        cout << a;
        if(i < N -1) cout << ' ';
        else cout << endl;
    }

    return 0;
} 
```

dequeを使用する必要はなかったです。

```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 N, K;
    cin >> N >> K;
    vector<int> A(N);
    rep(i, N) cin >> A[i];

    for(int i = N - K; i < N; i++){
        cout << A[i] << ' ';
    }

    for(int i = 0; i < N - K; i++){
        cout << A[i];
        if(i < N - K - 1) cout << ' ';
        else cout << endl;
    }   

    return 0;
} 
```

この実装のが完結でした。

## [B - Decrease 2 max elements](https://atcoder.jp/contests/abc368/tasks/abc368_b)

O(N)
シミュレート

要素の値が大きいのを２つ減算します。
ソートをします。
Aに含まれる正の要素の個数が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 N;
    cin >> N;
    vector<int> A(N);
    rep(i, N) cin >> A[i];

    int ans = 0;
    while(1){
        sort(A.begin(), A.end());
        if(A[N-1] == 0 || A[N-2] == 0) break;
        A[N-1]--;
        A[N-2]--;
        ans++;
    }
    cout << ans << endl;

    return 0;
} 
```

## [C - Triple Attack](https://atcoder.jp/contests/abc368/tasks/abc368_c)

O(N)
周期性を見つけて計算量の削減

Nは2*10^5
H[i]の要素は10^9
シミュレートをするとTLEになります。

問題文から周期性を見つけます。

```
Tを1増やす。
その後、体力が1以上である最も前の敵を攻撃する。
このとき、Tが3の倍数ならばその敵の体力は3減り、そうでないなら1減る。
```

1から3の倍数になるまで、3回ほど的に攻撃します。
その時の体力の減り方は、

```
1 + 1 + 3 = 5
```

となり、体力の減り方は5毎に周期性を持っています。
5で割った余りはシミュレートします。

```
(5で割り算をして計算量を削減する)
    T += H[i] / 5 * 3
(5で余りを計算してシミュレートする)
    H[i]を5で割り余りaを計算する
    aが0以下になるまでループを行う
        Tに1を加算
        (Tが3で割り切れる) a-=3;
        (Tが3で割り切れない) a--;
```

```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() {
    ll N;
    cin >> N;
    vector<ll> H(N);
    rep(i, N) cin >> H[i];

    ll T = 0;
    for(ll i=0; i < N; i++){        
        T += H[i] / 5LL * 3LL;

        ll a = H[i] % 5LL;
        while(a > 0){
            T++;
            if(T % 3 == 0) a -= 3;
            else a--;
        }
    }
    cout << T << endl;

    return 0;
} 
```

## [D - Minimum Steiner Tree](https://atcoder.jp/contests/abc368/tasks/abc368_d)

O(N)
dfsです。

木構造のグラフにて、Vkを含む頂点数最小のものを求めます。
図にしてみましょう。

![D - Minimum Steiner Tree.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/626801/03d177a3-66a1-1235-9274-8a4428fa0e11.jpeg)

左側がサンプル１の入力です。
{1, 3, 5}を含む頂点は４つです。
木構造にて、根がない頂点を削除していくと答えが求まります。

```
(p == u)を結ぶ辺の場合は探索しない。
(used[u]がtrueの時) used[v] = used[u]
```

dfsが終了した後にused[i]のtrueを数の合計が答えです。

もう少し詳しく考察しましょう。
サンプルの入力では全てのVkに1が含まれていました。
Vkの頂点を1を含まないように{5, 10}として入力を作成し図にしましょう。
画像の右側に記載しました。
{5, 10}を含む頂点は3つです。

dfsを開始する始点はVkの頂点である必要があります。

```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; }

void dfs(int v, int p, vector<vector<int>> &graph, vector<bool> &used){

    for(auto u:graph[v]){
        if(u == p) continue;

        dfs(u, v, graph, used);

        if(used[u]) used[v] = true;
    }
}

int main() {
    int N, K;
    cin >> N >> K;
    vector<vector<int>> graph(N);
    rep(i, N-1){
        int a, b;
        cin >> a >> b;
        a--; b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    vector<int> V(K);
    rep(i, K) cin >> V[i], V[i]--;
    vector<bool> used(N);
    rep(i, K) used[V[i]] = true;

    dfs(V[0], -1, graph, used);

    int ans = 0;
    for(auto u:used) if(u) ans++;
    cout << ans << endl;
    
    return 0;
} 
```