AtCoder Beginner Contest 408 D,E,F,G問題メモ

from itertools import groupby


def solve(n, s):
    rlc = []
    for c, itr in groupby(s):
        rlc.append((int(c), len(list(itr))))
    if rlc[0][0] == 1:
        rlc.insert(0, (0, 0))
    if rlc[-1][0] == 1:
        rlc.append((0, 0))
    if len(rlc) == 1:
        return 0

    dp0 = 0
    dp1 = 1 << 60
    dp2 = 1 << 60
    for c, l in rlc:
        if c == 0:
            dp2 = min(dp1, dp2)
            dp1 += l
        else:
            dp1 = min(dp1, dp0)
            dp0 += l
            dp2 += l
    return dp2


t = int(input())
for _ in range(t):
    n = int(input())
    s = input()
    ans = solve(n, s)
    print(ans)

import sys

input = sys.stdin.buffer.readline


def dfs(n, links, shift, use_ok):
    """ 辺コストを >> shift した値で、use_ok が0のbitが1になっている辺は使わないで行けるか？ """
    reachable = [False] * n
    reachable[0] = True
    q = [0]
    while q:
        u = q.pop()
        for v, w in links[u]:
            if reachable[v]:
                continue
            w >>= shift
            if w | use_ok != use_ok:
                continue
            reachable[v] = True
            q.append(v)
    return reachable[n - 1]


def solve(n, m, edges):
    links = [[] for _ in range(n)]
    for u, v, w in edges:
        u -= 1
        v -= 1
        links[u].append((v, w))
        links[v].append((u, w))
    ans = 0
    for shift in range(29, -1, -1):
        if dfs(n, links, shift, ans):
            ans = ans << 1
        else:
            ans = (ans | 1) << 1
    ans >>= 1
    return ans


n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]
ans = solve(n, m, edges)
print(ans)

from heapq import heappop, heappush
import os
import sys

import numpy as np


def solve(inp):
    n = inp[0]
    d = inp[1]
    r = inp[2]
    hhh = inp[3:]

    # == LazySegmentTree ==
    # Numbaで使うにあたり、いくつかのアドホックな使用方法に注意する。
    # ・data, lazyは2次元配列 (index, 1要素当たりのデータ数) で、Numbaで扱える型。それぞれで型は全て揃える必要がある。
    # ・関数定義(prefixの"lst_"は省略)
    #     operation(i,j,k):  data[k] に data[i]+data[j] を上書き更新
    #     mapping(i,j)    :  data[i] に lazy[j] を上書き反映
    #     composition(i,j):  lazy[i] に lazy[j] を上書き反映
    #     initialize_data(i): data[i] を単位元に戻す
    #     initialize_lazy(i): lazy[i] を単位元に戻す
    # ・初期配列があるときでも、自動的に構築はされないので、自前で前計算しておく
    # ・range_update(l,r) の前には、lazy[0] に更新用の値を埋め込んでおいてから呼ぶ

    lst_n = n  # CUSTOMIZABLE
    lst_depth = 0
    _n = lst_n
    while _n:
        _n >>= 1
        lst_depth += 1
    lst_offset = 1 << lst_depth

    # CUSTOMIZABLE
    lst_data = np.zeros((lst_offset << 1) + 2, np.int64)
    lst_lazy = np.zeros(lst_offset, np.int64)

    def lst_operation(i, j, k):
        lst_data[k] = max(lst_data[i], lst_data[j])

    def lst_mapping(i, j):
        lst_data[i] = max(lst_data[i], lst_lazy[j])

    def lst_composition(i, j):
        lst_lazy[i] = max(lst_lazy[i], lst_lazy[j])

    def lst_initialize_lazy(i):
        lst_lazy[i] = 0

    # /CUSTOMIZABLE

    def lst_push(i):
        if i < lst_offset:
            lch = i << 1
            rch = lch + 1
            lst_mapping(lch, i)
            lst_mapping(rch, i)
            if lch < lst_offset:
                lst_composition(lch, i)
                lst_composition(rch, i)
            lst_initialize_lazy(i)

    def lst_update(i):
        lch = i << 1
        rch = lch + 1
        lst_operation(lch, rch, i)

    def lst_all_apply(i):
        lst_mapping(i, 0)
        if i < lst_offset:
            lst_composition(i, 0)

    def lst_propagate(l, r):
        for i in range(lst_depth, 0, -1):
            if ((l >> i) << i) != l:
                lst_push(l >> i)
            if ((r >> i) << i) != r:
                lst_push((r - 1) >> i)

    def lst_range_update(l, r):
        """ lst_lazy[0] に更新したい値を入れてから呼ぶ """
        l += lst_offset
        r += lst_offset
        lst_propagate(l, r)

        l2 = l
        r2 = r
        while l < r:
            if (l & 1) == 1:
                lst_all_apply(l)
                l += 1
            if (r & 1) == 1:
                r -= 1
                lst_all_apply(r)
            l >>= 1
            r >>= 1
        l = l2
        r = r2

        for i in range(1, lst_depth + 1):
            if ((l >> i) << i) != l:
                lst_update(l >> i)
            if ((r >> i) << i) != r:
                lst_update((r - 1) >> i)

    def lst_point_get(p):
        p += lst_offset
        for i in range(lst_depth, 0, -1):
            lst_push(p >> i)
        return lst_data[p]

    ggg = np.argsort(hhh)
    task = [(n, n, n, n)]  # (-x,l,r,y): xが今処理中のh以上の時、[l,r)をyでchmax
    task.clear()
    ans = 0
    for gi in range(n - 1, -1, -1):
        i = ggg[gi]
        h = hhh[i]
        while len(task) > 0 and -task[0][0] >= h:
            x, left, right, y = heappop(task)
            lst_lazy[0] = y
            lst_range_update(left, right)

        best = lst_point_get(i)
        ans = max(ans, best)
        left = max(0, i - r)
        right = min(n, i + r + 1)
        heappush(task, (-(h - d), left, right, best + 1))

    return ans


SIGNATURE = '(i8[:],)'
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', SIGNATURE)(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit(SIGNATURE, cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(ans)

def euclid_history(a, b):
    result = []
    while b > 0:
        d, m = divmod(a, b)
        result.append(d)
        a, b = b, m
    return a, result


def solve(a, b, c, d):
    gcd_ab, his1 = euclid_history(a, b)
    gcd_cd, his2 = euclid_history(c, d)
    a //= gcd_ab
    b //= gcd_ab
    c //= gcd_cd
    d //= gcd_cd
    his1[-1] -= 1
    his2[-1] -= 1

    la = 0
    lb = 1
    ca = 1
    cb = 1
    ra = 1
    rb = 0
    direction = 1

    def dig(k):
        nonlocal la, lb, ca, cb, ra, rb, direction
        if direction == 1:
            la, lb, ca, cb = ca + (k - 1) * ra, cb + (k - 1) * rb, ca + k * ra, cb + k * rb
        else:
            ca, cb, ra, rb = k * la + ca, k * lb + cb, (k - 1) * la + ca, (k - 1) * lb + cb

    for i in range(min(len(his1), len(his2))):
        x = his1[i]
        y = his2[i]
        dig(min(x, y))
        if x == y:
            direction ^= 1
            continue

        if x < y:
            if i < len(his1) - 1:
                return cb
            else:
                remain = [y - x] + his2[i + 1:]
                break

        if x > y:
            if i < len(his2) - 1:
                return cb
            else:
                remain = [x - y] + his1[i + 1:]
                break

    else:
        if len(his1) < len(his2):
            remain = his2[len(his1):]
        else:
            remain = his1[len(his2):]

    if remain[0] > 1:
        dig(1)
        return cb

    if len(remain) == 1:
        return b + d

    for di in range(2):
        dig(remain[di])
        direction ^= 1

    if len(remain) == 2:
        direction ^= 1
        dig(1)

    return cb


t = int(input())
for _ in range(t):
    a, b, c, d = map(int, input().split())
    ans = solve(a, b, c, d)
    print(ans)