もはや毎週の恒例になっていますが、今週もAtCoder Beginner Contest 308に参加をしました。

ここのところはコンテストをtypescriptで振り返る、という記録をnoteで行っていました。

https://note.com/kuri_tter/n/n9ed0acc92414

せっかく自分の日記サイトもありますし、何より最近リニューアルをしたばかりなので、妙な愛着も沸いているタイミングでもあります。そのため、今後はこちらでコンテスト記録を更新していこうかなあと考えています。

結果

今回は、変則的でA,B,D,Fの４完という結果でした。

微増。
QlitreさんのCodeQUEEN 2023 予選 (AtCoder Beginner Contest 308)での成績：2245位
パフォーマンス：1086相当
レーティング：923→940 (+17) :)
Highestを更新しました！#AtCoder #CodeQUEEN2023予選(ABC308) https://t.co/POjvplbBhn

— Qlitre (@kuri_tter) July 1, 2023

A,Bまでは順調にいったものの、C問題にはまってしまい、Dを先に解きました。

その後、E問題を眺めたがよくわからず、駄目元でF問題を見てみたら、シンプルそうな問題だったこともあり、なんとか解くことができました。その後にC問題に戻るも制限時間内に実装をできず。

コンテスト中に初めてF問題を解くという経験ができたので、よかったです。

それでは早速コンテストを振り返っていきたいと思います。

A - New Scheme

https://atcoder.jp/contests/abc308/tasks/abc308_a

数列が与えられて以下の条件をすべて満たすか判定する問題です。

• 広義単調増加である
• すべて100以上675以下である
• 全て25で割り切れる

A問題ということを考えると難易度が高めだと思いました。

初めに答えをYesに設定しておいて、条件に合わなかったらNoに切り替えるという考え方で解きました。

a_list = list(map(int, input().split()))

ans = 'Yes'
# 広義単調増加か判定
for i in range(1, len(a_list)):
    now = a_list[i]
    prev = a_list[i - 1]
    if now < prev:
        ans = 'No'

# 残り二つの条件を判定
for num in a_list:
    if num < 100 or num > 675:
        ans = 'No'
    if num % 25 != 0:
        ans = 'No'

print(ans)

B - Default Price

https://atcoder.jp/contests/abc308/tasks/abc308_b

高橋君の食べた寿司の皿の色と、皿の色ごとの価格が情報として与えられます。

そうして、合計金額を求める問題です。

辞書に値を記録することで問題を解きました。

from collections import defaultdict

n, m = map(int, input().split())
dishes = list(map(str, input().split()))
colors = list(map(str, input().split()))
prices = list(map(int, input().split()))
# 皿の値段を記録
d = defaultdict(int)
for i in range(m):
    color = colors[i]
    price = prices[i + 1]
    d[color] = price

ans = 0
for color in dishes:
    # 色がない場合の金額
    base = prices[0]
    ans += d.get(color, base)

print(ans)

C - Standings

https://atcoder.jp/contests/abc308/tasks/abc308_c

N人がコイントスを行い、それぞれがA回表、B回裏を出したことが分かっています。

そのようなときにA/(A+B)で計算される成功率を高い順に求める、という問題です。

露骨に自分の経験不足が出た結果なのか、時間内に解くことができませんでした。

率直にやると以下のような形でしょうか。

n = int(input())

result = []
for i in range(n):
    a, b = map(int, input().split())
    rate = a / (a + b)
    result.append((rate, i + 1))

result.sort(key=lambda x: (-x[0], x[1]))
for _, i in result:
    print(i, end=' ')

通常のケースであればこれで十分なのですが、コンピューターは小数点を正確に扱うのが非常に苦手（原理は詳しくないですが）なので、特殊なケースではWAとなってしまいました。

コンテスト中になんとか、計算できるように試行錯誤をしました。

例えば、PythonにはFractionという分数を扱えるライブラリがあります。

from fractions import Fraction

print(Fraction(2, 3))
>>>
2/3

これは正確に計算をしてくれますが、速度が非常に遅く、PyPyで提出してもTLEでした。

それと、割る数字の(A+B)の最小公倍数を求めて、全てのAにかけてから割るということを試しましたがTLEでした。

解説を見て解きました。色々とやり方があるみたいです。

Decimalを使う：

from decimal import Decimal

n = int(input())

result = []
for i in range(n):
    a, b = map(int, input().split())
    rate = Decimal(a) / Decimal(a + b)
    result.append((rate, i + 1))

result.sort(key=lambda x: (-x[0], x[1]))
for _, i in result:
    print(i, end=' ')

なぜかPyPyだとTLEになります。

比較関数を使う：

from functools import cmp_to_key


def compare(a, b):
    x1, y1, i1 = a
    x2, y2, i2 = b
    s = x1 * y2 - x2 * y1
    if s > 0:
        return 1
    else:
        if s < 0:
            return -1
        else:
            return 0


def solve():
    n = int(input().strip())
    ab = []
    for i in range(n):
        a, b = map(int, input().strip().split())
        ab.append((-a, a + b, i + 1))

    ab.sort(key=cmp_to_key(compare))
    for i in range(n):
        print(ab[i][2], end=' ')


solve()

でかい数をかけて誤差をなくす：

10^20をかけるといいらしいです。

def solve():
    n = int(input().strip())
    ab = []
    inf = 10 ** 20
    for i in range(n):
        a, b = map(int, input().strip().split())
        r = (a * inf // (a + b))
        ab.append((r, i + 1))
    ab.sort(key=lambda x: (-x[0], x[1]))
    for i in range(n):
        print(ab[i][1], end=' ')


solve()

いろいろと勉強になりました。

D - Snuke Maze

https://atcoder.jp/contests/abc308/tasks/abc308_d

アルファベット小文字からなるグリッド情報が与えられて、左上から右下まで移動することを考えます。

このときsnukesnu...というように"snuke"の文字の順番にたどっていくことがルールです。

そのような制約で、右下までたどり着けるか判定する問題です。

幅優先探索のお手本のような問題だと思いました。こういう問題は個人的に好きです。

各マスを辿るときに移動回数を保持するようにします。

snukeは５文字なので、移動回数%5で余りを出せば次にどの文字へ行くべきか割り出せます。

そのように試行して右下にたどりつけたらYes、そうでなかったらNoというように解きました。

from collections import deque

h, w = map(int, input().split())
grid = [list(input()) for _ in range(h)]

# 開始地点がsじゃなかったらその時点で駄目
if grid[0][0] != 's':
    exit(print('No'))

que = deque()
# 初期座標(0,0)と移動回数をセット
que.append((0, 0, 0))
# 既にみたマスの記録
vis = set()
vis.add((0, 0))
# 移動方向
di = [(-1, 0), (0, 1), (1, 0), (0, -1)]
snuke = 'snuke'
while que:
    now_r, now_c, cnt = que.popleft()
    # 到達したらYes
    if now_r == h - 1 and now_c == w - 1:
        exit(print('Yes'))
    idx = (cnt + 1) % 5
    nxt_char = snuke[idx]
    # 上下左右のマスを見る
    for r, c in di:
        nxt_r, nxt_c = now_r + r, now_c + c
        # 範囲内か調べる
        if 0 <= nxt_r <= h - 1 and 0 <= nxt_c <= w - 1:
            # 移動先が次の文字で、訪れてなかったらqueに加える
            if grid[nxt_r][nxt_c] == nxt_char:
                if (nxt_r, nxt_c) not in vis:
                    vis.add((nxt_r, nxt_c))
                    que.append((nxt_r, nxt_c, cnt + 1))

# 到達できなかった
print('No')

E - MEX

https://atcoder.jp/contests/abc308/tasks/abc308_e

コンテスト中は解けず解説をみてやりました。

0,1,2からなる数列と同じ長さの"M","E","X"からなる文字列が与えられます。

そのようなときに順番につなげて"MEX"となるようなインデックスの組み合わせを考えます。

MEEX

例えばこういう時は(1,2,4),(1,3,4)の二つが"MEX"となるインデックスの組み合わせです。

そのような全ての組み合わせにおいて、数列に対応したインデックスの三つの数字のMEX（a,b,c）を足し合わせたらいくつになるか？

ということを求める問題です。

難しい問題だと思いました。

MEX(a,b,c)がとりうる値は0,1,2しか数字がないので、そんなに多くないです。

真ん中のEのインデックスにのみ注目すれば解けるらしいです。

つまり、i番目のEを見ているときに「そのインデックスまでに何個Mがあるか」、「そのインデックス以降に何個Xがあるか」

ということをまず、考えます。

今回はMEX(a,b,c)を求める必要があるので、少し発展させて、MとXの数を数えながら、0,1,2のそれぞれの出現回数も数え上げます。

あとはMとXの0,1,2の出現回数ごとに答えを足し上げていく、という流れです。

# mexの計算
def calc_mext(a, b, c):
    for i in range(3):
        if i != a and i != b and i != c:
            return i
    return 3


def solve():
    n = int(input())
    a_list = list(map(int, input().split()))
    a_chars = list(input())
    # i番目までにmで0,1,2が何回出現したか
    m_count = [[0, 0, 0] for _ in range(n + 1)]
    for i in range(n):
        # 今の出現回数をコピー
        for j in range(3):
            m_count[i + 1][j] = m_count[i][j]
        # Mだったら数字をプラス
        if a_chars[i] == 'M':
            num = a_list[i]
            m_count[i + 1][num] += 1
    # i番目以降にxで0,1,2が何回出現したか
    x_count = [[0, 0, 0] for _ in range(n + 1)]
    for i in reversed(range(n)):
        # 出現回数をコピー
        for j in range(3):
            x_count[i][j] = x_count[i + 1][j]
        if a_chars[i] == 'X':
            num = a_list[i]
            x_count[i][num] += 1

    ans = 0
    # 文字を繰り返す
    for i in range(n):
        if a_chars[i] == 'E':
            # 0,1,2の組み合わせを全探索
            for j in range(3):
                for k in range(3):
                    # それぞれの数字の出現個数 x mex(a,b,c)を答えに足す
                    cnt_m = m_count[i][j]
                    cnt_x = x_count[i][k]
                    a_mex = calc_mext(j, a_list[i], k)
                    ans += cnt_m * cnt_x * a_mex

    print(ans)


solve()

F - Vouchers

https://atcoder.jp/contests/abc308/tasks/abc308_f

商品の価格リストと、クーポンの情報が与えられます。

クーポンを使うと、価格がL円以上の商品を選び、D円割り引いて商品を購入できます。

適切にクーポンを使用して、支払い金額を最小にする、という問題です。

クーポンをできるだけ使うのがカギとなります。

コンテスト中は貪欲に、「割り引き金額が多いクーポンを一番金額が近いものに使う」、としたらACができました。

図で書くとこういうイメージでしょうか。

なるべく近い金額のものにクーポンを使うようにすれば、その後のクーポンを使える確率が高くなります。

あとは実装ですが、tatyamさんのSortedMultiSetを使わせていただきました。

# https://github.com/tatyam-prime/SortedSet/blob/main/SortedMultiset.py
import math
from bisect import bisect_left, bisect_right, insort
from typing import Generic, Iterable, Iterator, TypeVar, Optional, List

T = TypeVar('T')


class SortedMultiset(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 SortedMultiset from iterable. / O(N) if sorted / O(N log N)"""
        a = list(a)
        if not all(a[i] <= a[i + 1] for i in range(len(a) - 1)):
            a = sorted(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 "SortedMultiset" + 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 count(self, x: T) -> int:
        """Count the number of x."""
        return self.index_right(x) - self.index(x)

    def add(self, x: T) -> None:
        """Add an element. / O(√N)"""
        if self.size == 0:
            self.a = [[x]]
            self.size = 1
            return
        a = self._find_bucket(x)
        insort(a, x)
        self.size += 1
        if len(a) > len(self.a) * self.REBUILD_RATIO:
            self._build()

    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) -> Optional[T]:
        """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) -> Optional[T]:
        """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) -> Optional[T]:
        """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) -> Optional[T]:
        """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


def solve():
    n, m = map(int, input().split())
    a_list = list(map(int, input().split()))
    sorted_multi_set = SortedMultiset(a_list)
    L = list(map(int, input().split()))
    D = list(map(int, input().split()))
    coupons = []
    for l, d in zip(L, D):
        coupons.append([l, d])
    # Dを降順にソートする
    coupons.sort(key=lambda x: -x[1])
    # 貪欲に使う
    ans = 0
    for l, d in coupons:
        # lに一番近い値
        ge = sorted_multi_set.ge(l)
        if ge:
            # クーポンを使う
            ans += ge - d
            # 商品を取り除く
            sorted_multi_set.discard(ge)

    # クーポンを使えなかった商品を答えに足す
    for price in sorted_multi_set:
        ans += price

    print(ans)


solve()

おわりに

ライブラリの力を借りたおかげもあるのですが、初めてコンテスト中にF問題が解けたので嬉しかったです。

一方でC問題のような小数点問題を解けなかったので、地力をつける必要があるなと痛感しました。

引き続きよろしくお願いします。ではでは。