AtCoder Beginner Contest 286
結果
A - Range Swap:AC(12:31)
B - Cat:AC(16:13)
C - Rotate and Palindrome:提出無し
D - Money in Hand:AC(97:00)(1ペナ)
A - Range Swap
長さ$${N}$$の数列$${A=(A_{1},A_{2},…,A_{N})}$$が与えられ、数列$${A}$$の$${P}$$番目から$${Q}$$番目の項と$${R}$$番目から$${S}$$番目の項を入れ替えた数列を出力する問題
自分の回答
int main(){
int N, P, Q, R, S;
cin >> N >> P >> Q >> R >> S;
vector<int> A(N + 1);
for(int i = 1; i <= N; i++){
cin >> A[i];
}
while(P <= Q){
swap(A[P], A[R]);
P++;
R++;
}
for(int i = 1; i <= N; i++){
printf("%d", A[i]);
printf(i == N ? "\n" : " ");
}
}
そのままだけどswapの存在を忘れてて時間かかった
公式解説
int main() {
int n,p,q,r,s;
int a[100];
cin>>n>>p>>q>>r>>s;
for(int i=0;i<n;i++)cin>>a[i];
for(int i=p;i<=q;i++)swap(a[i-1],a[r-p+i-1]);
for(int i=0;i<n;i++){
cout<<a[i];
if(i<(n-1))cout<<" ";
else cout<<endl;
}
return 0;
}
https://atcoder.jp/contests/abc286/editorial/5574より
そうかforでPから<=Qでいいのか
気付かなかった
B - Cat
長さ$${N}$$の文字列$${S}$$が与えられ、$${S}$$に含まれる「na」を「nya」に置き換えた文字列を出力する問題
自分の回答
int main(){
int N;
string S;
cin >> N >> S;
for(int i = 0; i < N; i++){
if(S[i] != 'n'){
printf("%c", S[i]);
}
else{
if(S[i + 1] == 'a'){
printf("nya");
i++;
}
else{
printf("n");
}
}
}
printf("\n");
}
先頭から1文字ずつ見て行ってそれが「n」かつその次が「a」なら「nya」と出力してiを追加で1増やす、それ以外ならそのまま出力
公式解説
int main() {
int n;
string s;
cin >> n >> s;
cout << regex_replace(s, regex("na"), "nya") << endl;
}
https://atcoder.jp/contests/abc286/editorial/5589より
そうだregex_replaceがあったわ
忘れてた
C - Rotate and Palindrome
長さ$${N}$$の文字列$${S}$$が与えられ
・$${A}$$円払い左端の文字を右端に移動する
・$${B}$$円払い1文字選んでそれを任意の文字にする
この2つの操作を好きな順番で好きな回数行うことができる
このとき最小何円で$${S}$$を回文にすることができるかを求める問題
自分の回答
この手の問題はやったことなくてとっかかりすらわからんかった
公式解説
int main() {
int n;
long long a, b;
string s;
cin >> n >> a >> b >> s;
s += s;
long long ans = 1ll << 60;
for(int i = 0; i < n; i++) {
long long tmp = a * i;
for(int j = 0; j < n / 2; j++) {
int l = i + j;
int r = i + n - 1 - j;
if(s[l] != s[r]) tmp += b;
}
ans = min(ans, tmp);
}
cout << ans << endl;
}
https://atcoder.jp/contests/abc286/editorial/5587より
操作の順番は結果に影響しないからまずAを何回やるか固めて、その上でBを何回やれば回文になるかを総当たりして最も少ない値を求めるのか
なるほど
D - Money in Hand
$${N}$$種類の硬貨を持っていて$${A_{i}}$$円の硬貨は$${B_{i}}$$枚ある
この時$${X}$$円をちょうど支払うことができるかを求める問題
自分の回答
int main(){
int N, X;
cin >> N >> X;
vector<int> A(N), B(N);
for(int i = 0; i < N; i++){
cin >> A[i] >> B[i];
}
vector<vector<int>> dp(N, vector<int>(X + 1, 100000));
dp[0][0] = 0;
for(int i = 0; i < N; i++){
for(int j = 0; j <= X; j++){
if(dp[i][j] < 100000){
if(i < N - 1){
dp[i + 1][j] = 0;
}
if(dp[i][j] < B[i] && j + A[i] <= X){
dp[i][j + A[i]] = min(dp[i][j] + 1, dp[i][j + A[i]]);
}
}
}
}
printf(dp[N - 1][X] < 100000 ? "Yes\n" : "No\n");
}
具体的な方法こそわからないが動的計画法なのはわかったから調べたら同じタイプの問題とその解説を見つけたためそれを見ながら書いた
https://algo-method.com/tasks/313
ただ表の立て方が好みじゃなかったため理屈を考えてたらだいぶきれいに書けた
dp[i][j]はj円にするにはA[i]の硬貨を最低何枚使えばいいか
j=0のときはどのような種類の硬貨でも0枚で0円になるためdp[0][0]を0として始点にする
dp[i][j]がちょうど払えるならば値段の変わらないdp[i+1][j]も当然払え、A[i+1]の硬貨は使う必要がないためdp[i+1][j]=0とする
またdp[i][j]<B[i]ならばまだA[i]硬貨を使うことができるため追加で1枚使ったdp[i][j+A[i]]をdp[i][j]+1にする、ただしそこがすでに埋まってるならば値の小さい方とする
試行錯誤の残骸が残ってて1ペナ
公式解説
int main(void){
int n,x;
int a[50];
int b[50];
bool dp[51][10001];
cin>>n>>x;
for(int i=0;i<n;i++)cin>>a[i]>>b[i];
for(int i=0;i<=n;i++)for(int j=0;j<=x;j++)dp[i][j]=false;
dp[0][0]=true;
for(int i=0;i<n;i++){
for(int j=0;j<=x;j++){
for(int k=0;k<=b[i];k++){
if(j>=a[i]*k){
if(dp[i][j-a[i]*k])dp[i+1][j]=true;
}
}
}
}
if(dp[n][x])cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return 0;
}
https://atcoder.jp/contests/abc286/editorial/5567より
基本は同じだけどdp[i][j+A[i]]の部分をforで回すことで表をboolにしてるのか
なるほど
この記事が気に入ったらサポートをしてみませんか?