AtCoder ABC234 個人的メモ

2022/01/08に公開約5,100字

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通りしかない。
なので点の選び方を全探索して、それぞれの点を結ぶ線分の長さを求めればおk。

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。

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項をソートされた状態保持するにはフェニック木を使えばおk。

フェニック木の実装
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以上の最小の等差数を求めればおk。

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)

Discussion

ログインするとコメントできます