AtCoder Regular Contest 173 A,B,C,D問題メモ

from bisect import bisect_left
from itertools import accumulate

digits = [0] * 16
for d in range(1, 16):
    digits[d] = pow(9, d)
digits = list(accumulate(digits))


def solve(k, d, prev):
    if d == -1:
        return 0
    under = 0
    for i in range(10):
        if i == prev:
            continue
        tmp = pow(9, d)
        if k <= under + tmp:
            return i * pow(10, d) + solve(k - under, d - 1, i)
        under += tmp


t = int(input())
for _ in range(t):
    k = int(input())
    d = bisect_left(digits, k)
    k -= digits[d - 1]

    ans = solve(k, d - 1, 0)
    print(ans)

from collections import Counter
from math import gcd

n = int(input())
points = [tuple(map(int, input().split())) for _ in range(n)]

lines = Counter()
for i in range(n):
    x1, y1 = points[i]
    for j in range(i + 1, n):
        x2, y2 = points[j]
        dx = x2 - x1
        dy = y2 - y1
        g = gcd(dx, dy)
        if dx < 0:
            g *= -1
        elif dx == 0 and dy < 0:
            g *= -1
        dx //= g
        dy //= g
        lines[dy, -dx, dx * y1 - dy * x1] += 1

_, cnt = lines.most_common(1)[0]
same_line = int((cnt * 2) ** 0.5) + 1
others = n - same_line
ans = min(others, n // 3)
print(ans)

セグメント木実装。

from operator import add, eq


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_factory, func):
        n2 = 1 << (n - 1).bit_length()
        self.offset = n2
        self.tree = [identity_factory() for _ in range(n2 << 1)]
        self.func = func
        self.idf = identity_factory

    @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.idf()
        result_r = self.idf()

        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


n = int(input())
aaa = list(map(int, input().split()))
aaa = [a - 1 for a in aaa]

pos = [0] * n
for i, a in enumerate(aaa, start=1):
    pos[a] = i


def sgt_update(i):
    b = aaa[i - 1]
    if i > 1:
        a = aaa[i - 2]
        if a < b:
            sgt.update(i - 1, 1)
        else:
            sgt.update(i - 1, 0)
    if i < n:
        c = aaa[i]
        if b > c:
            sgt.update(i, 1)
        else:
            sgt.update(i, 0)


def pattern_left():
    j = 1
    over = 0
    under = 0
    while i <= n - 2:
        if b < aaa[j]:
            over += 1
        else:
            under += 1
        j += 1
        if b < aaa[j]:
            over += 1
        else:
            under += 1
        j += 1
        if over != under:
            return j
    else:
        return -1


def pattern_right():
    j = n - 2
    over = 0
    under = 0
    while j >= 1:
        if b < aaa[j]:
            over += 1
        else:
            under += 1
        j -= 1
        if b < aaa[j]:
            over += 1
        else:
            under += 1
        j -= 1
        if over != under:
            return n - j - 1
    else:
        return -1


sgt = SegmentTreeInjectable.from_array([1] * (n + 2), lambda: 1, max)
ans = [0] * n
INF = 1 << 60
for b in range(n):
    i = pos[b]

    if i == 1:
        ans[i - 1] = pattern_left()
        sgt_update(i)
        continue

    if i == n:
        ans[i - 1] = pattern_right()
        sgt_update(i)
        continue

    a = aaa[i - 2]
    c = aaa[i]
    if (a < b) == (b > c):
        ans[i - 1] = 3
        sgt_update(i)
        continue

    l = sgt.rightmost(0, i - 1, 1, eq)
    r = sgt.leftmost(i + 1, n + 2, 1, eq)

    tmp = INF
    if l > 0:
        tmp = min(tmp, (i - l + 1) // 2 * 2 + 1)
    if r < n:
        tmp = min(tmp, (r - i + 2) // 2 * 2 + 1)
    if tmp == INF:
        tmp = -1
    ans[i - 1] = tmp

    sgt_update(i)

print(*ans)

珍しく、Pythonのグラフ探索ライブラリ NetworkX が使える問題。
（ただ、NetworkXは様々な様式を受け付ける分だけ、自前実装より遅くなりがちなことは事実で、 ペナルティが無いときに提出して「通った」と言うことはできるが、 コンテスト中にTLEの心配なく使えるかというとやっぱりまだいろいろと怖い）

import networkx as nx

n, m = map(int, input().split())
G1 = nx.DiGraph()
G2 = nx.DiGraph()
G1.add_nodes_from(range(n))
G2.add_nodes_from(range(n))
for _ in range(m):
    u, v, c = input().split()
    u = int(u) - 1
    v = int(v) - 1
    c = 1 if c == '(' else -1
    G1.add_edge(u, v, weight=c)
    G2.add_edge(u, v, weight=-c)

res1 = nx.negative_edge_cycle(G1)
res2 = nx.negative_edge_cycle(G2)

if res1 == res2:
    print('Yes')
else:
    print('No')