0 はじめに
0-1 こんにちは
お久し振りです。
暇なんでABC286の解説を書きます。
こんな感じで解説します。
①問題の概要
②思ったこと・解法への論理など
③解説・実装
「思ったこと」についてですが、腹立たしい表現を用いているかも知れません。ご愛嬌。
又、不明な点などございましたら是非コメント欄より教えて下さい。お願いします。
0-2 感想
Eの早解きで大勝ち出来そうな回ですね。
又、Fはよく考えれば多分解けますね。
DiffはABが灰前半、CDが茶中間、Eが緑後半、Fが青中間くらいでした。
僕は44分2ペナで五冠してPerfは1455でした。
Dで詰まったのが痛かったです。
1 解説
1-1 A問題 Range Swap
問題の概要
長さ$N$の数列$A$が与えられるので次の操作をして下さい。
・$A$の$P$から$Q$項目と$R$から$S$項目を入れ替えた数列を$B$とする。
・入れ替えるべき2つの部分列の長さは等しい。
・$B$を出力(空白区切りで)してください。
制約
$1 \leq N \leq 100$
思ったこと
特にないです。
解法
入力を受け取って入れ替えて出力するだけですね。
配列の入力やfor文を用います。
詳しくは実装のところに書いてあります。
競プロ初学者の方はAPG4bなどでマスターしておきましょう。(最初の方は、APG4bは二章まででもとても十分です。)
実装
Pythonでの実装
N,P,Q,R,S=map(int,input().split())
A=list(map(int,input().split()))
A[P-1:Q],A[R-1:S]=A[R-1:S],A[P-1:Q]
print(*A,sep=" ")
ここではスライス表記を用いてswapしています。
スライス表記については次の記事を参考にどうぞ。スライス表記についてのよい記事
C++での実装
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N,M) for(int i=N; i<M; i++)
int main(){
int N,P,Q,R,S; cin>>N>>P>>Q>>R>>S;
vector<int> A(N);
rep(i,0,N) cin>>A[i];
rep(i,P-1,Q){
swap(A[i],A[i+R-P]);
}
rep(i,0,N){
cout<<A[i]<<" ";
}
}
$A$の$P$から$Q$項目の部分を$C$、$R$から$S$項目の部分を$D$とします。
$C$と$D$の$i$項目をswapすればよいです。
1-2 B問題 Cat
問題の概要
長さ$N$の文字列$S$が与えられます。
$S$に連続して現れるnaをnyaに変えた文字列を出力して下さい。
制約
$1 \leq N \leq 1000$
思ったこと
Pythonならreplace関数で一発だな～と思いつつ使い方を忘れて愚直にやりました。
解法
文字列を左から見ていきます。
答えの文字列をansとします。
今見ている文字と、その右の文字を合わせた文字列がnaになるならばansにnyaを加えて、
そうでないならばその今見ている文字を加えればよいです。
実装
for文を回しますが、naを検出したらfor文を1回飛ばすことに注意しましょう。
Pythonでの実装
N=int(input())
S=input()
ans=""
fl=0
for i in range(N):
if fl: fl=0; continue
if i<=N-2 and S[i]+S[i+1]=="na":
ans+="nya"
fl=1
else:
ans+=S[i]
print(ans)
前述のreplace関数での実装が次です。
文字列S.replace(文字列a,文字列b)で、文字列Sに含まれる文字列aを文字列bに書き換えた文字列を返します。
N=int(input())
S=input()
print(S.replace("na","nya"))
C++での実装
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N,M) for(int i=N; i<M; i++)
int main(){
int N; cin>>N;
string S; cin>>S;
string ans="";
bool fl=false;
rep(i,0,N){
if(fl){
fl=false; continue;
}
if(i<N-1 and S[i]=='n' and S[i+1]=='a'){
ans+="nya";
fl=true;
}else{
ans+=S[i];
}
}
cout<<ans<<endl;
}
1-3 C問題 Rotate and Palindrome
問題の概要
長さ$N$の文字列$S$が与えられます。
$S$を、次の二種類の操作を好きな回数行うことで回文にしたいです。
①$A$のコストで、$S$の最左の文字を最右に移動する。乃ち$S$=$S_2S_3S_4...S_NS_1$に変える。
②$B$のコストで、$S_i$を好きな文字に変える。
掛かるコストの最小値を求めて下さい。
制約
・$1 \leq N \leq 5000$
・$1 \leq A_i,B_i \leq 10^9$
思ったこと
操作②をした後に①をすると考えると複雑になりそう。
操作①の後に②をすると考えたい。
解法
操作①を$n$回行った後に②を何回する必要があるか、という小問題を各$0 \leq n \leq N$について求め、それぞれの時のコストの最小値を求めればよいです。
①を$n$回行った後の$S$は、一回毎に①の操作を$S$に施すことで自然に求められます。
②は、前から$i$文字目と後ろから$i$文字目が異なる時に行う必要があります。必要な回数はfor文を回して求められます。
実装
Pythonでの実装
N,A,B=map(int,input().split())
S=input()
ans=float("INF")
for n in range(N):
cnt=0
for i in range(N//2):
if S[i]!=S[-i-1]:
cnt+=1
ans=min(ans,cnt*B+n*A)
S=S[1:]+S[0]
print(ans)
C++での実装
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,N,M) for(int i=N; i<M; i++)
const ll INF=1001001001001001;
int main(){
ll N,A,B; cin>>N>>A>>B;
string S; cin>>S;
ll ans=INF;
rep(n,0,N){
ll cnt=0;
rep(i,0,N/2){
if(S[i]!=S[N-i-1]){
cnt++;
}
}
ans=min(ans,cnt*B+n*A);
char fir=S[0];
rep(j,0,N-1){
S[j]=S[j+1];
}
S[N-1]=fir;
}
cout<<ans<<endl;
}
1-4 D問題 Money in Hand
問題の概要
$N$種類の硬貨があります。
$i$種類目の硬貨は$A_i$円で、$B_i$枚持っています。
硬貨を上手く組み合わせることで$X$円丁度を払うことはできますか？
制約
・$1 \leq N \leq 50, 1 \leq X \leq 10^4$
・$1 \leq A_i \leq 100,1 \leq B_i \leq 50$
思ったこと
各種類の硬貨の使う枚数を全探索すると、計算量は$O(\max(B)^N)$のような指数オーダーになるので無理そう。
見た感じ、各種硬貨の選んだ枚数は互いに影響したりしないので単純なDPで解けそう。
解法
DP(動的計画法)で解けます。
DPとは
DPを知らない方の為に一応説明しておくと、DPとは、指数通りある選択肢を、それらの関係を表す漸化式を書くことで計算量を大きく削減する手法で、AtCoderに頻出のアルゴリズムです。
参考になるページを少しばかり挙げておきます。
DPの概念について
DPの種類など
DPの添え字には欲しい情報を詰め込むというのがDPの鉄則です。
$DP_{i,n}$を、「$i$種類目までの硬貨を上手く選んで、$n$円を作ることができるか」とすれば上手くいきます。
遷移は次のような感じにやればよいです。
$DP_{i,n}$は次の時に真となります。
「$i-1$種類までの硬貨で、$n-A_i×c$円を作ることができる」($c$は$i$種類目の硬貨を選ぶ枚数、$0 \leq c \leq B_i$)
つまり、$DP_{i-1,n-A_i×c}(0 \leq c \leq B_i)$のうちどれか1つでも真であれば$DP_{i,n}$は真です。
実装
上を実装すればいいです。
$DP_{i,n}$の遷移は、$n$が大きいものから行わないと、硬貨の枚数制限が無いことになってしまうので注意しましょう。
又、$DP_{i-1,n}$が真ならば$DP_{i,n}$は絶対に真になるので、$DP$は一次元にすることができます。詳しくは実装をどうぞ。
$i$で$N$回のループ、$n$で$X+1$回のループ、$c$で$B_i$回のループを行うので、計算量は$O(NX\max B)$となり間に合います。
Pythonでの実装
N,X=map(int,input().split())
DP=[0]*(X+1) #DP[n]=現在n円払えるか
DP[0]=1
for i in range(N):
a,b=map(int,input().split())
for n in reversed(range(X+1)):
for c in range(1,b+1):
if 0<=n-c*a and DP[n-c*a]:
DP[n]=1
print("Yes" if DP[X] else "No")
C++での実装
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N,M) for(int i=N; i<M; i++)
int main(){
int N,X; cin>>N>>X;
vector<bool> DP(X+1,false); DP[0]=true;
rep(i,0,N){
int a,b; cin>>a>>b;
for(int n=X; n>=0 ;n--){
rep(c,1,b+1){
if(0<=n-c*a and DP[n-c*a]){
DP[n]=true;
}
}
}
}
if(DP[X]) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
1-5 E問題 Souvenir
問題の概要
$N$個の都市があります。都市間には道路があります。
都市$i$を通るとスコアが$A_i$が上がります。
次のクエリが$Q$個飛んでくるので処理してください。
「都市$S$から$T$へ行く時の通る道の本数を最小化し、スコアを最大化したいです。
道の本数の最小化が最優先です。
その時の通る道の本数とスコアを求めて下さい。
又、$S$から$T$へ道を辿って行けないならば報告して下さい。」
制約
・$1 \leq N \leq 300$
・$1 \leq A_i \leq 10^9$
・$1 \leq Q \leq 50000$くらい
思ったこと
グラフの最短経路の問題にできそう。
道の本数を最小化し、スコアを最大化する必要があるが、それらを1つの数値にできそう。
あ、道の本数の最小化を優先するんだから、こんな感じの数値を最小化すればよさそう！(閃きの音)
$cost=(通った道の本数)×(ある程度大きい数)-(スコア)$
通った道の本数が小さくなるとこの数値は大幅に小さくなり、その中でもスコアが大きくなると更に小さくなるので、二つの値の最適化ができた！
解法
ほぼ上で説明したようなものです。
重み付き有向グラフ上での最短経路問題に帰着させます。
任意の頂点$i$から$j$へ移動する時のコストを$cost=(通った道の本数)×(ある程度大きい数)-(スコア)$と定義し、この$cost$を最小化します。
具体的には、道を通るたびに$(ある程度大きい数)$をコストに加算し、$(移動先で得られるスコア)$をコストから引けばよいです。
実装
重み付き有向グラフ上での最短経路問題なので、ダイクストラ法を使えば良いです。
クエリでは任意の2頂点間の最短距離が訊かれているので、事前に各頂点からダイクストラ法を行い、各頂点間の距離を知っておくとよいです。(そう考えるとワーシャルフロイド法でも良いかも知れませんね)
何回もダイクストラ法を行うので関数にしておくと見栄えがよいかも知れません。
又、$(ある程度大きい数)$は$10^{12}$くらいに設定しておくとよいです。
スコアは$3×10^{11}$くらいになり得るので、$10^{10}$くらいだとスコアの値が通った道の本数に影響を出してしまう可能性があるからです。
ダイクストラ法の計算量は$V$を頂点数、$E$を辺の本数として$O(V \log E)$で、$E \geq V^2$なので、$O(V \log V)$となります。
この問題では$N$回これを行い頂点数は$N$なので全体の計算量は$O(N^2 \log N)$となり間に合います。
ワーシャルフロイド法では計算量は$O(N^3)$です。
$S$から$T$へ到着できない時はImpossibleと出力するのを忘れないようにしましょう。
実装は次のようになります。
Pythonでの実装
from heapq import heapify, heappop, heappush
INF=float("INF")
N=int(input())
A=list(map(int,input().split()))
S=[input() for _ in range(N)]
G=[[] for _ in range(N)]
for i in range(N):
for j in range(N):
if S[i][j]=="Y":
G[i].append(j)
big=10**15
def dijkstra(s):
H=[(-A[s],s)]; heapify(H)
dist=[INF]*N; dist[s]=-A[s]
while H:
d,now=heappop(H)
if d>dist[now]:
break
for nxt in G[now]:
tmp=dist[now]+big-A[nxt]
if dist[nxt]>tmp:
dist[nxt]=tmp
heappush(H,(tmp,nxt))
return dist
Q=int(input())
dists=[dijkstra(i) for i in range(N)]
for i in range(Q):
s,t=map(int,input().split()); s-=1; t-=1
n=dists[s][t]
if n==INF:
print("Impossible")
continue
dis=-(dists[s][t]%big)+big
road=(dists[s][t]+dis)//big
print(road,dis)
C++での実装
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,N,M) for(int i=N; i<M; i++)
const ll INF=1001001001001001;
const ll big=1e12;
int N;
vector<int> A(300);
vector<vector<int>> G(300);
vector<ll> dijkstra(int s){
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> H;
H.push(make_pair(-A[s],s));
vector<ll> dist(N,INF); dist[s]=-A[s];
while(H.size()){
int d,now; tie(d,now)=H.top(); H.pop();
if(d>dist[now]) break;
for(auto nxt:G[now]){
ll tmp=dist[now]+big-A[nxt];
if(dist[nxt]>tmp){
dist[nxt]=tmp;
H.push(make_pair(tmp,nxt));
}
}
}
return dist;
}
int main(){
cin>>N;
rep(i,0,N) cin>>A[i];
vector<string> S(N);
rep(i,0,N) cin>>S[i];
rep(i,0,N) rep(j,0,N){
if(S[i][j]=='Y'){
G[i].push_back(j);
}
}
int Q; cin>>Q;
vector<vector<ll>> dists(N);
rep(i,0,N){
dists[i]=dijkstra(i);
}
rep(i,0,Q){
int s,t; cin>>s>>t; s--; t--;
ll ans=dists[s][t];
if(ans==INF){
cout<<"Impossible"<<endl;
continue;
}
ll dis=-(dists[s][t]%big);
if(dis<0) dis+=big;
ll road=(dists[s][t]+dis)/big;
cout<<road<<" "<<dis<<endl;
}
}
2 さいごに
お読み頂きありがとうございました。
時間が思ったよりなかったので可也適当な説明になってしまいましたが、前よりはクールな説明を書けたかと思います。
感想やアドバイスなどございましたら是非コメント欄にてお教えください。
これからも暇な時に記事を書くかも知れません。
その時はまたお読み頂けると幸いです。
よい競プロライフを！