ARC 128
Table of Contents
A - Gold and Silver
$i$ 日目に金を銀に, $j$ 日目に銀を金に交換すると金の量は $A_i / A_j$ 倍になる. ここで
$$ \frac{A_i}{A_j} = \frac{A_i}{A_{i+1}} \times \frac{A_{i+1}}{A_{i+2}} \times \cdots \times \frac{A_{j-1}}{A_j} $$であるから $i$ 日目に金を銀に, $j$ 日目に銀を金に交換することは
- $A_i / A_{i+1}$
- $i$ 日目に金を銀に交換
- $i+1$ 日目に銀を金に交換
- $A_{i+1} / A_{i+2}$
- $i+1$ 日目に金を銀に交換
- $i+2$ 日目に銀を金に交換
- …
- $A_{j-1} / A_j$
- $j-1$ 日目に金を銀に交換
- $j$ 日目に銀を金に交換
することと等価である. 金の量を増やすには $A_i > A_{i+1}$ となるところで交換を行えばいい.
void solve() {
int n;
cin >> n;
vector<int> A(n), change(n, 0);
rep(i, n) cin >> A[i];
rep(i, n - 1) {
if (A[i] > A[i + 1]) {
change[i] ^= 1;
change[i + 1] ^= 1;
}
}
print(change);
}
XOR をとっているのは同じ日に金を銀に, 銀を金にという交換を連続する操作があった場合に 打ち消し合わせるため.