ABC369 参加記(kazuppa ABCDEF解説)

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

# A - 369
[問題文](https://atcoder.jp/contests/abc369/tasks/abc369_a)
まず、答えの候補として$A-B+A$および$B-A+B$がある。
さらに、$A\ mod \ 2=B\ mod\ 2$なら$(A+B)\div 2$もある。
よって、これらをsetで管理すれば解ける。
また、答えとなる$x$の範囲は$-98\leq x\leq 199$となる。よって、これらを全探索しても解ける。

## set管理での解答例
```C++
#include <bits/stdc++.h>
using namespace std;

int main(){
  int a,b;cin>>a>>b;
  set<int> ans;
  ans.insert(a-b+a);
  ans.insert(b-a+b);
  if(a%2==b%2)ans.insert((a+b)/2);
  cout<<ans.size()<<endl;
}
```

## 全探索での解答例
```C++
#include <bits/stdc++.h>
using namespace std;

int main(){
  int a,b,ans=0;cin>>a>>b;
  for(int x=-98;x<=199;x++)
    if(a-b==b-x||a-x==x-b||b-a==a-x)ans++;
  cout<<ans<<endl;
}
```

# B - Piano 3
[問題文](https://atcoder.jp/contests/abc369/tasks/abc369_b)
変数$l$と$r$を次のように管理する。
・$l=$一番直近の左手の位置
・$r=$一番直近の右手の位置
初期値を$l=-1,r=-1$にして、次のように更新していく。
・$S_i=L$なら
　・$l=-1$なら$l$を$A_i$に更新する
　・そうじゃないなら答えに$|l-A_i|$を加算して、$l$を$A_i$に更新する
・$S_i=R$なら
　・$r=-1$なら$r$を$A_i$に更新する
　・そうじゃないなら答えに$|r-A_i|$を加算して、$r$を$A_i$に更新する
このようにして計算していけば解ける。
実行時間は$O(N)$

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

int main(){
  int n,ans=0,l=-1,r=-1;cin>>n;
  for(int i=0;i<n;i++){
    int a;char s;cin>>a>>s;
    if(s=='L'){
      if(l!=-1)ans+=abs(l-a);
      l=a;
    }
    if(s=='R'){
      if(r!=-1)ans+=abs(r-a);
      r=a;
    }
  }
  cout<<ans<<endl;
}
```

# C - Count Arithmetic Subarrays
[問題文](https://atcoder.jp/contests/abc369/tasks/abc369_c)
個人的にはA~Dで最難関。
まず、$l$と$r$それぞれについて等差数列が成り立つ成り立たないを調べると、$O(N^3)$かかり、間に合わない。
まず、等差数列を求めるときは、二つの整数の**差**を持つ配列を作った方がいいことがある。
今回の問題も使える。
$A_{i+1}-A_i=B_i$となる長さ$N-1$の配列$B$を持つことにする。
今回は考えやすさのため、$A_{i+1}$と$B_i$が対応すると考える。
直前までの差を表す変数$dist$および自分を含んだ最高の等差数列の長さを持つ変数$x$をつくる。
$x=1$に初期値を設定しておく（$A_0$までで長さ$1$の等差数列が作れているため）。
また、答えも$1$にしておく（$A_0$までで長さ$1$の等差数列が作れているため）。
そして、次のように動かしていく。
・$B_i=dist$なら$x$を$x+1$に置き換える。
・$B_i\neq dist$なら$x$を$2$に置き換え、$dist$を$B_i$にする。...①
①に関しては、新たに長さ$2$の等差数列が作れたと考えれば妥当だろう。
よって、毎回のループで答えに$x$を足していけば求められる。
実行時間は$O(N)$。

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

int main(){
  int n;ll ans=1;cin>>n;
  vector<int> a(n);
  for(int i=0;i<n;i++)cin>>a[i];
  //コーナーケース n=1
  if(n==1){
    cout<<1<<endl;
    return 0;
  }
  vector<int> b(n-1);
  for(int i=0;i<n-1;i++)b[i]=a[i+1]-a[i];
  int dis=b[0],x=1;
  for(int i=0;i<n-1;i++){
    if(b[i]!=dis){
      x=2;
      dis=b[i];
    }
    else x++;
    ans+=x;
  }
  cout<<ans<<endl;
}
```

# D - Bonus EXP
[問題文](https://atcoder.jp/contests/abc369/tasks/abc369_d)
2分で解けたのはでかい。

まず、敵を倒す倒さないをbit全探索で解こうとすると、$O(2^NN)$かかり、間に合わない。
こういう問題はdpで解ける。
今回は次のようなdpを作った。
$dp[i][j]$=$i$番目までの敵を $mod\ 2=j$ 倒した時のレベルの最大値
僕の場合、$i=0$のときなどの場合分けが面倒なため$i$の長さは $N+1$ にして、$A_i$と$dp_{i+1}$を対応させている。
すると、次のように書けるだろう。
・$dp[i+1][0]=max(dp[i][0],dp[i][1]+A[i]\times 2)$
・$dp[i+1][1]=max(dp[i][1],dp[i][0]+A[i])$
今回の答えは$max(dp[N][0],dp[N][1])$になるので、これを出力すればよい。
状態数は$N$、遷移は$O(1)$なので、実行時間は$O(N)$。
また、$dp[0][1]$から$dp[1][0]$への遷移はできないので、$dp[0][1]$は$-\infty$にしておく。

## 解答例
```C++
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define inf=1e+18;

int main(){
  int n;cin>>n;
  vector<ll> a(n);
  for(int i=0;i<n;i++)cin>>a[i];
  vector<vector<ll>> dp(n+1,vector<ll>(2,0));
  dp[0][1]=-inf;
  for(int i=0;i<n;i++){
    dp[i+1][0]=max(dp[i][0],dp[i][1]+a[i]*2);
    dp[i+1][1]=max(dp[i][1],dp[i][0]+a[i]);
  }
  cout<<max(dp[n][0],dp[n][1])<<endl;
}
```

# E - Sightseeing Tour
[問題文](https://atcoder.jp/contests/abc369/tasks/abc369_e)
かなり実装難の部類。

今回は、まずどの順番で$B_i$番目の橋を渡ればいいのか。
実は$K\leq 5$なので、順列全探索で**全列挙**できる。
また、$U$側か$V$側かどっちから回ればいいかもbit全探索で**全列挙**できる。
あり得るパターンは$K!\ 2^K$なので、少ない。
ただ、毎回ダイクストラ法で調べると、ダイクストラ一回は$O(M\ log\ N)$なので、$O(Q\ K!\ 2^K\ K\ M\ log\ N)$と、間に合わない。
そういう時に使えるのは**ワーシャルフロイド法**。事前に全点対間最短経路を$O(N^3)$で求めれば、$O(Q\ K!\ 2^K\ K+N^3)$で求まる。これは十分高速なので、これで解ける。

## 解答例
```C++
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define inf 2500000000000000000LL

int main(){
  int n,m,q;cin>>n>>m;
  vector<ll> u(m),v(m),t(m);
  for(int i=0;i<m;i++)cin>>u[i]>>v[i]>>t[i];
  for(int i=0;i<m;i++)u[i]--,v[i]--;
  //ワーシャルフロイド
  vector<vector<ll>> d(n,vector<ll>(n,inf));
  for(int i=0;i<m;i++)d[u[i]][v[i]]=min(d[u[i]][v[i]],t[i]);
  for(int i=0;i<m;i++)d[v[i]][u[i]]=min(d[v[i]][u[i]],t[i]);
  for(int i=0;i<n;i++)d[i][i]=0;
  for(int k=0;k<n;k++)
    for(int i=0;i<n;i++)
      for(int j=0;j<n;j++)
        d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
  cin>>q;
  for(int i=0;i<q;i++){
    int k;cin>>k;
    int h=(1<<k);ll ans=inf;
    vector<int> b(k);
    for(int j=0;j<k;j++){cin>>b[j];b[j]--;}
    do{
      //順列全探索
      for(int j=0;j<h;j++){
        //bit全探索
        bitset<5> e(j);int iti=0;ll sum=0;
        for(int l=0;l<k;l++){
          if(e[l]){
            //u[i] to v[i]
            sum+=d[iti][u[b[l]]];
            sum+=t[b[l]];
            iti=v[b[l]];
          }
          else{
            //v[i] to u[i]
            sum+=d[iti][v[b[l]]];
            sum+=t[b[l]];
            iti=u[b[l]];
          }
        }
        ans=min(ans,sum+d[iti][n-1]);
      }
    }while(next_permutation(b.begin(),b.end()));
    cout<<ans<<endl;
  }
}
```

# F - Gather Coins
[問題文](https://atcoder.jp/contests/abc369/tasks/abc369_f)
まず、次のようなdpを考える。
$dp[i][j]=$マス$(i,j)$でとれるコインの最大値。
ただ、この解法だと状態数が$HW$あり、間に合わない。
とりあえず、いったん$R$を基準に昇順ソートする。
すると、入出力例1の$R,C$が$(1,4),(2,1),(2,3),(3,3)$となる。
そのうえで、答えは$(2,1),(2,3),(3,3)$になっているのだが、この時$C$は**広義単調増加**になっている。
広義単調増加になっている長さの最大値が$D$の最大値となる。
これは、セグ木で解ける。
セグ木に持たせる情報は、
・$[L,R)$のなかの最大値（初期値は0）
・$[L,R)$のなかの最大値のインデックス（初期値は-1）
$C_i$の最大値は、$[0,C_i)の最大値+1$になるし、そのインデックスは$i$とすればよい。
そして、この問題は**復元**するdpである。よって、$i$番目の直前は$[0,C_i)$のなかの最大値のインデックスとなる。
よって、$(1,1)$からいい感じに進んでいけば解ける（言語化能力無くてすみません...）。

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

//一つ目は最大値、二つ目は最大値のインデックス
pair<int,int> op(pair<int,int> a,pair<int,int> b){
  if(a.first>b.first)return a;
  return b;
}

pair<int,int> e(){return {0,-1};}

int main(){
  int h,w,n;cin>>h>>w>>n;
  vector<pair<int,int>> c(n);
  for(int i=0;i<n;i++){cin>>c[i].first>>c[i].second;}
  sort(c.begin(),c.end());
  segtree<pair<int,int>,op,e> seg(w);
  vector<int> memo(n),siz(n);
  //復元のための作業
  for(int i=0;i<n;i++){
    pair<int,int> e=seg.prod(0,c[i].second);
    memo[i]=e.second;
    siz[i]=e.first;
    seg.set(c[i].second-1,{e.first+1,i});
  }
  int ma=0;
  for(int i=1;i<n;i++)
    if(siz[ma]<siz[i])ma=i;
  vector<int> now(1,ma);
  //nowは復元用配列
  while(now[now.size()-1]!=-1){
    now.push_back(memo[now[now.size()-1]]);
  }
  //nowの最後尾が-1になってるため
  now.pop_back();
  reverse(now.begin(),now.end());
  cout<<now.size()<<endl;
  //復元をもとに移動方法の作成
  for(int i=1;i<c[now[0]].first;i++)cout<<'D';
  for(int i=1;i<c[now[0]].second;i++)cout<<'R';
  for(int i=0;i<now.size()-1;i++){
    for(int j=c[now[i]].first;j<c[now[i+1]].first;j++)cout<<'D';
    for(int j=c[now[i]].second;j<c[now[i+1]].second;j++)cout<<'R';
  }
  for(int i=c[now[now.size()-1]].first;i<h;i++)cout<<'D';
  for(int i=c[now[now.size()-1]].second;i<w;i++)cout<<'R';
  cout<<endl;
}
```