💭

ABC286 A～E(C++)

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

競技プログラミング

AtCoder

競プロ

tech

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

A - Range Swap

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

問題概要

長さ $N$ の数列 $A=(A_1,A_2,\dots,A_N)$ および、正整数 $P,Q,R,S$ が与えられる。
ここで、 $P,Q,R,S$ は $1\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$ を出力せよ。

リンク

https://atcoder.jp/contests/abc286/tasks/abc286_b

解説

落ち着いて整理する。交換後の数列 $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$ に含まれるnaをnyaに置き換えて出力せよ。

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

リンク

https://atcoder.jp/contests/abc286/tasks/abc286_b

解説

便利な関数があるらしいですが、今回は無視します。
出力する文字を $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';
}

提出:AC 7ms

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$ の先頭の文字を末尾に移動させる。すなわち、 $S$ を $S_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$ 以外の入力はすべて整数

リンク

https://atcoder.jp/contests/abc286/tasks/abc286_c

解説

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

操作1を何回かやる
操作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_i$ の $j$ 文字目が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_i$ はYとNのみからなる長さ $N$ の文字列
$S_i$ の $i$ 文字目は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

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