AtCoder Regular Contest 203 (Div. 2)A,B,C,D,E問題メモ

まず、異なる2チームの全勝者数の合計は、$M$ より大きくできない。
さもないと、全勝者同士のマッチングを避けられなくなり、そのマッチではどちらかが負けるので矛盾する。

各チームの全勝者数を、大きい方から順に $W_1,W_2,...,W_N$ とする。
$i=1$ 以外の $W_i$ は、$\lfloor \frac{M}{2} \rfloor$ でなければならない。
その時、$W_1$ は $lceil \frac{M}{2} \rceil$ にできる。

def solve(n, m):
    if m % 2 == 0:
        return n * m // 2
    return n * (m // 2) + 1


t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    ans = solve(n, m)
    print(ans)

操作は可逆なので、どのような初期状態でも、ある「標準形」に必ず変換できることを示せばよい。
A→標準形→(逆に操作して)→B という変換が可能となる。

標準形を '0000…01111…1' という形と定める。

「最も左端の'1'」と、「左端以外にある'01'」を入れ替えることを繰り返せば、必ず標準形になる。

def solve(n, aaa, bbb):
    if aaa == bbb:
        return True
    sa = sum(aaa)
    sb = sum(bbb)
    if sa != sb:
        return False
    if sa >= 2:
        return True
    if aaa[0] == 0 and aaa[-1] == 0 and bbb[0] == 0 and bbb[-1] == 0:
        return True
    return False


t = int(input())
for _ in range(t):
    n = int(input())
    aaa = list(map(int, input().split()))
    bbb = list(map(int, input().split()))
    ans = solve(n, aaa, bbb)
    if ans:
        print('Yes')
    else:
        print('No')

def precompute_factorials(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f = f * m % MOD
        factorials.append(f)
    f = pow(f, MOD - 2, MOD)
    finvs = [1] * (n + 1)
    finvs[n] = f
    for m in range(n, 1, -1):
        f = f * m % MOD
        finvs[m - 1] = f
    return factorials, finvs


MOD = 998244353
facts, finvs = precompute_factorials(400000, MOD)


def solve(h, w, k):
    if k < h + w - 2:
        return 0
    base_pattern = facts[h + w - 2] * finvs[h - 1] % MOD * finvs[w - 1] % MOD
    remaining_wall = ((h - 1) * w + h * (w - 1) - (h + w - 2)) % MOD

    if k == h + w - 2:
        return base_pattern
    if k == h + w - 1:
        return base_pattern * remaining_wall % MOD

    ans = base_pattern * remaining_wall % MOD * (remaining_wall - 1) % MOD * pow(2, -1, MOD) % MOD
    ans -= facts[h + w - 3] * finvs[h - 2] % MOD * finvs[w - 2] % MOD

    if h >= 3:
        tmp = facts[h + w - 2] * finvs[h - 3] % MOD * finvs[w]
        tmp -= facts[h + w - 2] * finvs[h - 3] % MOD * finvs[w + 1] * 2
        ans += tmp
        ans %= MOD

    if w >= 3:
        tmp = facts[h + w - 2] * finvs[h] % MOD * finvs[w - 3]
        tmp -= facts[h + w - 2] * finvs[h + 1] % MOD * finvs[w - 3] * 2
        ans += tmp
        ans %= MOD

    return ans


t = int(input())
for _ in range(t):
    h, w, k = map(int, input().split())
    ans = solve(h, w, k)
    print(ans)

from enum import Enum, auto


class SegmentTreeInjectable:
    """
    単位元生成関数 identity_factory と二項演算関数 func を外部注入するセグメント木

    [生成]
    SegmentTreeInjectable(n, identity_factory, func)
    SegmentTreeInjectable.from_array(array, identity_factory, func)  # 既存の配列より作成

    [関数]
    add(i, x)               Aiにxを加算
    update(i, x)            Aiをxに書き換え
    get_range(a, b)         [a, b) の集約値を得る
    get_all()               全ての集約値を得る
    get_point(i)            Aiを得る
    leftmost(a, b, x, ev)   [a, b) の範囲で、ev(x, Ai)=True となる最も左の i を得る（前提条件あり）
    rightmost(a, b, x, ev)  [a, b) の範囲で、ev(x, Ai)=True となる最も右の i を得る（前提条件あり）
    debug_print()           深さ毎に整形して出力する
    """

    def __init__(self, n, identity, func):
        n2 = 1 << (n - 1).bit_length()
        self.offset = n2
        self.tree = [identity] * (n2 << 1)
        self.func = func
        self.identity = identity

    @classmethod
    def from_array(cls, arr, identity_factory, func):
        """ 既存の配列から生成 """
        ins = cls(len(arr), identity_factory, func)
        ins.tree[ins.offset:ins.offset + len(arr)] = arr
        for i in range(ins.offset - 1, 0, -1):
            l = i << 1
            r = l + 1
            ins.tree[i] = func(ins.tree[l], ins.tree[r])
        return ins

    def add(self, i, x):
        """
        Aiにxを加算
        :param i: index (0-indexed)
        :param x: add value
        """
        i += self.offset
        self.tree[i] = self.func(self.tree[i], x)
        self.__upstream(i)

    def update(self, i, x):
        """
        Aiの値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.offset
        self.tree[i] = x
        self.__upstream(i)

    def __upstream(self, i):
        tree = self.tree
        func = self.func
        while i > 1:
            i >>= 1
            lch = i << 1
            rch = lch | 1
            tree[i] = func(tree[lch], tree[rch])

    def get_range(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        tree = self.tree
        func = self.func
        result_l = self.identity
        result_r = self.identity

        l = a + self.offset
        r = b + self.offset
        while l < r:
            if r & 1:
                result_r = func(tree[r - 1], result_r)
            if l & 1:
                result_l = func(result_l, tree[l])
                l += 1
            l >>= 1
            r >>= 1

        return func(result_l, result_r)

    def get_all(self):
        return self.tree[1]

    def get_point(self, i):
        return self.tree[i + self.offset]

    def leftmost(self, a, b, x, ev):
        """
        [a, b) の範囲で、ev(x, 値) = True となる最初の index を得る。存在しない場合は-1。

        使用できる条件:
        [l, r) の集約値を y としたとき、ev(x, y)=True となることが、
        l <= i < r 内に ev(x, Ai)=True となる要素があることと等しい。（(func, ev) = (min,ge), (max,le) など）
        """
        tree = self.tree
        l = a + self.offset
        r = b + self.offset
        r_found = -1
        while l < r:
            if l & 1:
                if ev(x, tree[l]):
                    return self._leftmost_sub(l, x, ev)
                l += 1
            if r & 1:
                if ev(x, tree[r - 1]):
                    r_found = r - 1
            l >>= 1
            r >>= 1

        if r_found == -1:
            return -1

        return self._leftmost_sub(r_found, x, ev)

    def _leftmost_sub(self, i, x, ev):
        """
        tree-index i が示す範囲で、ev(x, Aj)=True となる最も左のarray-index j を得る
        （tree[i] が示す範囲には条件を満たすものが必ず存在する前提とする）
        """
        tree = self.tree
        while i < self.offset:
            l = i << 1
            if ev(x, tree[l]):
                i = l
            else:
                i = l + 1
        return i - self.offset

    def rightmost(self, a, b, x, ev):
        """
        [a, b) の範囲で、ev(x, 値) = True となる最後の index を得る。存在しない場合は-1。

        使用できる条件:
        [l, r) の集約値を y としたとき、ev(x, y)=True となることが、
        l <= i < r 内に ev(x, Ai)=True となる要素があることと等しい。（(func, ev) = (min,ge), (max,le) など）
        """
        tree = self.tree
        l = a + self.offset
        r = b + self.offset
        l_found = -1
        while l < r:
            if r & 1:
                if ev(x, tree[r - 1]):
                    return self._rightmost_sub(r - 1, x, ev)
            if l & 1:
                if ev(x, tree[l]):
                    l_found = l
                l += 1
            l >>= 1
            r >>= 1

        if l_found == -1:
            return -1

        return self._rightmost_sub(l_found, x, ev)

    def _rightmost_sub(self, i, x, ev):
        """
        tree-index i が示す範囲で、ev(x, Aj)=True となる最も右のarray-index j を得る
        （tree[i] が示す範囲には条件を満たすものが必ず存在する前提とする）
        """
        tree = self.tree
        while i < self.offset:
            l = i << 1
            if ev(x, tree[l + 1]):
                i = l + 1
            else:
                i = l
        return i - self.offset

    def debug_print(self):
        i = 1
        while i <= self.offset:
            print(self.tree[i:i * 2])
            i <<= 1


class State(Enum):
    N = auto()  # 空文字
    O = auto()  # 単独の 0
    I_ = auto()  # 左端が 1..
    OO_ = auto()  # 左端が 00..
    OI_ = auto()  # 左端が 01..
    _I = auto()  # 右端が ..1
    _OO = auto()  # 右端が ..00
    _IO = auto()  # 右端が ..10


def solve(n, aaa, q, queries):
    # (左State, 右State, 省略できる文字数)
    def merge(a, b):
        if a[1] == State.N:
            return b
        if b[0] == State.N:
            return a
        if a[1] == State.O:
            if b[0] == State.O:
                return (State.OO_, State._OO, 0)
            if b[0] == State.I_:
                return (State.OI_, b[1], b[2])
            if b[0] == State.OO_:
                return (State.OO_, b[1], b[2] + 1)
            if b[0] == State.OI_:
                return (State.OO_, b[1], b[2])
        if a[1] == State._I:
            if b[0] == State.O:
                return (a[0], State._IO, a[2])
            if b[0] == State.I_:
                return (a[0], b[1], a[2] + b[2] + 1)
            if b[0] == State.OO_:
                return (a[0], b[1], a[2] + b[2])
            if b[0] == State.OI_:
                return (a[0], b[1], a[2] + b[2] + 2)
        if a[1] == State._OO:
            if b[0] == State.O:
                return (a[0], State._OO, a[2] + 1)
            if b[0] == State.I_:
                return (a[0], b[1], a[2] + b[2])
            if b[0] == State.OO_:
                return (a[0], b[1], a[2] + b[2] + 2)
            if b[0] == State.OI_:
                return (a[0], b[1], a[2] + b[2] + 1)
        if a[1] == State._IO:
            if b[0] == State.O:
                return (a[0], State._OO, a[2])
            if b[0] == State.I_:
                return (a[0], b[1], a[2] + b[2] + 2)
            if b[0] == State.OO_:
                return (a[0], b[1], a[2] + b[2] + 1)
            if b[0] == State.OI_:
                return (a[0], b[1], a[2] + b[2])

    init = [(State.O, State.O, 0) if a == 0 else (State.I_, State._I, 0) for a in aaa]
    sgt = SegmentTreeInjectable.from_array(init, (State.N, State.N, 0), merge)
    ans = []
    total = sum(aaa)
    for i in queries:
        i -= 1
        if aaa[i] == 0:
            aaa[i] = 1
            total += 1
            sgt.update(i, (State.I_, State._I, 0))
        else:
            aaa[i] = 0
            total -= 1
            sgt.update(i, (State.O, State.O, 0))

        if total == n:
            ans.append(n)
        else:
            res = sgt.get_all()
            if res[2] == n - 1:
                ans.append(2)
            else:
                ans.append(n - res[2])
    return ans


n = int(input())
aaa = list(map(int, input().split()))
q = int(input())
queries = [int(input()) for _ in range(q)]
ans = solve(n, aaa, q, queries)
print('\n'.join(map(str, ans)))

def iterate_without_hole(h, l, r):
    assert h % l == 1
    assert r % l == 1
    i = 1
    for _ in range(h // l):
        if i == r:
            i += 1
        yield i
        i += l


def put_square(i, j, l, n, m, hrz, vrt):
    if n > 0:
        for ii in range(i, i + l):
            hrz.append((ii, j))
        n -= l
    else:
        for jj in range(j, j + l):
            vrt.append((i, jj))
        m -= l
    return n, m


def solve(h, w, l, n, m, r, c):
    if h % l == 1 and w % l == 1 and r % l == 1 and c % l == 1:
        n -= w // l
        m -= h // l
        if not (n >= 0 and m >= 0 and n % l == 0 and m % l == 0):
            return None
        hrz = []
        for j in iterate_without_hole(w, l, c):
            hrz.append((r, j))
        vrt = []
        for i in iterate_without_hole(h, l, r):
            vrt.append((i, c))
        for bi in iterate_without_hole(h, l, r):
            for bj in iterate_without_hole(w, l, c):
                n, m = put_square(bi, bj, l, n, m, hrz, vrt)
        return hrz + vrt

    if h % l == l - 1 and w % l == l - 1 and r % l == 0 and c % l == 0:
        n -= (w + 1) // l * (l - 1)
        m -= (h + 1) // l * (l - 1)
        if not (n >= 0 and m >= 0 and n % l == 0 and m % l == 0):
            return None
        hrz = []
        vrt = []
        for j in range(1, c, l):
            for i in range(1, l):
                hrz.append((r + i, j))
        for j in range(c, w, l):
            for i in range(1, l):
                hrz.append((r - i, j))
        for i in range(1, r, l):
            for j in range(1, l):
                vrt.append((i, c - j))
        for i in range(r, h, l):
            for j in range(1, l):
                vrt.append((i, c + j))
        for i in range(1, r, l):
            for j in range(1, c - l + 1, l):
                n, m = put_square(i, j, l, n, m, hrz, vrt)
        for i in range(1, r - l + 1, l):
            for j in range(c, w, l):
                n, m = put_square(i, j, l, n, m, hrz, vrt)
        for i in range(r, h, l):
            for j in range(c + l, w, l):
                n, m = put_square(i, j, l, n, m, hrz, vrt)
        for i in range(r + l, h, l):
            for j in range(1, c, l):
                n, m = put_square(i, j, l, n, m, hrz, vrt)
        return hrz + vrt
    return None


def visualize(h, w, l, n, m, r, c, ans):
    if ans is None:
        return
    ans = [(i - 1, j - 1) for i, j in ans]
    field = [[''] * w for _ in range(h)]
    field[r - 1][c - 1] = '×'
    for i, j in ans[:n]:
        field[i][j] = '┝'
        field[i][j + l - 1] = '┥'
        for jj in range(j + 1, j + l - 1):
            field[i][jj] = '━'
    for i, j in ans[n:]:
        field[i][j] = '┰'
        field[i + l - 1][j] = '┸'
        for ii in range(i + 1, i + l - 1):
            field[ii][j] = '┃'
    for row in field:
        print(''.join(row))


t = int(input())
for _ in range(t):
    h, w, l, n, m, r, c = map(int, input().split())
    ans = solve(h, w, l, n, m, r, c)
    if ans is None:
        print('No')
    else:
        print('Yes')
        print('\n'.join(f'{a} {b}' for a, b in ans))
        # visualize(h, w, l, n, m, r, c, ans)