ABC260 回想(Python)

総括

ooooxxxx

defaultdictが大車輪の活躍を見せてくれました。

B問題はひらめきor実装力が求められる問題だったように思います。

_Ci_=10000×(100−_Ai_)+i という値を考え、この値についてソートすることを考えます。例えば A=(95,70,100,85)A=(95,70,100,85) とすると C=(50001,300002,3,150004)C=(50001,300002,3,150004) となり、これをソートすると (3,50001,150004,300002)(3,50001,150004,300002) となります。(C_i_Ci_ を 1000010000 で割った余りが受験者の番号に対応することに注意してください。)
https://atcoder.jp/contests/abc260/editorial/4455

_Ci_=10000×(100−_Ai_)+i なんて思いつかんやろ...defaultdictでkeyを得点、valueを番号にしてソートして解答した。

C問題はB問題に比べて特に考えることがなく、条件をそのまま実装すると通る。

D問題は最初にSortedSetの利用を考えたものの実装の経験値が低かったため、確信が持てず断念。defaultdictとdequeを用いて一から実装するハメになった。

A. A Unique Letter

問題文長さ 3 の文字列 S が与えられます。 S に 1 度だけ含まれる文字を 1 つ出力してください。但し、そのような文字が存在しない場合は代わりに -1 と出力してください。

制約 S は英小文字のみからなる 3 文字の文字列

Counterを用いて、一度だけ含まれるかどうか判定。

from collections import Counter

S = Counter(list(input()))
for k, v in S.items():
    if v == 1:
        print(k)
        exit()
print(-1)

B. Better Students Are Needed

番号を保持しつつ、得点順に並べるうまい方法をパッと思いつかなかったため、愚直に実装した。defaultdictでkeyを得点、valueを番号にしてソートして解答した。

▼解答

from collections import defaultdict

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

A_d = defaultdict(list)
B_d = defaultdict(list)
sum_d = defaultdict(list)
for i in range(N):
    a = A[i]
    b = B[i]
    A_d[a].append(i)
    B_d[b].append(i)
    sum_d[a + b].append(i)

A_d = sorted(A_d.items(), key=lambda x: x[0], reverse=True)
B_d = sorted(B_d.items(), key=lambda x: x[0], reverse=True)
sum_d = sorted(sum_d.items(), key=lambda x: x[0], reverse=True)

ans = list()

for k, v in A_d:
    for i in v:
        if X == 0:
            break
        ans.append(i)
        X -= 1
for k, v in B_d:
    for i in v:
        if i in ans:
            continue
        if Y == 0:
            break
        ans.append(i)
        Y -= 1

for k, v in sum_d:
    for i in v:
        if i in ans:
            continue
        if Z == 0:
            break
        ans.append(i)
        Z -= 1

for a in sorted(ans):
    print(a + 1)

A, B, 合計をそれぞれdefaultdictで持つという美しくない方法だったので、他の人の提出結果を見ていて、自分のやりたかったことのきれいな実装を見つけたので、下記に書いておく。

リストのなかにタプルでA, B, 合計を格納して、ソートする際のキーを変えることで、それぞれのソートを実現している。

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

AB = [(a, b, i + 1) for i, (a, b) in enumerate(zip(A, B))]
AB.sort(key=lambda x: x[0], reverse=True)  # aの得点が高い順にソート
ans = []
for j in range(X):
    ans.append(AB[j][2])
AB = AB[X:]  # 合格したx人を除く
AB.sort(key=lambda x: x[2])  # 番号順にソート
AB.sort(key=lambda x: x[1], reverse=True)  # bの得点が高い順にソート
for j in range(Y):
    ans.append(AB[j][2])
AB = AB[Y:]  # 合格したy人を除く
AB.sort(key=lambda x: x[2])  # 番号順にソート
AB.sort(key=lambda x: x[1] + x[0], reverse=True)  # a+bの得点が高い順にソート
for j in range(Z):
    ans.append(AB[j][2])

ans.sort()
for a in ans:
    print(a)

C. Changing Jewels

公式解説では再帰関数・動的計画法のいずれかを用いると解くことができるとあったが、別段計算量がきついわけではないので、そのまま実装したら通る。（B問題に時間がかかったのも相まって）C問題の割に行動の選択肢がなかったので、問題が間違っているのではないかと疑ったほどだった。

最初にレベルNの赤い宝石を1個だけを持っているので、どんどん赤い宝石と青い宝石に交換していくだけである。ここで、赤い宝石に交換するか青い宝石に交換するか、のような選択肢はなく、交換できるものをどんどん交換していくだけである。

レベルをkey、個数をvalueに持つdefaultdictで個数を管理して、最終的にblue[1]を出力しておわり。

from collections import defaultdict


def ex_red(n):
    cnt = red[n]
    red[n] = 0
    red[n - 1] += cnt
    blue[n] += X * cnt


def ex_blue(n):
    cnt = blue[n]
    blue[n] = 0
    blue[n - 1] += Y * cnt
    red[n - 1] += cnt


N, X, Y = map(int, input().split())
red = defaultdict(int)
blue = defaultdict(int)
red[N] += 1

for i in range(N, 1, -1):
    ex_red(i)
    ex_blue(i)
print(blue[1])

D. Draw Your Cards

冒頭にも書いたが、D問題は最初にSortedSetの利用を考えたものの実装の経験値が低かったため、確信が持てず断念。defaultdictとdequeを用いて一から実装した。

大きく判定は2つあって、引いたカードより大きいカードの有無（有るなら最小の数）とK枚重なっているかの2つである。

ここでSortedSetを考えたが、利用できなかった。そこで、defaultdictでkeyを場にでている一番上のカードの数、valueに重なっている数（一枚の場合でも自身も含める)で管理した。さらに、defaultdictのkeyを二分探索するのがめんどそうだったので、defaultdictとは別に場にでている表のカードの数のみを管理する配列を用意した。

つまり、場に出ているカードの数を二分探索して、重ねられる場合は重ねて（defaultdictに追加して）、valueの長さがKに達したらansに記録するという方法をとった。やっていることはほとんどsortedsetを利用したときの実装である...

from bisect import bisect_left
from collections import defaultdict, deque

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

ans = [-1] * (N + 1)
field_d = defaultdict(list)
field = deque()
for i in range(N):
    # print("P[i]", P[i])

    idx = bisect_left(field, P[i])
    if idx == 0 and len(field) == 0:
        field.appendleft(P[i])
        field_d[P[i]].append(P[i])
    elif idx == len(field):
        field.append(P[i])
        field_d[P[i]].append(P[i])
    else:
        field_d[P[i]] = field_d.pop(field[idx])
        field_d[P[i]].append(P[i])
        field[idx] = P[i]
    if len(field_d[P[i]]) == K:
        for f in field_d[P[i]]:
            ans[f] = i + 1
        field.remove(P[i])
    # print("field_d", field_d)
    # print("field", field)
for a in ans[1:]:
    print(a)

別解（sortedsetを使った場合）

import math
from bisect import bisect_left, bisect_right
from collections import defaultdict
from typing import Generic, Iterable, Iterator, TypeVar, Union, List

T = TypeVar("T")


class SortedSet(Generic[T]):
    BUCKET_RATIO = 50
    REBUILD_RATIO = 170

    def _build(self, a=None) -> None:
        """Evenly divide `a` into buckets."""
        if a is None:
            a = list(self)
        size = self.size = len(a)
        bucket_size = int(math.ceil(math.sqrt(size / self.BUCKET_RATIO)))
        self.a = [
            a[size * i // bucket_size : size * (i + 1) // bucket_size]
            for i in range(bucket_size)
        ]

    def __init__(self, a: Iterable[T] = []) -> None:
        """Make a new SortedSet from iterable.
        O(N) if sorted and unique / O(N log N)
        """
        a = list(a)
        if not all(a[i] < a[i + 1] for i in range(len(a) - 1)):
            a = sorted(set(a))
        self._build(a)

    def __iter__(self) -> Iterator[T]:
        for i in self.a:
            for j in i:
                yield j

    def __reversed__(self) -> Iterator[T]:
        for i in reversed(self.a):
            for j in reversed(i):
                yield j

    def __len__(self) -> int:
        return self.size

    def __repr__(self) -> str:
        return "SortedSet" + str(self.a)

    def __str__(self) -> str:
        s = str(list(self))
        return "{" + s[1 : len(s) - 1] + "}"

    def _find_bucket(self, x: T) -> List[T]:
        """Find the bucket which should contain x. self must not be empty."""
        for a in self.a:
            if x <= a[-1]:
                return a
        return a

    def __contains__(self, x: T) -> bool:
        if self.size == 0:
            return False
        a = self._find_bucket(x)
        i = bisect_left(a, x)
        return i != len(a) and a[i] == x

    def add(self, x: T) -> bool:
        """Add an element and return True if added. / O(√N)"""
        if self.size == 0:
            self.a = [[x]]
            self.size = 1
            return True
        a = self._find_bucket(x)
        i = bisect_left(a, x)
        if i != len(a) and a[i] == x:
            return False
        a.insert(i, x)
        self.size += 1
        if len(a) > len(self.a) * self.REBUILD_RATIO:
            self._build()
        return True

    def discard(self, x: T) -> bool:
        """Remove an element and return True if removed. / O(√N)"""
        if self.size == 0:
            return False
        a = self._find_bucket(x)
        i = bisect_left(a, x)
        if i == len(a) or a[i] != x:
            return False
        a.pop(i)
        self.size -= 1
        if len(a) == 0:
            self._build()
        return True

    def lt(self, x: T) -> Union[T, None]:
        """Find the largest element < x, or None if it doesn't exist."""
        for a in reversed(self.a):
            if a[0] < x:
                return a[bisect_left(a, x) - 1]

    def le(self, x: T) -> Union[T, None]:
        """Find the largest element <= x, or None if it doesn't exist."""
        for a in reversed(self.a):
            if a[0] <= x:
                return a[bisect_right(a, x) - 1]

    def gt(self, x: T) -> Union[T, None]:
        """Find the smallest element > x, or None if it doesn't exist."""
        for a in self.a:
            if a[-1] > x:
                return a[bisect_right(a, x)]

    def ge(self, x: T) -> Union[T, None]:
        """Find the smallest element >= x, or None if it doesn't exist."""
        for a in self.a:
            if a[-1] >= x:
                return a[bisect_left(a, x)]

    def __getitem__(self, x: int) -> T:
        """Return the x-th element, or IndexError if it doesn't exist."""
        if x < 0:
            x += self.size
        if x < 0:
            raise IndexError
        for a in self.a:
            if x < len(a):
                return a[x]
            x -= len(a)
        raise IndexError

    def index(self, x: T) -> int:
        """Count the number of elements < x."""
        ans = 0
        for a in self.a:
            if a[-1] >= x:
                return ans + bisect_left(a, x)
            ans += len(a)
        return ans

    def index_right(self, x: T) -> int:
        """Count the number of elements <= x."""
        ans = 0
        for a in self.a:
            if a[-1] > x:
                return ans + bisect_right(a, x)
            ans += len(a)
        return ans


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

ans = [-1] * (N + 1)
field = defaultdict(list)
std_set = SortedSet()

for i, p in enumerate(P):
    k = std_set.ge(p)
    # 大きい数がある場合
    if k is not None:
        field[p] = field.pop(k)
        std_set.discard(k)
    field[p].append(p)
    std_set.add(p)
    if len(field[p]) == K:
        for d in field.pop(p):
            ans[d] = i + 1
        std_set.discard(p)
print(*ans[1:], sep="\n")

ABC260 回想(Python)

目次

総括

A. A Unique Letter

B. Better Students Are Needed

C. Changing Jewels

D. Draw Your Cards

E. At Least One