# **[2020/01/28 Shichifuku04](https://onlinejudge.u-aizu.ac.jp/services/room.html#shichifuku04/)**
# **A. Bit String Reordering**
問題見てない.
# **C. Shopping**
## 読解
一次元上に $1$ ~ $N$ の店が並んでいて隣同士の間隔は $1$. $m$ 個の制約 (店 $c$ は店 $d$ の後に訪れないといけない) が与えられるので, 店 $1$ から店 $N$ までの最短経路を求める. (実際には $+1$ したものを出力する.)

## 解法
よく見ると $c < d$ なので, 右に向かって左に向かって右に向かえば良い. 重なっている区間ごとに分けて考えれば正しく求まる.
# **E. Automotive Navigation**
問題見てない.
# **G. Flipping Parentheses**
## 読解
正しい括弧列に対して, 各クエリで列中の $1$ 文字が指定されるので反転し, 反転すると正しい括弧列に戻るような最も左の文字を求める (+反転する).
## 解法
正しい括弧列 $\iff$ 累積和がすべて正かつ (全体の和) $= 0$.
これを用いると,
- 反転する文字が '(' → 最も左の ')' を反転
- 反転する文字が ')' → '(' のうち, その文字より右の累積和がすべて $2$ 以上で最も左のものを反転

となる.
どちらもセグ木 (StarrySkyTree: 区間加算区間min) 上を二分探索することで実現可能.
## ソースコード

ll N, Q, A;
cin >> N >> Q;
string S;
cin >> S;
starry_sky_tree seg(N);
rep(i, N) seg.add(i + 1, N + 1, S[i] == '(' ? 1 : -1);
rep(i, Q) {
    cin >> A;
    if (S[A - 1] == '(') {
        S[A - 1] = ')';
        seg.add(A, N + 1, -2);
        ll ng = 0, ok = A;
        while (ok - ng > 1) {
            ll md = (ok + ng) / 2;
            if (seg.getmin(md, md + 1) < md) {
            // S[i] == ')' <=> 累積和[i] < i
                ok = md;
            } else {
                ng = md;
            }
        }
        cout << ok << rt;
        S[ok - 1] = '(';
        seg.add(ok, N + 1, 2);
    } else {
        S[A - 1] = '(';
        seg.add(A, N + 1, 2);
        ll ng = 0, ok = A;
        while (ok - ng > 1) {
            ll md = (ok + ng) / 2;
            if (seg.getmin(md, N) >= 2) {
            // 累積和[i, N) >= 2
                ok = md;
            } else {
                ng = md;
            }
        }
        cout << ok << rt;
        S[ok - 1] = ')';
        seg.add(ok, N + 1, -2);
    }
}

## コメント
これを 30 分以内に通せたのは嬉しい.

# **I. Sweet War**
## 読解
よくある取り合いゲーム. チョコレート ($1$ ~ $N$) にはそれぞれにパラメータ $S,\ R$ があり, $2$ 人は交互に順に以下の行動をする.
- pass する. 満腹度が $1$ 減る. (満腹度の初期値は $2$ 人それぞれ $A,\ B$.)
- eat する. 一番上のチョコレートを食べ, 満腹度が $S$ 増え, 得点が $R$ 増える.

## コンテスト中の考察
とりあえず満腹度の上限が小さいと仮定する ($\sum S$ がかなり小さいため). ゲーム DP なので後ろから DP したい. が, バグらせて答えが合わない.

# **K. $L_\infty$ Jumps**
## 読解
毎回同じ半径の正方形のマスにジャンプできるので, $(0,\ 0)$ から $(s,\ t)$ へちょうど $N$ 回で行く最小コストを求める. ただし, ジャンプのコストは各回で変更され, それぞれ $(+x,\ +y)$ のコストが $1$ で反時計回りに $1$ ずつ増加.

## コンテスト中の考察
まず, ジャンプする方向 (NEWS) とその回数を決め打つと, 到達可能性については範囲に変換される. また, コストが平等なので, 割と貪欲にとっても問題なさそう.

## コメント
最終的には DP らしい. 本番で通したチーム $0$ らしい.