D - Gomamayo Sequence Editorial by cn449
問題の性質を利用して前後から文字列を扱う方法について解説しています。
dp により前からのみ文字列を扱う方法はこちらで紹介しています。
\(T\) の \(i\) 文字目と \(i + 1\) 文字目が一致するような \(i\) を固定します。すると、\(1\) 文字目から \(i\) 文字目および \(i + 1\) 文字目から \(N\) 文字目は ...0101010101...
のように 0
と 1
が交互に並ぶ文字列となります。
したがって、各 \(i\) に対して以下の値が計算できればよいです。
\(S\) の \(1\) 文字目から \(i\) 文字目を
01010101...
のような0
から始まり0
と1
が交互に並ぶ文字列にするために必要なコストの総和の最小値\(S\) の \(1\) 文字目から \(i\) 文字目を
10101010...
のような1
から始まり0
と1
が交互に並ぶ文字列にするために必要なコストの総和の最小値\(S\) の \(i + 1\) 文字目から \(N\) 文字目を
...10101010
のような0
で終わり0
と1
が交互に並ぶ文字列にするために必要なコストの総和の最小値\(S\) の \(i + 1\) 文字目から \(N\) 文字目を
...01010101
のような1
で終わり0
と1
が交互に並ぶ文字列にするために必要なコストの総和の最小値
上 \(2\) つは \(i\) での計算結果から \(i + 1\) での計算結果が簡単にわかるため \(i\) の昇順、下 \(2\) つは \(i\) での計算結果から \(i - 1\) での計算結果が簡単にわかるため \(i\) の降順に計算することで答えを求めることができます。
具体的に \(1\) 番上に書いたものの計算を例にして説明します。
\(i + 1\) 文字目は \(i + 1\) が奇数のとき 0
に、偶数のとき 1
にするべきですが、これが元の \(S_{i + 1}\) と一致している場合には \(i\) での計算結果と \(i + 1\) での計算結果は一致します。そうでない場合は、\(i\) での計算結果に \(C_{i + 1}\) を足すことにより \(i + 1\) での計算結果が得られます。
実装の際には、0
で終わる / 1
で終わるというような扱いではなく、(\(N\) 文字全体のうちの) 偶数文字目が 0
で奇数文字目が 1
の文字列 / 偶数文字目が 1
で奇数文字目が 0
の文字列というような扱いをすると考えるべきことが減ると考えられます。
実装例
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n;
cin >> n;
string s;
cin >> s;
vector<ll> c(n);
for (int i = 0; i < n; i++) cin >> c[i];
vector<ll> f0(n + 1), f1(n + 1), g0(n + 1), g1(n + 1);
for (int i = 0; i < n; i++) {
f0[i + 1] = f0[i];
f1[i + 1] = f1[i];
if (i % 2 == 0) {
if (s[i] == '0') f1[i + 1] += c[i];
else f0[i + 1] += c[i];
}
else {
if (s[i] == '0') f0[i + 1] += c[i];
else f1[i + 1] += c[i];
}
}
for (int i = n - 1; i >= 0; i--) {
g0[i] = g0[i + 1];
g1[i] = g1[i + 1];
if (i % 2 == 0) {
if (s[i] == '0') g0[i] += c[i];
else g1[i] += c[i];
}
else {
if (s[i] == '0') g1[i] += c[i];
else g0[i] += c[i];
}
}
ll ans = 1'000'000'000'000'000'000;
for (int i = 1; i < n; i++) ans = min(ans, f0[i] + g0[i]);
for (int i = 1; i < n; i++) ans = min(ans, f1[i] + g1[i]);
cout << ans << '\n';
}
posted:
last update: