---
tags: Programming Contest
---

# AtCoder Beginner Contest 223 題解

## 心得

比賽中解五題，都一次 AC，開心（直到看到 vtuber 最後五分鐘竟然過 F），積分 +71。

另外雖然我聽不懂日語也看不懂日文，但仍想推廣一下這個 vtuber [RinSakamichi](https://atcoder.jp/users/RinSakamichi)。她三年前就出道，二年前開始打 atcoder，從以前只能解出三題到這次解出六題，一直在進步，但 youtube 上一直沒什麼觀眾，訂閱數也才 1.1K。若有人感興趣可以去追蹤一下。也許是出於興趣，她三年都沒什麼起色還一直做下去，讓人覺得了不起。

## A, B

(〃∀〃)

## C. [Doukasen](https://atcoder.jp/contests/abc223/tasks/abc223_c)

比賽時沒想到總花費時間除 2 就是相遇的時間，二分搜直接開幹。

二分搜相遇的位置，檢查函式為 check(pos) 看「從左邊到 pos 所花的時間」是否大於「從右邊到 pos 所花的時間」。

二分搜的下界是 0，上界是 A 的和。在這個區間中 check 的分佈是 0 0 0 1 1 1。題目所求就是最後一個 0 的位置。因為是在浮點數上二分搜，所以用固定次數的版本。

N = int(input())
A, B = [], []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
S = sum(A)

def check(pos):
    pref = 0
    timeL = 0
    for a, b in zip(A, B):
        if pref <= pos <= pref + a:
            d = pos - pref
        else:
            d = a
        timeL += d / b
        pref += d
        
    suff = 0
    timeR = 0
    for a, b in zip(reversed(A), reversed(B)):
        if S - (suff + a) <= pos <= (S - suff):
            d = S - suff - pos
        else:
            d = a
        timeR += d / b
        suff += d

    return timeL > timeR

lb, ub = 0, S
for _ in range(100):
    m = (lb + ub) / 2
    if check(m):
        ub = m
    else:
        lb = m
print(lb)

## D. [Restricted Permutation](https://atcoder.jp/contests/abc223/tasks/abc223_d)

畫一下可以發現，將 input 轉成 DAG 後 topological sort 即可。字典序的部份就將 queue 轉成用 priority queue。

from heapq import heappop, heappush


N, M = map(int, input().split())
G = [[] for _ in range(N)]
inD = [0 for _ in range(N)]
for _ in range(M):
    u, v = map(int, input().split())
    u, v = u - 1, v - 1
    G[u].append(v)
    inD[v] += 1

que = [u for u in range(N) if inD[u] == 0]
ans = []
while len(que) > 0:
    u = heappop(que)
    ans.append(u + 1)
    for v in G[u]:
        inD[v] -= 1
        if inD[v] == 0:
            heappush(que, v)

if len(ans) == N:
    print(' '.join(map(str, ans)))
else:
    print(-1)

## E. [Placing Rectangles](https://atcoder.jp/contests/abc223/tasks/abc223_e)


在紙上畫了一下，去掉交換與旋轉，會發現就只有兩種分割方式。所以就兩種 case 都試試看可不可行。旋轉的部份透過 X, Y 的全排列，交換透過 A, B, C 的全排列解決。

def ceil_div(x, y):
    return (x + y - 1) // y


def check(x, y, a, b, c):
    # Case 1
    ha = ceil_div(a, x)
    hb = ceil_div(b, x)
    hc = ceil_div(c, x)
    if ha + hb + hc <= y:
        return True
    # Case 2
    ha = ceil_div(a, x)
    hbc = y - ha
    if hbc > 0:
        wb = ceil_div(b, hbc)
        wc = ceil_div(c, hbc)
        if wb + wc <= x:
            return True
    return False


from itertools import permutations

X, Y, A, B, C = map(int, input().split())
ans = False
for (x, y) in permutations([X, Y]):
    for (a, b, c) in permutations([A, B, C]):
        if check(x, y, a, b, c):
            ans = True
print('Yes' if ans else 'No')

## F. [Parenthesis Checking](https://atcoder.jp/contests/abc223/tasks/abc223_f)

官方題解看不懂，看了前面說的 vtuber 的 [submission](https://atcoder.jp/contests/abc223/submissions/26651828) 才想通。
沒寫過類似題這題不太可能自己想出來吧，我覺得比第五題難上不少。

將左括號視為 +1，右括號視為 -1，得到的數列的**前綴**為 P：

| S: | ( | ( | ( | ) | ) | ) | ( |
| --- | --- | --- | --- | --- | --- | --- | --- |
| P: | 1 | 2 | 3 | 2 | 1 | 0 | 1 |

如果詢問的區間 [l, r] 是 correct 的，也就是說

1. S[l] = '(' 且 S[r] = ')'
2. [l, r] 的左括號數 = 右括號數，即 P[r] - P[l - 1] = 0。這個條件只考慮了數量，沒考慮順序是不是合理的，順序的部份為條件 3。
3. 這個區間中的 P 值都不能小於 P[l] - 1。若發生，代表從左至右遇到的右括號比左括號多。另外 P[r] 必需是 P[l] - 1，所以 min(P[l], P[l + 1], ..., P[r]) = P[l] - 1。

使用線段樹來存 P，因為我們想知道任意區間的最小值來實作條件 3。

交換操作的情況如下：

| S: | ( | ( | ) | ) | ) | ( | ( |
| --- | --- | --- | --- | --- | --- | --- | --- |
| P: | 1 | 2 | 1 | 0 | -1 | 0 | 1 |
| | | | l | | | r | |

跟前面的表格相比，可以發現：
1. l 以左（不含 l）的 P 值不變。
2. r 以右（包含 r）的 P 值不變。
3. [l, r - 1] 的 P 值都 -2，這是因為位置 l 從左括號變成右括號，因為 P 是前綴，所 [l, r - 1] 的值都 -2 了。

#include <algorithm>
#include <atcoder/lazysegtree>
#include <iostream>
#include <vector>
using namespace std;

using S = int;
using F = int;
S op(S a, S b) { return min(a, b); }
S default_val() { return 0x3f3f3f3f; }
S apply_lazy(F lazy, S val) { return lazy + val; }
F push_lazy(F parent, F child) { return parent + child; }
F default_lazy() { return 0; }
using SegTree = atcoder::lazy_segtree<S, op, default_val, F, apply_lazy,
                                      push_lazy, default_lazy>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;
    string S;
    cin >> S;

    vector<int> P(N, 0);
    P[0] = ((S[0] == '(') ? +1 : -1);
    for (int i = 1; i < N; i++) {
        P[i] = P[i - 1] + ((S[i] == '(') ? +1 : -1);
    }

    SegTree seg(P);

    while (Q--) {
        int cmd, l, r;
        cin >> cmd >> l >> r;
        l--;
        r--;
        if (cmd == 1) {
            if (S[l] == '(' and S[r] == ')') {
                seg.apply(l, r, -2);
                swap(S[l], S[r]);
            } else if (S[l] == ')' and S[r] == '(') {
                seg.apply(l, r, +2);
                swap(S[l], S[r]);
            }
        } else { // closed interval [l, r]
            // endpoint check
            bool check1 = S[l] == '(' and S[r] == ')';
            // bracket balance
            bool check2 = seg.get(r) - ((l > 0) ? seg.get(l - 1) : 0) == 0;
            // cannot drop under P[l] - 1
            bool check3 = seg.prod(l, r + 1) == seg.get(l) - 1;

            if (check1 and check2 and check3) {
                cout << "Yes" << endl;
            } else {
                cout << "No" << endl;
            }
        }
    }

    return 0;
}

:::success
[< 回到所有題解](https://hackmd.io/@amoshyc/HkWWepaPv/)
:::