https://cf17-tournament-round1-open.contest.atcoder.jp/tasks/asaporo2_c
考察よりも実装を重視して解いた。
解法自体は良くありがちなやつ。
2つのカッコ列が成立するための必要条件が、最初がどちらも(、最後がどちらも)、真ん中で違うのが偶数個なのだが、それが実は十分でもあるというもの。なので、基本的に真ん中はAとBの好きな方を取れるが、Aを取る回数が奇数回になってしまった時に調節をしなければならない。調節方法だが、AiとBiの絶対値が一番小さいiを見て、使うのを最善の時と逆にする。これはmultisetを使えばできる。
強い人の実装をみて思ったことは、
1.定義する変数or関数が少ない
2.if文が少ない
だったのでそれに沿って実装してみました。結構コンパクトにかけたんじゃないかなぁ。
int N, Q; ll A[MAX_N], B[MAX_N]; //[0, 2 * N) !! multiset<ll> S; void solve() { cin >> N >> Q; rep(i, 0, 2 * N) cin >> A[i]; rep(i, 0, 2 * N) cin >> B[i]; ll ans = 0; bool odd = false; ans += A[0] + A[2 * N - 1]; rep(i, 1, 2 * N - 1) { ans += max(A[i], B[i]); odd ^= (A[i] > B[i]); S.insert(abs(A[i] - B[i])); } while(Q--) { ll a, x, y; cin >> a >> x >> y; a--; if(a == 0 || a == 2 * N - 1) { ans += x - A[a]; A[a] = x; } else { odd ^= (A[a] > B[a]); odd ^= (x > y); ans += max(x, y) - max(A[a], B[a]); S.erase(S.lower_bound(abs(A[a] - B[a]))); S.insert(abs(x - y)); A[a] = x; B[a] = y; } cout << (!odd ? ans : ans - (*S.begin())) << "\n"; } }