AtCoder ABC234 個人的メモ

A - Weird Function

def f(x):
    return x ** 2 + 2 * x + 3

t = int(input())

ans = f(f(f(t) + t) + f(f(t)))
print(ans)

B - Longest Segment

$N\leq 100$なので、2個の点の選び方を全探索しても全部で$10^4$通りしかない。
なので点の選び方を全探索して、それぞれの点を結ぶ線分の長さを求めればおｋ。

N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]

ans = 0
for a, b in A:
    for c, d in A:
        ans = max(ans, ((a - c) ** 2 + (b - d) ** 2) ** 0.5)

print(ans)

C - Happy New Year!

0,2からなる正整数ではなく、0,1からなる生成数のうちで$K$番目に小さいものを考える。
これは$K$を2進法で表現すれば良い。
0,2からなる正整数の場合は1を2にすればおｋ。

K = int(input())

K = f"{K:b}"
ans = K.replace("1", "2")

print(ans)

D - Prefix K-th Max

「$P$の先頭$i$項のうち、$K$番目に大きい数」は$P$の先頭$i$項がソートされた状態で保持されていれば、二分探索を使って$O(\log_2 N)$で求めることができる。
これならば全体の計算量は$O(N\log_2 N)$となるので、十分高速に計算できる。
$P$の先頭$i$項をソートされた状態保持するにはフェニック木を使えばおｋ。

フェニック木の実装

class fenwick:
    """Fenwick Tree (Binary Indexed Tree)

    This is a data structure that can efficiently update elements
    and calculate prefix sums (cumulative sum from the head of list)
    in a table of numbers.

    To use this class, first initialize the table using the constructor.
    Constructor build a table with only one element.
    At this time, if you use an iterable as an argument,
    you can initialize the tree with any iterable.

    This tree can use indexes from 1 to n + 1.
    This is to use the least signigicant bit(LSB) to simplify the migration.

    2の補数を使った頂点間の遷移の話とかのフェネック木の実装に関する話

    Attributes:
        table: List that records each element of the tree
        func : The function use for calculation. Defaults to sum.

    Raises:
        IndexError: An error occurred accessing unuse index.\
            The available index for this table is 1 or greater.
    """

    def __init__(self, init_iter: list = []):
        """Build fenwick tree.

        If arg is nothing, tree initialized by a 0-element is built.
        If arg is iterable, tree initialized by the iterable is built.

        Args:
            init_iter (list, optional): Iterable used for initialization.\
                Defaults to [].
        """
        self.table = [0]
        for x in init_iter:
            self.push(x)

    def push(self, x: int = 0):
        """Update the tree by adding elements to the end of the table.

        Args:
            x (int): Element x to be added. Defaults to 0.
        """
        num_elems = len(self.table)
        index = 1
        lsb = num_elems & -num_elems  # lsb represents 2's compelemtnt
        while index != lsb:           # Update other elements
            x += self.table[num_elems - index]
            index *= 2

        self.table.append(x)          # Add new element

    def sum(self, i: int) -> int:
        """Caliculate [0, i] prefix sums (Σ[j=0..i-1]tree_j).

        Args:
            i (int): Last index of the prefix sums range

        Raises:
            IndexError: See base class.
        """
        # if i == 0:
        #     raise IndexError("Can't use 0-index. Check docstrings for details.")
        prefix_sum = 0
        while i > 0:
            prefix_sum += self.table[i]
            i -= i & -i
        return prefix_sum

    def add(self, i: int, x: int):
        """Add x to the element of index i.

        Args:
            i (int): Index of element
            x (int): Number to be added

        Raises:
            IndexError: See base class.
        """
        if i == 0:
            raise IndexError(
                "Can't use 0-index. Check docstrings for details.")
        while i < len(self.table):
            self.table[i] += x
            i += i & -i

N, K = map(int, input().split())
P = list(map(int, input().split()))

lst = fenwick([0] * N)
for i, p in enumerate(P):
    lst.add(p, 1)
    if i + 1 < K:
        continue

    ok = N
    ng = 0
    lower_num_cnt = i + 2 - K
    while ok - ng > 1:
        mid = (ng + ok) // 2
        if lst.sum(mid) >= lower_num_cnt:
            ok = mid
        else:
            ng = mid

    print(ok)

E - Arithmetic Number

$X\leq 10 ^{17}$なので、解となる等差数は最大でも$10^{18}$以下になりそうと分かる。
$10^{18}$以下の等差数を考えるとあんまり数が多くなさそう。
なので、$10^{18}$以下の等差数を全列挙した後に$X$以上の最小の等差数を求めればおｋ。

from bisect import bisect_left

X = int(input())
N = 18

arithmetic_nums = set()
for start in range(1, 10):
    arithmetic_nums.add(start)
    for diff in range(-9, 10):
        d_lst = [start]
        for _ in range(N):
            next_num = d_lst[-1] + diff
            if not 0 <= next_num < 10:
                break
            d_lst.append(next_num)
            arithmetic_nums.add(int("".join(map(str, d_lst))))

sorted_nums = sorted(arithmetic_nums)
ans = sorted_nums[bisect_left(sorted_nums, X)]

print(ans)