AtCoder Beginner Contest 310 参加記録 A-D

2023年07月16日

今週もAtCoder Beginner Contest 310に参加をしました。

結果

A-Cの３完ノーペナでした。

ここのところD問題まではコンスタントに解けていたのですが、久しぶりに3完となりました。

ただ、コンテスト中も感じていましたが、今回のDは難しい問題でした。そのため、パフォーマンスは1236相当と、良い結果となりました。

Qlitreさんのfreee プログラミングコンテスト2023（AtCoder Beginner Contest 310）での成績：2130位
パフォーマンス：1236相当
レーティング：955→987 (+32) :)
Highestを更新しました！#AtCoder #freeeプログラミングコンテスト2023（ABC310） https://t.co/wp2o4re5ZJ
— Qlitre (@kuri_tter) July 15, 2023

早速ですが、復習を兼ねてA-Dまでを振り返っていきたいと思います。

A - Order Something Else

https://atcoder.jp/contests/abc310/tasks/abc310_a

ドリンクの値段Pと、割引後の価格であるQが与えられます。ただし割引する場合はN品ある食事から一つ頼まなければいけません。

そのようなときにドリンクを飲むため支払う合計金額の最小値を出力する、という問題です。

A問題ということを考えると問題文が長いと思いました。

単純にP円払って頼む場合と、割引のQ + 食事の最小値を比較すればいいです。

def solve():
    n, p, q = map(int, input().split())
    foods = list(map(int, input().split()))
    ans = min(p, q + min(foods))
    print(ans)


if __name__ == '__main__':
    solve()

B - Strictly Superior

https://atcoder.jp/contests/abc310/tasks/abc310_b

AtCoder商店にN個の商品があります。各商品は価格PiとCi個の機能を持っています。商品iのj番目の機能は整数Fi,jで表されます。

高橋くんは、商品同士の上位互換関係について調べます。

具体的には、以下の条件を満たす商品の組み合わせが存在するかどうかを判定します。

Pi ≥ Pjである。
商品jは商品iのすべての機能を持っている。
Pi > Pjであり、かつ商品jは商品iには存在しない機能を1つ以上持っている。

全ての条件を満たす組み合わせがあればYes,そうでなければNoを出力する問題です。

商品の数と機能の数は最大で100と小さいので、組み合わせを全探索すればいいです。

条件を調べるところが複雑なので、適宜関数に切り出すと見通しがよくなります。

def check(item1, item2):
    pi, ci, *a_list_i = item1
    pj, cj, *a_list_j = item2
    # 価格が高いとFalse
    if pj > pi:
        return False

    # 機能がない場合False
    for fi in a_list_i:
        if fi not in a_list_j:
            return False
    # 価格が安い、もしくは、機能が多ければTrue
    if pj < pi:
        return True
    else:
        if cj > ci:
            return True
        else:
            return False


def solve():
    n, m = map(int, input().split())
    items = [list(map(int, input().split())) for _ in range(n)]

    # 組み合わせを全探索
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            item1 = items[i]
            item2 = items[j]
            # 条件を満たしていたらYesで終了
            if check(item1, item2):
                exit(print('Yes'))
    print('No')


if __name__ == '__main__':
    solve()

C - Reversible

https://atcoder.jp/contests/abc310/tasks/abc310_c

ある数のボールがN本の棒に刺さっています。各ボールには英小文字が書かれています。

各棒に刺さっているボールの英小文字列を表す文字列Siが与えられます。

2つの棒が同じであるとは、片方の棒に刺さっているボールの英小文字列ともう一方の棒に刺さっているボールの英小文字列が一致するか、前後反転した場合に一致する場合です。

N本の棒の中に存在する異なる棒の種類の数を出力する、という問題です。

問題文が長くてややこしいですが、以下のように言い換えられます。

ある棒に刺さっている文字と、同じ文字がある場合は一種類。
何種類あるか

文字列と反転させた文字列を二つ用意して、昇順にソートし、そうして結合した文字を一種類とみなす、という風にやりました。

// 反転させる
cba -> abc
// 昇順でくっつける
abccba

あとは集合に突っ込めば何種類の文字があるか分かります。

n = int(input())

a_set = set()
for _ in range(n):
    s = input()
    s_rev = s[::-1]
    tmp = [s, s_rev]
    tmp.sort()
    char = tmp[0] + tmp[1]
    a_set.add(char)

print(len(a_set))

D - Peaceful Teams

https://atcoder.jp/contests/abc310/tasks/abc310_d

N人のスポーツ選手がいます。

選手たちは互いに相性の悪い選手のペアがM組あり、i組目の相性の悪い組は選手Aiと選手Biです。

以下の条件を満たしながら、T個のチームに分けることを考えます。

各選手は1つのチームに所属しなければならない。
各チームには少なくとも1人の選手が所属しなければならない。
相性の悪い選手Aiと選手Biは同じチームに所属してはならない。

与えられた条件を満たすチーム分けの方法が何通りあるかを求める、という問題です。

難しかったです。サンプルすら通すことができませんでした。

そもそも相性が悪い云々の前に、N人の人間をT個のチームに振り分ける、ということができませんでした。

まずは、N人の人間をグループ分けするような関数を組んでみました。

def find_all_groupings(p: int, groups: list, n: int, group_count: int) -> list:
    """
    n人をgroup_count数のグループに分けるような組み合わせを全列挙して返す
    :param p:startのインデックス。大体０で始まる
    :param groups: グループ分け組み合わせ。最初は空の配列を渡す
    :param n:総人間数
    :param group_count:
    :return:[[groups],[groups]...]
    """
    if p == n:
        if len(groups) == group_count:
            return [groups]
        else:
            return []
    else:
        res = []
        for j, group in enumerate(groups):
            new_groups = groups.copy()
            new_group = group.copy()
            new_group.append(p)
            new_groups[j] = new_group
            res += find_all_groupings(p + 1, new_groups, n, group_count)
        # group_count未満だったらgroupを増やす
        if len(groups) < group_count:
            new_groups = groups.copy()
            new_groups.append([p])
            res += find_all_groupings(p + 1, new_groups, n, group_count)
        return res

この関数はこう使います。

ret = find_all_groupings(0, [], 4, 2)
print(ret)
>>>
[[[0, 1, 2], [3]],
 [[0, 1, 3], [2]],
 [[0, 1], [2, 3]],
 [[0, 2, 3], [1]],
 [[0, 2], [1, 3]], 
 [[0, 3], [1, 2]],
 [[0], [1, 2, 3]]]

今回のNの最大数は10と非常に小さいです。そのため、一番多くて10人を5つのチームに分ける場合でしょうか。

ret = find_all_groupings(0, [], 10, 5)
print(len(ret))
>>>
42525

それでも高々4万ほどの組み合わせ数なので、悪い組み合わせがないか全探索すれば答えが出せます。

関数を使って解く場合。

from itertools import combinations


def find_all_groupings(p: int, groups: list, n: int, group_count: int) -> list:
    """
    n人をgroup_count数のグループに分けるような組み合わせを全列挙して返す
    :param p:startのインデックス。大体０で始まる
    :param groups: グループ分け組み合わせ。最初は空の配列を渡す
    :param n:総人間数
    :param group_count:
    :return:[[groups],[groups]...]
    """
    if p == n:
        if len(groups) == group_count:
            return [groups]
        else:
            return []
    else:
        res = []
        for j, group in enumerate(groups):
            new_groups = groups.copy()
            new_group = group.copy()
            new_group.append(p)
            new_groups[j] = new_group
            res += find_all_groupings(p + 1, new_groups, n, group_count)
        # group_count未満だったらgroupを増やす
        if len(groups) < group_count:
            new_groups = groups.copy()
            new_groups.append([p])
            res += find_all_groupings(p + 1, new_groups, n, group_count)
        return res


def solve():
    n, t, m = map(int, input().split())
    # 悪い組み合わせ
    bad = set()
    for _ in range(m):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        bad.add((u, v))
    ans = 0
    all_groups = find_all_groupings(0, [], n, t)
    for teams in all_groups:
        flg = True
        # 各チームを繰り返す
        for j in range(t):
            members = teams[j]
            # 1人しかいない場合は無視
            if len(members) == 1:
                continue
            # 組み合わせを列挙
            combi = combinations(members, 2)
            # 全探索
            for u, v in combi:
                # badな組み合わせだったらFalse
                if (u, v) in bad or (v, u) in bad:
                    flg = False
                    break
            if not flg:
                break
        # badな組み合わせがなかったら答えに足す
        if flg:
            ans += 1
    print(ans)


if __name__ == '__main__':
    solve()

これで余裕をもってACできますが、一般的には以下のように探索の際に枝刈りをするイメージでしょうか。

関数名を書き換えてます。

from collections import defaultdict

n, t, m = map(int, input().split())
bad = defaultdict(set)
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    bad[a].add(b)
    bad[b].add(a)

ans = 0


def dfs(p, teams):
    if p == n:
        if len(teams) == t:
            global ans
            ans += 1
    else:
        for team in teams:
            ok = True
            for member in team:
                # badな関係があったらそのteamは参加できない
                if p in bad[member] or member in bad[p]:
                    ok = False
                    break
            if ok:
                # teamに加える
                team.append(p)
                # 次の人に進める
                dfs(p + 1, teams)
                # 戻ってきたらpopして次のteamを見る
                team.pop()
        # t未満だったらteamを増やす
        if len(teams) < t:
            teams.append([p])
            dfs(p + 1, teams)
            teams.pop()


dfs(0, [])
print(ans)

難しい問題でした。

今回の用にN人をチーム分けするようなケースは他でも出そうです。計算量は増えますが、一般化して損はないと思いました。

おわりに

レートはあがったのですが、やはりD問題が解けなかったのが悔しいなーと思った結果でした。

再帰関数の実装が苦手なのでなんとか補っていきたいところです。ではでは。

記事一覧へ