AtCoder Beginner Contest 174を見直す D - Alter Altar
C問題よりも簡単だったD問題ですが、説明できるかは正直不安
問題
白色の石と、赤色の石が合計n個、直線に並んでいます。その石の列が与えられるので、任意の石2つを入れ替えるか、任意の石の色を変えて最短で、赤い石の左側に白い石がない状態にするには何手かかるか答えなさい。
これは、赤い石を右側に、白い石を左側に並び替える問題と言える。なので、以下の解答を作成
当日作成した解答(Python:84ms)
n = int(input())
c = input()
cnt = [0 for _ in range(n)]
red = 0
for i in range(n):
if c[i] == 'R': red += 1
cnt[i] = red
print(red - cnt[red-1])
例えば以下の様な石の並び(下図上部)があったとして
赤石は4つなので、右4つを赤石にする必要がある。(下図下部)すると右から4つ以内の白石と、右から4つ以内にない赤石を入れ替える事になる。石の色を変える事もできるが、手数が増えるので考えない。
よって、赤石にする必要がある範囲(赤石の総数)内にある白石の数が、最小手数になる。
後日作成した解答(CPP:15ms)
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using vi = vector<int>;
int main() {
int n;
string s;
cin >> n >> s;
int red = 0, white = 0;
vi count(n);
rep (i, n) {
if (s.at(i) == 'R') red++;
else white++;
count.at(i) = white;
}
if (red == 0) cout << 0 << endl;
else cout << count.at(red - 1) << endl;
return 0;
}
最後の分岐を入れていなかったので、最初ランタイムエラーが出ました。赤がないパターンでエラーが出たものと考えられます。Pythonの場合は配列のインデックスに「-1」を渡しても、最後から1番目の値が返るので気付きませんでした(正解ではあるが考慮漏れ)、CPPの「at」ではインデックスに「-1」はエラーになる様です。バグを埋め込みづらいと言う意味で、CPPで配列を扱う際には「at」を使った方がいいと思いました。
この記事が気に入ったらサポートをしてみませんか?