🦁

AtCoder ABC231 個人的メモ

2021/12/12に公開

Python

競技プログラミング

AtCoder

tech

A - Water Pressure

D = int(input())

print(D / 100)

B - Election

コンテスト中はcollections.Counter使ってacした。
他の人の見たらmax関数とかstatistics.modeとか使ってた。

# コンテスト中にacしたコード
from collections import Counter

N = int(input())
S = [input() for _ in range(N)]

cnt = Counter(S)

num = 0
ans = ""
for s in cnt.keys():
    if num < cnt[s]:
        num = cnt[s]
        ans = s

print(ans)

# max
N = int(input())
S = [input() for _ in range(N)]

print(max(S, key=S.count))

# statistics.mode
from statistics import mode

N = int(input())
S = [input() for _ in range(N)]

print(mode(S))

参考

C - Counting 2

各クエリで二分探索すれば良いなって思ったけどうまく実装できなかったので適当にやった。

生徒の身長 $A$ と質問 $X$ を降順(大きい順)でソートして、質問 $X$ を前から順に( $X$ の値が大きい順に)処理していくことを考える。
この時 $A$ と $X$ は広義単調減少になっているので、 $X$ の各値以上となる $A$ の要素の個数は尺取法の要領で解ける。

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

a_sort = sorted(A)
x_i_sort = sorted(((x, i) for i, x in enumerate(X)), reverse=True)
ans = [0] * Q
for x, i in x_i_sort:
    while a_sort and a_sort[-1] >= x:
        a_sort.pop()
    ans[i] = N - len(a_sort)

print(*ans, sep="\n")

# 二分探索
from bisect import bisect_left

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

A.sort()
for x in X:
    ans = N - bisect_left(A, x)
    print(ans)

D - Neighbors

グラフとして考える。
$N$ 個の頂点と $M$ 個の辺からなるグラフが与えられ、そのグラフが以下の条件を満たしているか判定すればおｋ。

全ての頂点の次数が $2$ 以下
閉路が無い

頂点の次数は計算量 $O(N)$ で求めれる。
閉路が無いということは各連結成分が木になっているということなので、dfsで計算量 $O(N+M)$ で判定できる。
両方調べても十分高速なのでこれでおｋ。

閉路探しは、union-findを使ってある辺の両端点が既に同じ連結成分に属していないか、を調べることでも判定できる。

from sys import setrecursionlimit

setrecursionlimit(10 ** 7)


def rec(now: int, parent: int):
    # 頂点nowが親でないのに探索済み = 閉路になっている
    if seen[now]:
        print("No")
        exit()

    seen[now] = 1
    for n_node in edge[now]:
        if n_node == parent:
            continue
        rec(n_node, now)
    return seen[now]


N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(lambda n: int(n) - 1, input().split())
    edge[x].append(y)
    edge[y].append(x)

if any(len(e) >= 3 for e in edge):
    print("No")
    exit()

seen = [0] * N
for n in range(N):
    if seen[n]:
        continue
    rec(n, -1)

print("Yes")

簡単のために $(A_i, B_i)=(A_j, B_j)(0\leq i,j\leq N)$ となる $(i,j)$ の組み合わせが無いとする。
まず青木君の嫉妬は無視して、高橋君が嫉妬しないような両者へのプレゼントの選び方を考える。
プレゼントを高橋君の嬉しさの昇順(小さい順)でソートする。
このとき $i$ 番目のプレゼントの高橋君にとっての嬉しさ $A_i$ は、それ以前の $j(0\leq j\leq i)$ 番目のプレゼントの嬉しさ $A_j$ 以上になっている。(狭義単調増加)
つまり、 $i$ 番目のプレゼントを高橋君に $j(0\leq j\leq i)$ 番目のプレゼントを青木君に渡すと、高橋君は嫉妬しない。
また、 $i$ 番目以降のプレゼントである $k(i<k\leq N)$ 番目のプレゼントを青木君に渡すと、高橋君は嫉妬する。
これで、高橋君が嫉妬しないプレゼントの選び方が計算量 $O(N\log N)$ で分かる。

$(A_i, B_i)=(A_k, B_k)(0\leq i,k\leq N)$ となる $(i,k)$ の組み合わせがあるとすると、 $i$ を高橋君に $k$ を青木君に渡しても高橋君が嫉妬しない場合がある。
なので $(A_i, B_i)=(A_k, B_k)$ となる $k$ の個数を $d$ とすると、 $i$ 番目のプレゼントを高橋君に渡す場合に高橋君に嫉妬させずに青木君に渡せるプレゼント $j$ は $0\leq j\leq i+d$ の範囲となる(実装ではまとめて処理してる)。

後は各 $i$ において青木君も嫉妬しない $j(0\leq j\leq i)$ の数を十分高速に数えることができればおｋ。
高橋君に $i$ 番目のプレゼントを渡した時に青木くんが嫉妬しないプレゼントの選び方の数は、 $B_i\leq B_j(0\leq j\leq i)$ となる $j$ の個数になる。
つまり配列 $cnt_{B_i}:=$ ( $B_i$ が $i$ 以前に $cnt_{B_i}$ 個ある)という配列を定義して、各 $i$ で $\sum_{j=B_i}^{max(B)} cnt_j$ を求めればおｋ。
これはプレゼントを $A$ の値で昇順かつ $A$ の値が等しい場合は $B$ の値の降順にソートしておいて、各 $i$ でフェニック木を使えば各 $i$ あたり $O(\log N)$ で求まるので十分高速。

配列 $cnt$ の長さは $B_i\leq 10^9$ より $10^9$ になり得るが、 $N\leq 2\times 10^5$ なので座標圧縮すれば $N$ 以下に収まる。

フェニック木

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.

    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

from operator import itemgetter
from collections import Counter

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

# 座標圧縮(Bの値をkeyとして座標圧縮後のiを返す)
# iが1始まりなのはフェニック木の実装の都合
num_to_i = {num: i for i, num in enumerate(sorted(set(B)), start=1)}
L = len(num_to_i)

# dup_cnt[(a, b)] := (a, b)となっているプレゼントが何個あるか
dup_cnt = Counter(zip(A, B))
no_dup_nums = list(dup_cnt.keys())
no_dup_nums.sort(key=itemgetter(1), reverse=True)
no_dup_nums.sort(key=itemgetter(0))

cnt = fenwick([0] * (L + 1))
ans = 0
for a, b in no_dup_nums:
    # cnt.add(i,x) := cntのインデックスiにxを加算する
    cnt.add(num_to_i[b], dup_cnt[(a, b)])

    # cnt.sum(r) := cntの区間[0,r]の区間和を求める
    # res = (cntの区間[B_i, N]の区間和)
    res = cnt.sum(L + 1) - cnt.sum(num_to_i[b] - 1)
    # 重複分を考慮
    res *= dup_cnt[(a, b)]
    ans += res

print(ans)

参考

ソートの安定性の話