注意事項
・この記事はすべて0-indexedで説明する。
A - 369
問題文
まず、答えの候補として$A-B+A$および$B-A+B$がある。
さらに、$A\ mod \ 2=B\ mod\ 2$なら$(A+B)\div 2$もある。
よって、これらをsetで管理すれば解ける。
また、答えとなる$x$の範囲は$-98\leq x\leq 199$となる。よって、これらを全探索しても解ける。
set管理での解答例
#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;
}
全探索での解答例
#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
問題文
変数$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)$
解答例
#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
問題文
個人的には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)$。
解答例
#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
問題文
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$にしておく。
解答例
#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
問題文
かなり実装難の部類。
今回は、まずどの順番で$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)$で求まる。これは十分高速なので、これで解ける。
解答例
#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
問題文
まず、次のような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)$からいい感じに進んでいけば解ける（言語化能力無くてすみません...）。
解答例
#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;
}