ABC368 参加記(kazuppa ABCDF解説)

# 注意事項
・この記事はすべて**0-indexed**で解説する。

# A - Cut
[問題文](https://atcoder.jp/contests/abc368/tasks/abc368_a)
まず、この操作によって先頭に行くのは$A_{N-K}$。また、この操作によって上に行くのは$A_{N-K},A_{N-K+1}...A_{N-1}$。
それ以外は元の順番でならんでいるので、$A_{N-K},A_{N-K+1}...A_{N-1},A_0,A_1...A_{N-K-1}$をこの順に出力すればよい。
実行時間は$O(N)$

以下、解答例
```C++
#include <bits/stdc++.h>
using namespace std;

int main(){
  int N,K;cin>>N>>K;
  vector<int> A(N);
  for(int i=0;i<N;i++)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]<<" ";
  cout<<endl;
}
```

# B - Decrease 2 max elements
[問題文](https://atcoder.jp/contests/abc368/tasks/abc368_b)
まず、降順ソートは次のように書けばよい。
```C++
sort(rbegin(A),rend(A));
```
これを利用して実際にシミュレーションをすることを考える。
$A_i>0$なる$i$が$1$以上かの判定は降順ソートした後$A_1>0$かの判定だけをすればよい。
なぜなら、$A_1>0$なら$A_0>0$のため正の要素の数が少なくとも$2$個以上あるし、$A_1\leqq 0$なら正の要素の数が高々$1$個しかないからである。
よって、これをwhile文で表せばよい。
答えは、多く見積もっても$\sum_{i=0}^{N-1} A_i\div 2$。また、ソート系は$O(N\hspace{1mm}log\hspace{1mm}N)$なので、実行時間は$O(N\hspace{1mm}log\hspace{1mm}N\sum_{i=0}^{N-1} A_i)$。
$\sum_{i=0}^{N-1} A_i$は高々$10^4$なので、十分高速。

以下、解答例
```C++
#include <bits/stdc++.h>
using namespace std;

int main(){
  int N,ans=0;cin>>N;
  vector<int> A(N);
  for(int i=0;i<N;i++)cin>>A[i];
  while(true){
    sort(rbegin(A),rend(A));
    if(A[1]<=0)break;
    ans++;
    A[0]--;A[1]--;
  }
  cout<<ans<<endl;
}
```

# C - Triple Attack
[問題文](https://atcoder.jp/contests/abc368/tasks/abc368_c)
まず、この問題は愚直にシミュレートしたら$O(\sum_{i=0}^{N-1}H)$かかる。この問題では$\sum_{i=0}^{N-1}H_i$は最大$2\times 10^{14}$になるので、到底間に合わない。
そこで、ダメージは$3$回周期で$5$ずつという性質に着目する。
つまり、最初にまとめて$3$回周期の分を計算してしまえば、十分高速に解ける。
具体的には、次のように解ける。
・ 答えに$\lfloor H_i\div 5\rfloor \times 3$を加える($\lfloor x\rfloor$とは、$x$以下の最大の整数のこと)。
・ $H_i$を$H_i \hspace{1mm} mod \hspace{1mm} 5$に置き換える。
・ 愚直にシミュレーションする、
この方法なら、3個目のシミュレーション回数が高々$3$で収まる。
実行時間は$O(N)$なので、十分高速。

以下、解答例
```C++
#include <bits/stdc++.h>
using namespace std;
using ll=long long;

int main(){
  //ans=Tのこと
  int n;ll ans=0;cin>>n;
  vector<int> h(n);
  for(int i=0;i<n;i++)cin>>h[i];
  for(int i=0;i<n;i++){
    ans+=h[i]/5*3;h[i]%=5;
    while(h[i]>0){
      ans++;
      if(ans%3==0)h[i]-=3;
      else h[i]--;
    }
  }
  cout<<ans<<endl;
}
```

# D - Minimum Steiner Tree
[問題文](https://atcoder.jp/contests/abc368/tasks/abc368_d)
まず、この問題は説明のため$V_0$を根とした根付き木として考える。
すると、答えは$V_1,V_2...V_{K-1}$から$V_0$への最短経路に含まれる点の個数といえる（なお、当然だがそれには各$V$も含む）。
任意の頂点から根に戻るときの遷移には、**木dpを書くのがよい**。そう僕は考えている。
$dp_i$→$i$の親
$dp_{V_0}$は-1などにする。
$dp$の設計は深さ優先探索や幅優先探索などを利用することで$O(N)$で実装できる。
ただ、これでそのまま$V_i$から$V_0$に戻り、使った点をメモるという方法だと、$O(KN)$かかり、TLEしてしまう。
そこで、**任意の二頂点のパスは木だと一意に定まる**ということを利用する。
ある時点でその頂点をすでに使っているということが確定した場合、もうその点からまた戻る必要はないので（上記のパスの考え方による）、その時点で探索を打ち切ってしまって構わない。
探索する回数は高々$N$回なので、これで実行時間はvector管理で$O(N)$。またはset管理で$O(N\hspace{1mm}log\hspace{1mm}N)$になるので、十分高速。
今回の実装例ではdfs・set管理を利用している。

以下、解答例
```C++
#include <bits/stdc++.h>
using namespace std;

//dp[i]=iの親
vector<int> dp(200000);
void dfs(vector<vector<int>> &g,int mae,int i){
  //dfsを木でするときは直前の頂点を持っておけばよい。
  dp[i]=mae;
  for(int j:g[i]){
    if(mae!=j)dfs(g,i,j);
  }
}

int main(){
  int N,K;cin>>N>>K;
  vector<vector<int>> G(N);vector<int> V(K);
  for(int i=1;i<N;i++){
    int A,B;cin>>A>>B;
    A--;B--;
    G[A].push_back(B);
    G[B].push_back(A);
  }
  for(int i=0;i<K;i++){
    cin>>V[i];
    V[i]--;
  }
  dfs(G,-1,V[0]);
  set<int> ans;ans.insert(V[0]);
  //V[0]の探索でansに-1がinsertされるのを防ぐため事前にinsertしておく
  for(int i=1;i<K;i++){
    int ima=V[i];
    while(!ans.count(ima)){
      ans.insert(ima);
      ima=dp[ima];
    }
  }
  cout<<ans.size()<<endl;
}
```

# F - Dividing Game
[問題文](https://atcoder.jp/contests/abc368/tasks/abc368_f)
まず、各$A$について最大何回操作できるかを考える。
例えば、次のような感じ。
・$4$→$2$を$2$→計$2$回。
・$6$→$2$を$1$回、$3$を$1$回→計$2$回。
これで分かるかもしれないが、**素因数の回数分最高で操作できる**。
つまり、次のように言い換えることができる。
> $B_i$を$A_i$の素因数の個数とする。
$i$および$1\leqq x \leqq B_i$なる$x$を選び、$B_i$を$B_i-x$に置き換える。
先に操作できなくなった方を負けとしたとき、どちらが勝つか。

このような問題は、ニムを利用することで解ける。
このようなゲームの勝利方法は
> $A_0\oplus A_1\oplus A_2\oplus...\oplus A_{N-1}=0$なら後手必勝。
そうでないなら先手必勝

これで判断できる（$\oplus$はいわゆるxor）。
素因数の個数の計算は$O(\sqrt A_i)$。xorの計算は$O(1)$。なので、実行時間は$O(\sum_{i=0}^{N-1}\sqrt A_i)$と十分高速。

以下、解答例
```C++
#include <bits/stdc++.h>
using namespace std;

int main(){
  int N,xo=0;cin>>N;
  //xoはこれまでの数のxor
  for(int i=0;i<N;i++){
    //kaiはAの素因数の個数
    int A,kai=0;cin>>A;
    //素数列挙
    for(int j=2;j*j<=A;j++)
      while(A%j==0){
        kai++;
        A/=j;
      }
    if(A!=1)kai++;
    xo^=kai;
  }
  //xo>=1ならtrue
  cout<<(xo?"Anna":"Bruno")<<endl;
}
```

# 個人的な感想
・Cの実装を少し複雑にした
・Dの解法までにかなり時間がかかった（15分ほど）
・Eをすぐ飛ばしFにすぐ挑めたのがよかった（Eが最難関の回）
・全部ノーペナなのはうれしい