💭

ABC286 A~E(C++)

2023/01/22に公開約8,100字

ABC286に参加しました。感想・解説を書いていきます~

A - Range Swap

Aにしては難しいかも...普通にめんどくさい。

問題概要

長さNの数列A=(A_1,A_2,\dots,A_N)および、正整数P,Q,R,Sが与えられる。
ここで、P,Q,R,S1\leq P\leq Q < R\leq S\leq NかつQ-P=S-Rを満たしている。
(A_P,A_{P+1},\dots,A_Q)(A_R,A_{R+1},\dots,A_S)をswapして、Aを出力せよ。

リンク

解説

落ち着いて整理する。交換後の数列Bは次を満たす。

  • i<P,Q<i<R,S<iのいずれかを満たすとき、B_i=A_i(交換の影響を受けない)
  • P\leq i\leq Qのとき、B_i=A_{i-P+R}
  • R\leq i\leq Sのとき、B_i=A_{i-R+P}

これの通りに実装する。

実装例

#include<bits/stdc++.h>
using namespace std;
int main() {
	int n, p, q, r, s;
	cin >> n >> p >> q >> r >> s;
	p--, q--, r--, s--;    //0-indexになおす

	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	vector<int> b(n);   //操作後の数列

	for (int i = 0; i < n; i++) {
		if (i < p || (q < i && i < r) || s < i)b[i] = a[i];
		else if (p <= i && i <= q)b[i] = a[i - p + r];
		else b[i] = a[i - r + p];
	}
	//出力
	for (int i = 0; i < n; i++) {
		cout << b[i] << ' ';
	}
	cout << '\n';
}

B - Cat

問題概要

長さNの文字列Sが与えられる。Sに含まれるnanyaに置き換えて出力せよ。

  • N\leq 10^3
  • Sは英小文字のみからなる長さNの文字列

リンク

解説

便利な関数があるらしいですが、今回は無視します。
出力する文字をTとします。この時、次のようにTを構築できます。S,Tは0-indexになことに気を付けてください。

i=0とする。i<N の間、次を繰り返す。

  • i+1<NかつS_iS_{i+1}=naなら、Tの末尾にnyaを追加する。i+2にワープする(i\leftarrow i+2)
  • それ以外なら、Tの末尾にS_iを追加する。i+1に進む(i\leftarrow i+1)

これは、whileとかforとかを使えばできます。

実装例

while文

#include<bits/stdc++.h>
using namespace std;
int main() {
	int n;
	string s;
	cin >> n >> s;
	string t;
	int pos = 0;  //i
	while (pos < n) {
		if (s.substr(pos, 2) == "na") {
			t += "nya";
			pos += 2;
		}
		else {
			t += s[pos];
			pos += 1;
		}
	}
	cout << t << '\n';
}

for文

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    string s;
    cin>>n>>s;
    string t;
    for(int i=0;i<n;){
        if(s.substr(i,2)=="na"){
            t+="nya";
            i+=2;
        }else{
            t+=s[i];
            i++;
        }
    }
    cout<<t<<'\n';
}

C - Rotate and Palindrome

問題概要

長さNの文字列Sが与えられる。
Sに対して次の2種類の操作を0回以上行うことができる。
操作1:A円払う。Sの先頭の文字を末尾に移動させる。すなわち、SS_2S_3\dots S_NS_1に変える。
操作2:B円払う。1\leq i\leq Nなるiを選び、S_iを好きな文字に変更する。

Sを回文にするために必要なコストの最小値を求めよ。

  • 1\leq N\leq 5\times 10^3
  • 1\leq A,B\leq 10^9
  • Sは英小文字のみからなる長さNの文字列
  • S以外の入力はすべて整数

リンク

解説

考察っぽい...が、案外そうでもない。
操作の順番は、次のようにしても問題ありません。

  1. 操作1を何回かやる
  2. 操作2を何回かやる

1で行う回数を固定します。この時2で行う回数はS_i\neq S_{N-i-1}なるiの個数をcとして\frac{c}{2}です。
さらに、1で行う回数をは高々N回です。したがって、これを全探索すればO(N^2)で解くことができます。

実装例

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n, a, b;
    string s;
    cin >> n >> a >> b >> s;

    const long long infl = 1e18;
    long long ans = infl;
    for (int i = 0; i <= n; i++) {
        int c = 0;
        for (int j = 0; j < n; j++) {
            if (s[j] != s[n - j - 1]) {
                c++;
            }
        }

        c /= 2;
        ans = min(ans, 1ll * a * i + 1ll * c * b);
        s = s.substr(1) + s.front();
    }
    cout << ans << '\n';
}

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
  • A_iはすべて異なる
  • 入力はすべて整数

解説

部分和問題の進化系...というか、ほぼ同じ問題。DPで処理しよう。
DP,部分和問題を知らない人は...ほかの記事を参考にしてほしい!!!
dp[i][j]を次で定める。

dp[i][j]=i番目までの硬貨を見たとき、ちょうどj円を支払えるか?

このとき、dp[i][j]からの遷移は次の通りです。

dp[i][j]=\text{true}のとき
k=0,1,\dots,B_iについてdp[i+1][j+A_ik]=\text{true}

以上で、全体でO(X\sum B_i)で解ける。

実装例

#include<bits/stdc++.h>
using namespace std;
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<bool>> dp(n + 1, vector<bool>(x + 1, false));
    dp[0][0] = true;
    for (int i = 0; i < n; i++)for (int j = 0; j <= x; j++) {
        if (!dp[i][j])continue;
        for (int k = 0; k <= b[i]; k++) {
            if (j + k * a[i] > x)continue;
            dp[i + 1][j + k * a[i]] = true;
        }
    }

    if (dp[n][x])cout << "Yes\n";
    else cout << "No\n";
}

E - Souvenir

問題概要

N個の都市があり、いくつかの相異なる都市の間は一方通行の直行便によって移動することができます。
どの直行便が存在するかはN個の長さNの文字列S_1,S_2,\dots,S_Nによって表されます。
S_ij文字目がYの時都市iから都市jへの直行便があることを、Nのときはないことを示しています。
各都市にはお土産が1つずつ売られていて、都市iには価値A_iのお土産が売られています。
Q個のクエリが与えられます。各クエリでは整数U_i,V_iが与えられるので、次の問いに答えてください。

都市U_iから都市V_iに向かう。途中に通るすべての都市(U_i,V_iを含む)でお土産を購入する。
都市U_iから都市V_iに向かう経路が複数存在するとき、次の基準に沿って経路を選ぶ。

  • 使う直行便の本数が少ないほうを選ぶ。
  • どちらも使う本数が同じときは、途中で購入するお土産の価値の合計が大きいほうを選ぶ。

この時、使う直行便の本数と、購入するお土産の価値の合計を出力せよ。

  • 2\leq N\leq 3\times10^2
  • 1\leq A_i\leq10^9
  • S_iYNのみからなる長さNの文字列
  • S_ii文字目はN
  • 1\leq U_i,V_i\leq N
  • U_i\neq V_i
  • (U_i,V_i)\neq (U_j,V_j)
  • 与えられるN,A_i,Q,U_i,V_iはすべて整数

解説

まず、グラフの言葉に直す。

有向グラフGが与えられる。頂点vには値A_vが定まっていて、vを通ると価値A_vのお土産がもらえる。
Q個のクエリが与えられる。各クエリでは整数U_i,V_iが与えられるので次の問いに答えよ。

頂点U_iから頂点V_iまで最短距離で移動する。もらえるお土産の価値の総和をできるだけ大きくするとき、

  • 最短距離
  • お土産の価値の総和

を求めよ。

...まあ、あんまり変わらないけど。


一旦最短経路長だけについて考える。これは「全点対最短経路」というやつで、ワーシャルフロイド法を使うとO(N^3)で解くことができる。
お土産の扱いがやや困るが、最短距離と同時に更新していって問題ない。
...細かいことは、実装を見てほしい!!!

なお、BFS,DFS,dijkstraを使っても解けるらしい。

実装例

計算量はO(N^3+Q)です。

#include<bits/stdc++.h>
using namespace std;
template<class T, class U>void chmax(T& x, U y) { x = max(x, y); }
int main() {
    const int inf = 1e9;
    using ll = long long;

    //入力受け取り
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& aa : a) {
        cin >> aa;
    }
    vector<string> s(n);
    for (auto& ss : s) {
        cin >> ss;
    }
    vector<vector<int>> dist(n, vector<int>(n, inf)); //dist[i][j]:=i->jの最短距離(到達できないときはinf)
    vector<vector<ll>> val_sum(n, vector<ll>(n));  //val_sum[i][j]:=i->jでのお土産の価値の和の最大値(iを除く!!!)


    for (int i = 0; i < n; i++)for (int j = 0; j < n; j++) {
        if (s[i][j] == 'Y') {
            dist[i][j] = 1;
            val_sum[i][j] = a[j];
        }
    }


    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int pre_dist = dist[i][j];    //i->j
                int new_dist = dist[i][k] + dist[k][j];     //i->k->j

                if (pre_dist < new_dist)continue;  //悪化したらダメ

                //処理が違うことに注意!!!
                if (pre_dist == new_dist) {
                    //同じ距離なら、価値の合計が大きいほうを選ぶ
                    chmax(val_sum[i][j], val_sum[i][k] + val_sum[k][j]);
                }
                else {
                    //前の経路は候補から外す
                    dist[i][j] = dist[i][k] + dist[k][j];
                    val_sum[i][j] = val_sum[i][k] + val_sum[k][j];
                }
            }
        }
    }


    //クエリに答える

    int q;
    cin >> q;
    while (q--) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;

        if (dist[u][v] >= inf) {
            cout << "Impossible\n";
        }
        else {
            cout << dist[u][v] << ' ' << a[u] + val_sum[u][v] << '\n';
        }
    }
}

終わりに

ここまで読んでくださってありがとうございました。

Discussion

ログインするとコメントできます