ARC 194
Table of Contents
A. Operations on a Stack
https://atcoder.jp/contests/arc194/tasks/arc194_a
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vll a(n + 1);
rep(i, n) cin >> a[i + 1];
// dp[i][j]: i 回目の操作で操作 j を行ったときの S の総和の最大値
// j = 0: 何もしない
// j = 1: a[i] を入れる
vvll dp(n + 1, vll(2, -INF));
dp[0][1] = 0;
rep2(i, 1, n + 1) {
chmax(dp[i][1], dp[i - 1][1] + a[i]);
chmax(dp[i][1], dp[i - 1][0] + a[i]);
if (i - 2 >= 0) {
// i-1 回目で要素を入れて、i 回目で要素を取り出すと何もしていないのと同じ
chmax(dp[i][0], dp[i - 2][1]);
chmax(dp[i][0], dp[i - 2][0]);
}
}
cout << max(dp[n][0], dp[n][1]) << '\n';
}
B. Minimum Cost Sort
https://atcoder.jp/contests/arc194/tasks/arc194_b
右側で swap を極力したくないから大きい数字から順に右端に持っていくのがコストとして最適
$i$ 番目の要素を $j$ 番目 ($i < j$) に持っていくのにかかるコストは \begin{align*} \sum_{k=i}^{j-1} k &= \left( \sum_{k=1}^{j-1} k \right) - \left( \sum_{k=1}^{i-1} k \right) \\ &= \frac{j(j-1)}{2} - \frac{i(i-1)}{2} \end{align*} である。
移動する毎に要素の index が変わっていくので、次に移動させる数字の index は何になるのかがわかれば問題に AC できる。
これから移動させる数字を $x$ とし、$x$ の元々の index を $i_x$ とする。 大きい数から順に右に数字を移動させていくので $x$ の index は $i_x$ よりも増えることはない。 減るタイミングは今まで移動させてきた数字のうち元々の index が $i_x$ 未満のものを移動させたときに $x$ の index は -1 される。($x$ よりも左側の $x$ よりも大きい数が存在したとき)
よって数を移動させるたびにどの index だったものが移動したかを記録しておくことで $x$ を移動させるときの実際の index を求めることができる。
$x$ を移動させるときの実際の index は $i_x - \text{(元の index が } i_x \text{ 未満である数字のうち値が } x \text{ よりも大きい数の個数}$ である。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll N;
cin >> N;
vint P(N + 1);
rep(i, N) cin >> P[i + 1];
vint id(N + 1);
rep(i, N) {
id[P[i + 1]] = i + 1;
}
auto cal = [](ll n) -> ll {
return n * (n + 1) / 2;
};
fenwick_tree<int> fw(N + 1);
set<int> memo;
ll ans = 0;
for (int j = N; j >= 1; j--) {
int i = id[j] - fw.sum(0, id[j]);
ans += cal(j - 1) - cal(i - 1);
fw.add(id[j], 1);
}
cout << ans << endl;
}
C. Cost to Flip
https://atcoder.jp/contests/arc194/tasks/arc194_c
D. Reverse Brackets
https://atcoder.jp/contests/arc194/tasks/arc194_d